5完。
各問題
A - ^{-1}
P_i == X となる i を答えるだけです。
B - Playing Cards Validation
書かれている条件をプログラムに書き下すだけです。重複チェックは set でやると楽。
C - Ladder Takahashi
グラフを作ってBFSをやるだけです。ループにはまらないようにすでに訪れた階に再度行かないように注意。
D - Takahashi's Solitaire
問題文を見た瞬間ぎょっとしてしまいますが、要するにソートしてから、増加量が1以下に収まる範囲のかたまりを取り除くことが可能、ということです。ただし、(X+1) mod M なので、M - 1 の次は 0 につながることに注意です。これは典型の「同じ配列を横に二つ並べる」をすれば実装が楽になります。
入力例1の 3 0 2 5 5 3 0 6 3 だと、ソートして 0 0 2 3 3 3 5 5 6、二つ並べて 0 0 2 3 3 3 5 5 6 0 0 2 3 3 3 5 5 6 となり、ここから取り除ける範囲を確定していきます。この場合 0 0, 2 3 3 3, 5 5 6 0 0, 2 3 3 3, 5 5 6 となります。
あ、二つ並べるテクを使う場合、例えば M=7 で 0 1 2 3 3 4 5 5 6 みたいなのが与えられたとき、答えをマイナスにしないように注意です。
E - Crystal Switches
ダイクストラ法をすればよいですが、スイッチの存在があります。
頂点数が N*2 あると考えて、a = 1 の方を 1 から N に、a = 0 を N+1 から N*2 に割り当てればよく、スイッチを押すとお互いを行き来できると考えて s_i と s_i + N に重さ 0 の辺を張ればよいです。
F - Sorting a Matrix
しばらく考えましたが全然わからず。
G - Random Walk to Millionaire
どう見てもDPですが、単純にやると時間も空間もたりなさそうで悩んでるうちに終わってしまいました。Fで留まらずにこっちをもっと早く見ていればワンチャンあったかも...。
まとめ
Fがとんでもない崖で、Eまでほぼ詰まらず解けたおかげで青パフォ中位が取れてしまいました。レートもHighest更新で1400台に突入！毎回こんなだったらいいのに！！
