Eまで五完。時間ギリギリで通ったのは嬉しい！
F. Christmas Game
解説AC。
公式解説が分かりやすかった。
こういう問題だとNIMに帰着するのは定石とはいえ、なかなか面白かった。
が、解説では実装がよく分からず、全方位木DPだよね？ と思ったらそう書いているツイートを見つけた。
今回は逆元がある全方位木DPということで、実装はそれほど大変ではなかった。
が、全方位木DPで得た配列の添え字のどこからどこまでを使うかで混乱、結局時間がかかってしまった。
上手く書けたら全方位木DPのライブラリにしようと思って書き始めたのだけど、（まあまあ上手く書けた方かとは思うものの）結局遷移式とか添え字とかを考えるところが大変だからライブラリ化してもなぁ、という気持ちになったのでライブラリ化は見送りかなぁ。
全方位木DPは二回DFSをやることになるわけだけど、一回目のDFSを書いたら二回目は書かなくていいようにライブラリ化したい。
今回みたいに、DP配列の中身が配列の場合にも対応できるようにライブラリ化できるはずだよね。また今度やります。（先送りして良いのだろうか）
0 件のコメント:
コメントを投稿