非想定解っぽいですがまとめておきます。 Problem - F - Codeforces 問題概要 問題文中の図のように、一列に並んだ 個のノードを挟むように根付き木が2つ与えられる。それぞれの頂点数は であり、葉の数はいずれも で、それぞれの木について各ノードごとに1…

お題箱より。 F - Laminate 解法 問題で最小化すべき値である「塗る操作の回数」を「コスト」と呼ぶことにします。また各 の値を「高さ」と呼ぶことにします。 説明をやりやすくするため、0列目に である列が存在すると考えます。 の値が確定した後、コスト…

E - Majority of Balls 解法 キーとなるのは以下の2つの気付きです。 に対する質問の答えと に対する質問の答えは必ず異なる。片方が Red であればもう片方は Blue である。 もし「赤青が半々ずつ」ということが分かっている 個のボールの集合が得られたとす…

F - Sugoroku 解法 個の連続するゲームオーバーマスがある場合はゴール不可能なので、そうでないことを仮定します。「最小ターン数」と「辞書順最小」、それぞれに注目します。 ゴールするための最小ターン数はDP等で求めることができます（後で具体的に説明…

お題箱より。 Problem - D - Codeforces 問題概要 ※解説の都合上、0-indexedと半開区間での記述に書き換えます。 非負とは限らない整数列 と、正整数 が与えられる。 この数列の連続部分列 について、そのスコアを と定める。ただし長さ0の連続部分列のスコ…

お題箱より。 F - Xor Sum 3 線形代数を用いた解法の正当性について理解したい…というリクエストだったので、そこを重点的に書きます。 前段の考察 を表すビット桁を 桁目と表記することにします。一番下が0桁目です。 各ビット桁ごとに、 のうち 桁目が立っ…

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

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

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

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

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

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