Cまで三完。
コンテスト後のツイート
AtCoder Regular Contest 143 Cまで三完。
— titia (@titia_til) June 26, 2022
A maxと他の二つの和の比較かな、と思いつつ実験した。
B ダメな数は一つなので、その数を全探索
C https://t.co/u6MIHD4z3Gの応用。解説を読んだ。（実験コードも書いた）
D サイクルをいっぱい作りたい。循環費用流とか考えていたが違ったみたい。
C - Piles of Pebbles
コンテスト中は、（まずちょっと考えて一度飛ばそうかとDに行き、分からず戻った後）、
・再帰で愚直解を書く
・書いてみたら、X=Y=1のときは見たことある結果になる
・この問題を思い出し、解説を読む。
・大体同じように解けそう、と分かり、(愚直解と一致するか試した後)AC
という流れでした。
類題を覚えていたのは、当時嘘解法でACしたためです。嘘解法でACすると、記憶に残りやすいので良いかも？
D - Bridges
解法ツイートを見てAC。
コンテスト中、最初は（問題文通り）2N個の頂点があるグラフを考えていたけれど、Cを解いて戻った後は、N個の頂点のグラフで考察すべきでは？ とは思い直した。N頂点のグラフで、多くの頂点がサイクルに巻き込まれるような辺の貼り方をすれば良さそう……と思うも、最小循環費用流？ とか考えたりして、やり方が分からなくなってしまった。
落ち着いて見れば、これはDFSする（DFS木を考える）だけで良い。
こういったDFS系の問題は落とすことが多いので注意しようと思っていたのに、また解けなかったというのは悲しい。最初、2N頂点のグラフを考えていたために引きずられた、という部分はあるが、これは思いつきたかった。
E - Reversi
解説放送を見てAC。
葉について考察し、それをもとに木DPをすればOK。
葉については考えたけど、それを元に有効辺を付けようとは考えなかった。石を取り除けるかどうかの判定をどうやるんだろう、と考えるだけでなく、辞書順最小の裏返し方をどう見つけるんだろう、と考えたなら有効辺にするのは結構自然かもしれない。
まず判定をどうにかしよう、と思ってしまうけど、（この問題に関しては）辞書順のことも考えて臨むべきだったのかな。
0 件のコメント:
コメントを投稿