Eまで五完。Rustで解いていたら、Dまででかなりの時間がかかってしまい、EからPyPyに。が、Fが解けずに終了。Fは考察から間違っていた。
F. Multi-Colored Segments
一応自力ACした。
[l, r, c]についてlでソートしたとき、最も大きいrと、それとは色が違うものの中で最も大きいrを管理する。
……というようなことを二回（lについて左から、rについて右から）で解けると思ったのだけど、WAが出て困った。
結局、l, rそれぞれについて、大きい順・小さい順でソートして、計四回似たようなことをしたらACしたが、それで良いのかよく理解していない。
G. Kirill and Company
解説ACしたが、解説を理解するのにも、実装にも苦労した。
まず、
・ある車を持っている友人のがいる頂点を使ったとき、どんな車のない友達の集合を運べるか？ という候補を知りたい。
これは、BFSしながらDPして調べられる。
DP配列としてはベキ集合を持つ。つまり、問題文の図にある頂点5なら、{{0, 1}, {0, 2}}を持つようにする。（0, 1, 2は車のない人のindex。たとえば1は2に住んでいる）
BFSして、車のない人の家を通るたび、今までのDPの各集合にその人のindexを追加していく。
なお、実装上は、{{0, 1}, {0, 2}}でなく、{3=(1<<0)|(1<<1), 5=(1<<0)|(1<<2)}を持った方が良い。
これをした上で、
・車を持っていく人を順に見て、どんな集合に対処できるか？
を見ていくDPをする。
公式解説にあるように、これはbit DPというよりはナップザックDPに近い。
解説を読んだ際、前者を処理した後どんなDPをすれば良いか分からず理解に時間がかかってしまった。自然なDPなのだが、bit DPだろう、と思っていると盲点になりやすいかもしれない。
0 件のコメント:
コメントを投稿