Cまで三完。そこそこ速かったためレートは下がらなかったものの、時間があってもDやEが解けておらず、気持ちは良くない。
D - Odd Degree
公式解説放送を見てAC。
まとめると、
・全域木に着目する。
・木の場合は、頂点の個数が同じなら答えは同じで、二項係数で求められる。
・木にさらに辺を付け加えた場合、一本ごとに全て二倍の個数になる。
・連結成分ごとに求めたものをマージしても計算量は二乗で収まる。
といったあたりがポイントだったと思う。
コンテスト中は、全域木を取ったときに木DPできそうだけど、上手くいかない……と悩んでいた。
逆に言えば、一つ目のポイントには気付いていて、三つ目のポイントにも（理由は説明できなかったけど）気付いていた。
あとは、二つ目のポイントに気付ければ答えにたどりつけたと思うのだが、近いことは考えたものの、上手くいかない気がしてしまった。
だが、これは、ちゃんと実験していれば気付けたのでは？
手で実験するのではあまり多くのグラフを試しにくいが、愚直コードを書いていれば、実験するのはそう難しくなかったはず。
愚直コードといって思いつくのは、辺の数Mに対して$2^M$通り試すコードで、確かにちょっと面倒くさい。とはいえ、書くのに五分もかからなかったのでは？ と思う。
ちょっと詰まった時点でこれをしていれば展開が変わったかもしれない。「愚直コードを書いてみる」というのは、今までしていなかったわけではないし、この問題でもしようか迷った時間はあった（が、手で考察が進む気がして避けてしまった）。
だけど、今までよりもっと早い段階で、またもっと色々な問題で試すべきなのかもしれない。
E - LEQ and NEQ
公式解説放送を見てAC。
包除原理は確かに考えるかもしれない。
（私は包除原理に慣れていないせいかピンと来なかったけど）そうすると、三乗のDP（けんちょんさんの解説の一番始めのDP）は思いつくと思う。
それを高速化できる、というのは、解説放送を聞けば確かに、となる。
……が、それを実際に実装しようとしたら何をすれば良いか分からなくなり戸惑った。最終的には、具体例と合わせながらやれば書けたけども。
包除原理を使う問題は、実装でも混乱しがちなのが大変だと思う。あまりさくっと書ける気がしないのだけど、これは包除原理が頭の中で整理できていないからなのだろうか……。
0 件のコメント:
コメントを投稿