AtCoder Beginner Contest 199 反省

実は先週の最強コン、それに続くARCについての記事を書いていない。忙しかったので仕方がない。軽く先週のおさらいをしておくと、「最強コンで黄パフォ黄色昇格→ARCで水パフォで-50くらいして青入り」

結果を鑑みて

1500(1) 66:52

298位となった。普段のABCでこの順位だと冷えかねないが、どうやら今日は参加人数が多かったようだ。今回のセットは典型力と実装力を問う問題が多かった。実生活の心配事を引きずって考察が鈍る傾向があるが、今回はウォームアップと睡眠（昼寝もあわせて13時間寝てる......）の甲斐あって冷えずには済んだ。

A - Square Inequality

どこかで見たような問題文だが、整数値の判定なのでふつうにやればよい。サンプル一通り試しても1分かからなかった。

B - Intersection

これも見てすぐ解法はわかった。

軽実装なので解いてすぐ順位表を見たが、特に危ない順位にはなっていなかった。

C - IPFL

問題文を読んで、これもすぐにわかったがflipが奇数回行われたときと偶数回行われたときで場合わけする必要があることが予期されて、少し実装したくなさがあった。そういうわけで少し実装が楽になる気付きポイントがないか少し考えたが、何も思いつかないので実装し始めた。実装していくと、flip奇数回のときにA, Bの値を書き換えることにしておけばそれ以降の処理は共通なので実装は案外重くならなかった。

最近はシンプルな実装ができるようになっている一方で、泥臭い実装を要することが予期されるとすぐにやる気がなくなることが増えた。よくないなあと思うが、競技との向き合い方自体に問題がある気がしている。

D - RGB Coloring 2

制約を見て、計算量の評価がすぐにできた。雑にやれば状態数が3^Nあるが、連結成分ごとに一頂点決め打てば2^Nに落ちる。

ところが、これを実装に落とすのに難儀してしまった。最初は色を配分した表を持ちながらDFSしていく方針だったが、これは探索中の頂点が連結成分の末端に達した時にうまく他に遷移できないこと、木ではないのでボトムアップな集計ができないこと（木は二点間のパスが1個だけなので二点間の情報伝播に矛盾が生じないが、閉路があると簡単ではない）から正しく実装できずに時間だけが過ぎ去ってしまった。

順位表を見て、DとEが50人ほど解けている状態だったので仕切り直す意味を込めてEを見に行った。このときにDが200人くらいに解かれていたら冷静な判断ができなくなっていたかもしれない。

Eを解いて戻ってくると、すでに150人程度に解かれていた。最初の方針で1回組み切って出して1ペナした。その後、やや実装は重いが連結成分ごとに頂点の色を決め打ちして正しく塗れているかをチェックする方針にシフトした。最初に取った方針と似てはいるが、DFSの集計に関する弱点がこちらの方針にはないので何とかこれを解くことができた。

最近のD問題にしてはかなり実装が難しい問題だったと思う。

E - Permutation

制約を見て、こんなものはbitDPしかないなと思った。実際、数列を端から順に構築していく場合に保持すべき状態数は2^Nずつで抑えることができる。あとは素直に組めばいいのだが、全状態でM個の制約全部を見ているとO(N^2M2^N)などという計算量（この計算量回文じゃん！）になってしまい、破滅の予感がした。そういうわけで枝刈りをして祈りながら提出をした。この枝刈りに少し時間を取られたが、最悪O((Mcomb(N,N/2)+2^N)N^2)くらいにはなっていたため通すことができた。一応、最悪ケースでコードテストもしておいた。

これを解いた後に気分新たにDを見に行った。

F - Graph Smoothing

難しい。これは本番中に解けなかった。なぜこんなに解かれているのか。

最初はDFSで考えていた。パスをうまく管理できればあとは組み合わせ計算でなんとかなるように見えたため。これは難航したので、別のアイデアがないか少し考えた。

次に出たアイデアが隣接行列のようなものを持っての行列累乗で、思いつきだったが問題の条件にフィットしており、大いに興味をそそられた。そこから先、行列の初期値をあわせるためにガチャガチャと値を変えていたのだが、ついにACできなかった。

行列累乗で考える場合は、「どの部分が何を表しているか」「次状態に遷移する際に、どこから寄与が生じていてどのような遷移式になるか」を意識して特に遷移部分を明確にしなくてはならない。今回は雰囲気で値をガチャガチャやっていてこの二点を疎かにしていたのが敗因となったように思う。

ところで、さっきまでこの問題Graph Somethingだと思っていた。

総括

Dで詰まってEに行った時のムーブは良かったが、もう少し早くDを後回しにしても良かった。また、最近は（といっても今回のと直近のcodeforcesだが）解法の正しい道筋が見えずに嘘解法を出してペナると途端に解法と問題の全体像が見えることが多くなってきた。できればWAとかになる前に気付きを得たいのだが、コンテスト中の冷静さが足りていないのだろうか。