更新してなかったのを思い出したので
8問abcは再走するには後半が重すぎるので、この企画(?)の最終記事になります。
■206F - Interval Game 2
区間dp+Grundy数
[0,100)から初めて取れる区間[l,r)を取る
[0l)と[r,100)に分かれる
Grundy数なのでxorを取ればいい
■207F - Tree Patrolling
２乗の木dp
根っこからdfsするのは当然として
状態を１：誰にも警備されていない、２：他人が警備している、３：自分が警備している
と定める。２と３は３のほうが強い条件なのは明らか。
としてマージする。
■208F
ラグランジュ補間
めちゃめちゃ高校数学をするとk+m次式なのがわかるので
序盤のk+m+1項を愚直に計算してライブラリに打ち込む
■209F - Tree Patrolling
コストは隣接する要素の伐採順で決まる
h[i] < h[i+1]ならi+1を
h[i] > h[i+1]ならiを
同じならどちらでもいい。
dp[i][j]:=i番目まで最低になるような並びで、i番目の木をj番目に切った通り数とする
O(n^3)になりそうだが加える区間は連続する範囲なので累積和が出来る。
いわゆる挿入dp
■210F
2-SAT
まだ良くわかってない。
■211F
実装が面倒ですがセグ木に乗せるだけです。
