Good Bye 2016 A問題からE問題

黄色コーダーで終わりました。個人的には結構強くなったと思うんですが、数値だけ見ると去年の自分と大差ないですね。というか去年の自分が思ってるより強いですね。

http://codeforces.com/contest/611

A. New Year and Hurry

どこまで使えるかを実際に試してみれば良い。

B. New Year and North Pole

おそらく South 100000 みたいな入力がきたときの処理がどうなるかで迷う。実は南極にたどりついて、なお南方向の移動が残っている場合は条件 2 に反するため NO である。そのままくるくる回ると解釈してしまうと不正解を得る上に、実装も大変になるだろう。

C. New Year and Rating

開始時のレートが $x$ だとして遷移のグラフを書いてみる。下図のような遷移をしたのであれば、$x-30 \le 1899$, $x-20 \le 1899$ が成り立つような最大の $x$ を求めればよくて、これは $x=1919$ となる。

div.1 回なのにレートが1900を下回っていることがある可能性があるので、開始時の最小レートも同様の手法で求めておく。（開始時の最小レート）>（最大レート）になっていた場合は Impossible だとわかる。

また div.1 回しかない場合はいくらでも開始時のレートをあげられるため Infinity になる。

x が答えなのではなく、最終的なレートが答えなので注意。自分はこれに気が付かなくて無駄なデバッグで苦しんでいた。

D. New Year and Fireworks

実は花火の範囲は $300\times300$ 程度しかないので DP ができる。dp[i][d][y][x]:=方向 d の i 段階目の花火が座標 (y,x) に存在 としておく。方向 d は0,1,2,...,7 を 8 近傍時計回りと対応させたもの。状態数は 30x8x300x300=21600000 程度。遷移で 5 回くらいのループが回るが、適当な枝刈りをしておけば通る程度の計算量である。

E. New Year and Old Subsequence

貪欲が難しそうに見えるけどDPは間に合わない。しかしよく見るとDPがマージ可能であるためセグメント木が使える。まずは愚直なDPについて説明する。

文字の削除を無視すれば、nice string を判定するオートマトンは以下のようになる。

2016 以外のノードに 0,1,2,3,4 と番号を付けて、これをDPの状態にする。このとき、dp[i 文字を処理した][状態 j にいる]:=削除する文字数の最小値 として DP できる。

マージ可能、というのはどういうことだろうか。

文字列 S があったとき S.ep[状態 i から開始][状態 j で終了] := 削除する文字数の最小値 というのが計算できる。文字列 S と文字列 T を結合したとき、(S+T).ep[i][j] = min(S.ep[i][k]+T.ep[k][j]) となる。ep がマージ可能なので、これをセグメント木に乗せればいい。

あらゆるコンテストにおいて完全にレートが収束している。