Educational Codeforces Round 76 (virtual) 解法

コンテストページ

Dashboard - Educational Codeforces Round 76 (Rated for Div. 2) - Codeforces

解法

✔A - Two Rival Students

まずは N を気にせず好きなだけ離すのですが、限度がありますから、N - 1 との Min を取りましょう。

✔B - Magic Stick

x が 4 以上なら OK、そうではなく y が 4 以上なら NG です。それ以外は有限通りです。

初めこの問題は YES / NO ではなく最小手数と思ったのですが、最小手数の場合はどのように解くのでしょう。前から見ると先読みが必要になるのですが、逆から見ると、「3 で割って 2 を掛ける」を優先的に行い、x を下回ったら「1 を足す」で調整が最適に見えます。どうなのでしょう。（大して考えていない顔です。）

✔C - Dominated Subarray

実は条件は、同じ要素を 2 つ以上持つことと同値です。こどふぉさんは優しいですから、要素の値は N 以下です。そう、座圧がいりません（感涙）値が同一な 2 つの要素であって、距離の最小のものを探しましょう。前から順に見て、書く値について最後にそれを見た場所を管理です。

✔D - Yet Another Monster Killing Problem

1 日のうち i 体目に相手を出来る最大の強さを b[i] としましょう。b[0] よりも強い敵がいれば詰みです。シュミレーションです。前から順に見て、倒せるだけ倒しましょう。その日見た最強の敵の顔を忘れてはいけません。b を見て、それが倒せなさそうならば一旦退却、睡眠を取ってから 0 体目としてお相手です。冒頭の例外処理のおかげで、この勝負はかならず勝利することが出来ます。

✔E - The Contest

入力を 0 と 1 と 2 からなる N 項の列だと思っておきましょう。最終的に配る問題数に応じてこれらを 3 つに区切ると思うと、「誤った」区域に入っている数字の個数が交換回数です。

0 人目と 1 人目の境界を全探索です。交換は 2 種類に分けることが出来ます。

0 人目と他の 2 人の交換は、0 の数を前計算すれば簡単にわかります。残るは 1 人目と 2 人目の交換です。これは、2 人目の部分に入っている 1 の数と、1 人目の部分に入っている 2 の数の合計値です。このままでは 0 人目と 1 人目の境界に依存してしまいそうですが、実はこれは 2 人目の部分に入っている 1 の数から 2 の数を引いたものの一次関数ですから、それを前計算です。