久々にRatedなABCで非常に緊張した。良い出来とは言えないけど、なんとか黄色に復帰出来てほっとした。
D - RGB Coloring 2
全部の色を試そうとすると$3^20$必要そうに見える。
が、連結成分ごとに見て、隣が塗られているようなノードを試していけば、二個ずつしか試さなくていいため、全探索しても計算量が減る。
……と、そこまではコンテスト中に気付いていたが、上手い実装が思いつかなかった。
そもそも、全探索を再帰で行う方法がピンと来ていなかったと思う。今まで塗った色の集合を持って、次のノードで何を塗るかを決めれば良い。
「どういう順番に塗るか」は、DFSの順番で良い。そうすれば、同じ連結成分内で二個目以降に見るノードでは、隣のどこかが既に塗られている。
E - Permutation
三十分以上悩んだ上、bit DPを思いつかず、怪しい解法（結局、時間計算量的にはそんなに悪くなかったが、Hack caseはあった）を投げてしまった。
コンテスト中考えたのは、
・何を使うか決めたら、N-1要素の場合に帰着できる
ということ。
N要素の場合に対応するM個の条件たちも、N-1要素の場合へ変わる。ので、条件たちを状態と見て、DP（実装はメモ化再帰）をした。
計算量はよく分かっていなかったが、投げたら通った。
が、ここで何をまとめているか、というと、たとえば、
・2→4→1と使った場合
・1→2→4と使った場合
は同じ状態に遷移することが分かる。
つまり、使う順番は関係なく、集合として同じ要素を消費した場合は同じ状態になる、ということ。
これはbit DPですね。
制約からもまずbit全探索やbit DPを疑うべきなのに気付かなかった（bit全探索は考えたけどbit DPは考えなかった）のはひどい。
でも、After_contestで落ちたとはいえ、ACできて救われた。
F - Graph Smoothing
これはすんなり解けた。
「平均を取る」という操作を二回行って平均を取るのは、いかにも、「平均を取る」という操作の平均を取る、というのを二回繰り返したものと同じになりそう。
それで良いと分かったら、「一回操作して平均を取る」というのは行列で表せるので、行列累乗すればOK。
0 件のコメント:
コメントを投稿