ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

HACK TO THE FUTURE 2020予選 参加記録

HACK TO THE FUTURE 2020予選 - AtCoder なんと全体10位で本戦に進むことができました! やったことを軽く書いておこうかと思います。けっこう雑な焼きなまし法なので、あまり参考になるかは分かりませんが… ビジュアライザのスクリーンショット等はexample_…

AtCoder Grand Contest 040 B - Two Contests

B - Two Contests 本番では考察不足で2ペナを出しましたが…自分の考察がある程度整理できたので書きます。 解法 公式解説にならい、それぞれのコンテストを「集合」、問題 を解ける人の範囲を「区間 」、コンテストの楽しさを「含まれる区間の共通部分の長さ…

JOI春合宿2015 K - 遺産相続

お題箱より。JOIの解説記事は初めてかな…? K - 遺産相続 解説途中の証明についてのリクエストだったのでそこを重点的に書きます。 解法 最大全域木として考える 都市を「頂点」、鉄道を「辺」、鉄道の収益を「辺重み」と考えます。 「閉路ができない範囲で…

Educational Codeforces Round 75 E2. Voting (Hard Version)

お題箱より。 Problem - E2 - Codeforces 問題概要 選挙の投票者が 人いて、全員が自分を支持するようにしたい。投票者 が自分を支持する条件は2つあり、どちらかを満たすと支持する。 金額 を払って買収する。 他の投票者のうち 人以上が自分を支持している…

CPSCO2019 Session1 F - Fruits in Season

お題箱より。 F - Fruits in Season 解法 最小値の最大化問題です。このタイプの問題はまず二分探索を考えてみる価値があります。 判定問題として、ある に対して「果物の美味しさの最小値を 以上にできるか?」という問題を考えます。最小値の最大化問題に…

Codeforces Round #358 (Div. 2) D. Alyona and Strings

お題箱より。 Problem - D - Codeforces 問題概要 文字列 が与えられ、それぞれの長さは である。また整数 が与えられる。 以下の条件を満たすような 個の文字列の組 の、長さの総和の最大値を求めよ。 のどの文字列も空でない。 のどちらにも、 がこの順番…

AtCoder Beginner Contest 144 E - Gluttony

E - Gluttony 解法 この問題はいくつか考察ステップが必要なので、順に見ていきましょう。 記法などについて 簡単のため、入力として与えられる値の集合 を単に 、 を単に と書くことにします。 また、最小化すべき値である「メンバーと食べ物の組み方を決め…

Codeforces Round #595 (Div. 3) D2. Too Many Segments (hard version)

お題箱より。 Problem - D2 - Codeforces 問題概要 整数を端点とする 個の閉区間 が与えられる。これらから0個以上の区間を捨てて、全ての整数点について「その整数点を含んでいる区間は 個以下である」という状態にしたい。 捨てる区間の最小個数と、その選…

Kyoto University Programming Contest 2019 E - 根付き森二人用ゲーム

お題箱より。 E - 根付き森二人用ゲーム 解法 それぞれの木を小規模なゲームとして解く スタート地点からある木に移動し、その木の葉に到達してスタート地点に戻るまでの一連の動作を考えます。このときゲームに本質的に影響するのは「次にスタート地点で手…

Codeforces Round #594 (Div. 1) B. The World Is Just a Programming Task (Hard Version)

Problem - B - Codeforces 問題概要 長さ の括弧列 が与えられる。長さ の括弧列のスコアを、「 を 回だけ右巡回シフトした文字列が正しい括弧列になっている」という条件を満たす の個数とする。 に対して1度だけ、2箇所を選んでスワップする操作を行うこと…

AtCoder Beginner Contest 143 F - Distinct Numbers

F - Distinct Numbers 解法 色々な解法があるみたいですが…この記事ではそれぞれの について独立に解きます。ある について解くときには、可能な操作回数には単調性があるので二分探索できます。 ある と操作回数 を固定したときに、操作を 回行えるかどうか…

AtCoder Regular Contest 077 E - guruguru

お題箱より。 E - guruguru 後半は公式解説と少し違う方法になっています。 解法 お気に入りで節約できる回数を定式化する ある1つの に対する から への移動を考えます。まず簡単のため、 と仮定しておきます。移動元と移動先をそれぞれ と書くことにします…

Codeforces Global Round 5 E. Balanced Binary Search Trees

Problem - E - Codeforces 問題概要 以下の条件を満たす根付き木を二分探索木と呼ぶ。 任意の頂点 について以下が成り立つ。 「左側の子」と「右側の子」がそれぞれ高々1個存在する。 左側の子孫が存在する場合、それら全ての頂点番号は より小さい。 右側の…

Codeforces Round #590 (Div. 3) E. Special Permutations

お題箱より。 Problem - E - Codeforces Editorialのソースコードがよく分からないというリクエストだったんですが、見たところ確かによく分からなかったので、私の解法を書きます。 問題概要 長さ の順列 を と定義する。 長さ の整数列 ()が与えられる。…

Educational Codeforces Round 74 E. Keyboard Purchase

お題箱より。ただ、この問題は元々書こうと思っていました。 Problem - E - Codeforces 問題概要 文字のアルファベットからなる長さ の文字列 が与えられる。アルファベット 個を並べる順列 を1つ決めた時、「 の隣り合う2文字のペアそれぞれについて、その…

第一回日本最強プログラマー学生選手権決勝 C - Maximize Minimum

お題箱より。同じ問題に2件リクエストがありました。 C - Maximize Minimum 簡潔に飛ばし気味ではあるものの公式解説の説明が分かりやすいと思うので、流れは公式解説に沿いつつ図や行間を補って書いていきます。 解法 イチゴの最適な折り返し方 まずクエリ…

Kodamanと愉快な仲間たち S - 五等分の分銅

お題箱より。 Programming Problems and Competitions :: HackerRank 解法 分数のままでは考えにくいので、通分します。 の最大公約数は なので、まず重りを全て 倍して とします。そして目標の重さも に置き換えます。するとこの問題は「重さ の重りをそれ…

AtCoder Beginner Contest 054 D - Mixing Experiment

お題箱より。 D - Mixing Experiment 半分全列挙解法を…とのリクエストだったので、そちらを書きます。 解法 個の薬品をグループ0・グループ1に分け、それぞれについて薬品の選び方を決めたとします。これらを混ぜてちょうど混合比 になっているかどうかを判…

Codeforces Round #587 (Div. 3) F. Wi-Fi

お題箱より。 Problem - F - Codeforces セグメント木を使わない解法を…とのリクエストだったので、何通りか解法を紹介します。 問題概要 個の部屋が並んでいて、順に番号 が付けられている。これらの部屋全てにインターネット回線を提供したい。 回線提供に…

Codeforces Round #587 (Div. 3) E2. Numerical Sequence (hard version)

Problem - E2 - Codeforces 問題概要 正整数 に対して、 を十進表記で書いたものをこの順に連結した文字列を とする。例えば "1234567891011" である。 そして、 をこの順に連結した無限の長さの文字列を考える。与えられる 個の整数 に対して、この文字列の…

AtCoder Grand Contest 038 B - Sorting a Segment

B - Sorting a Segment 公式解説と少し違う方法で解いたので記録。 解法 ある長さ の区間を昇順に並び替えた時に、値が変更される最左のインデックスを 、最右のインデックスを とします。この時操作の結果は、閉区間 内の要素を昇順に並び替えたものとなり…

AtCoder Beginner Contest 141 E - Who Says a Pun?

E - Who Says a Pun? 解説で別解として紹介されている二分探索+ローリングハッシュで通したので書いておきます。 解法 条件を満たす長さで二分探索 「文字列 の連続部分文字列として位置が重ならずに2回以上出現する、長さ の文字列が存在する」ということ…

AtCoder Grand Contest 024 E - Sequence Growing Hard

E - Sequence Growing Hard 公式解説とだいたい同じ考察を辿ったんですが、最後の計算で違うことをしたので書いておきます。 解法 用語 要素を挿入して、辞書順でより大きくなる条件は 長さ の数列に1つ要素を挿入して、辞書順でより大きい長さ の数列を作る…

競プロでWAが出たときのランダム入力データ生成入門

概要 競技プログラミングで提出コードがWAになったとき、実際に不正解となるような入力データを入手できると役に立つ場合があります。ただ多くのコンテストサイトでは、コンテスト中には入力データを見ることはできません。 そのような時に、小さめの入力デ…

TTPC2019 オンライン参加記

てんぷらさんとチームpurameriaで出場しました。オンライン参加でしたが、せっかくのチーム戦だったので記事を書こうと思います。 はじまり アルメリアさんへTTPCチーム組みませんかてんぷら— てんぷら (@tempura_cpp) August 1, 2019 ご指名いただきました…

Codeforces Round #577 (Div. 2) B. Zero Array

お題箱より。 Problem - 1201B - Codeforces 問題概要 個の正整数 が与えられる。これに 異なる2つの要素を選び、それぞれの要素を1減らす。 という操作を繰り返すことで全ての要素を0にできるかどうか判定せよ。 制約 解法 この判定は競技プログラミングで…

第一回日本最強プログラマー学生選手権-予選- C - Cell Inversion

C - Cell Inversion 解法 各マスの操作のされ方は、 自分より左のマスとペアになって、1つの反転操作区間の終点になる 自分より右のマスとペアになって、1つの反転操作区間の始点になる のどちらかです。そして各マスがそのどちらになるかは、実は端から順番…

「みんなのプロコン」本選 A - YahooYahooYahoo

お題箱より。 A - YahooYahooYahoo 解法 「編集距離DP」を知ろう まずは「編集距離DP」なるものを説明します。2つの文字列 の編集距離とは、文字列 に以下の操作を好きな順序で行って文字列 に一致させるための、操作回数の最小値です。 置換: の任意の1文…

AtCoder Beginner Contest 135 D - Digits Parade

お題箱より。 D - Digits Parade 「与えられた条件に従って各桁の数字を決められる」「出来上がる整数のうち、余りが特定の条件を満たすものを数える」という、是非とも押さえておきたい問題パターンの入門としてぴったりです。いつも以上に丁寧めに書きたい…

AtCoder Beginner Contest 138 F - Coincidence

F - Coincidence 解法 考察も実装もそこそこ重い問題です。順に考えていきましょう。 記法について 剰余演算を記号 、XOR演算を記号 で表すことにします。 またこの記事では数え上げの対象である2数のペアを ではなく の順番で記載しています。 ビットだけの…