250 ColorfulRabbits
方針
サンプル見て考える。返答が違うもの同士は絶対に違うグループ。返答が同じなら、同じグループにしてよい。つまり、返答がnなら、そのグループのメンバはn+1。もし、同じ返答をしたウサギが n+1以上いるなら、グループを分割しないといけない。
実装
書くだけ。
書いた後は、いつものように、オーバーフロー・アンダーフロー・境界のチェックなどをした上で submit。DIV1 250 にしては簡単すぎると思い、慎重に。どうせ 550 は解けないんだから、これを外すわけにはいかないのだ。
550 WhiteSpaceEditing
方針
いかにも DP っぽいが、どうすればいいのか分からない。状態をすべて naive に持つのは無理だ。
NL する回数は 行数 - 1 で一定なので、それを手がかりにできそう。結果から {NL} に戻すように考えたらどうだろう。どの行とどの行が共通祖先から来たのか、系統樹を作るような感じで。その組み合わせは、値が近い隣接ペアを選べば……? いや、10 10 10 2 10 10 10 みたいなのは、10 を作って分裂させておいてから 2 を作るんだよなぁ。←その必要はなかった(後述)
いずれにせよ、単純に「1からk番目までが完成しているときに、k+1番目を」みたいなDPでは無理そう。分からん。
実装
直前 10分くらいで、状態遷移をグラフにして Dijkstra とか嘘解法を書き始めたが、それも間に合わず。
Challenge Phase
250は落とせるとは思えないので、550に着目。やっぱりみんな DP してるが、かなり複雑で解読できない。みるみるうちに、DP組が challenge されていく。そんな中、DPではない異様に単純な解答がいくつか残った。なんだこれは? 探索なしで行けるとは思えないんだが…… 撃沈ケースを探すが、落とせる自信がない。自分の点も悪いので、ヘタに手を出すのはやめよう。
結果
250は通った。しかしレートは 1269→1240 と低下。
考察
DIV1下限付近のレートでも、解くのが遅いだけで下がっちゃうんだ。1問解ければ下がらないと思ってた。残念。
250は慎重に行きすぎて時間をかなり無駄にした。ただ、今の実力では、レート云々よりもまずは正解することを心がけたい。
550は、謎のnon-DP解答が通ってた。実は「10 10 10 2 10 10 10 みたいなのは、10 を作って分裂させておいてから 2 を作る」必要はなく、「2 2 2」を「10 2 10」にしてから分裂させても同じ手数だった。なぜならば、NL する回数は同じ。左側の10を作るのに必要な手数を同じ。右側で2を10にするのも、10を2に減らすのも同じ手数。ゆえに、手数は同じ。うまいなぁ。
一方、着実に DP してる人の解法はというと、dp[左端][右端][タネ] で、「あるタネから、ある範囲を完成させるのに必要な手数」としていた。状態数 50 ** 3。状態遷移は、長い領域→左側+真ん中1つ+右端 と分ける。これでいい理由は、論理としては分かったが、感覚的にしっくり来ない。要検討。
