競技プログラミング用 知識集積所
ABC440C - Striped Horse
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
愚直にやると、もちろんTLE。
ということで工夫を考える。
ということで工夫を考える。
問題の色塗りルール的に、位置の差が2Wの倍数であるところは、必ず同じ色になる。
ということは、コストの加算もまとめて扱ってよい。
ということで、まずは位置そのものを2Wで割った値ごとにコストを合計して、長さ2Wのvectorにしておく。
ということは、コストの加算もまとめて扱ってよい。
ということで、まずは位置そのものを2Wで割った値ごとにコストを合計して、長さ2Wのvectorにしておく。
あとはここから連続W個の区間和の最小値を求めればいい。
区間の長さが一定なのでsliding window法を使うことになる。
余り2W-1と余り0が循環で繋がっているところは、データを2周分用意した長さ4Wのvectorに作り直すことで対応する。
（厳密には、W-1個をコピーした3W-1個以上あればよい）
区間の長さが一定なのでsliding window法を使うことになる。
余り2W-1と余り0が循環で繋がっているところは、データを2周分用意した長さ4Wのvectorに作り直すことで対応する。
（厳密には、W-1個をコピーした3W-1個以上あればよい）
