年も変わったし、コンテストへの参加記録を書いていきます！
……といっても、コンテスト後、既に一日経っている。いつまで続けられるんでしょうか。
D - Choose Me
何もしないと全員が青木氏に投票する。
高橋氏が演説を行うと票がどれだけ動くか、と考えると、2*A+Bでソートすれば良いと分かる。
E - Through Path
最初、全方位木DPが必要だと思い一旦飛ばした。
Fを解いた後、やりたくないし書き終える自信がないけど、全方位木DPを書くかー、と書き始めたら、通常の木DPでいけることに気付いた。
自然に書けば全方位木DP、「全体にxを足して、逆側からxずつ引く」ことを思いつけば普通の木DPでいける。
とはいえ、全方位木DPでも書けるべき問題ですよね。
F - Close Group
Nが小さいのでbit系を色々考えたが、しばらく思いつかず苦労した。
「まず、完全グラフになっているものを列挙」を思いつけば、$4^N$のDPにはたどりつける。
それが実は$3^N$になるというのは、この問題のsnukeさんの解説動画で覚えていた。難しい問題を解説ACしておいたのが役に立った！ と嬉しかったのですが、Educational DP Contestのこの問題もそうだったのですね。解いたはずなのに全く覚えていなかった……。
0 件のコメント:
コメントを投稿