原案：admin

塗るマスの決め方は要するに「『 \(W\) マス連続して黒く塗り、続けて \(W\) マス連続して白いままにする』の \(2W\) 周期でマスを塗る」という意味です。

全ての \(i\) でマス \(i\) とマス \(i+2W\) を塗るかどうかは一致します。よって予めそのようなマスをまとめ、必要ならコスト \(0\) のマスを補うことで問題は次のように変換できます：
\(2W\) 個のマスが円環上に並んでおり、各マスにはコストが定まっている。連続する \(W\) マスを塗るときの、塗るマスのコストの和の最小値は？

以下この変換後の問題を考えます。

まず適当なマスから連続する \(W\) マスを塗る際のコストを求めます。その後、尺取法のように「片方の端を1マス伸ばし、もう片方の端を1マス縮める」とすることで、塗る区間を1マスずつずらしたもののコストを \(O(1)\) で計算できます。これを繰り返すことにより、全ての塗り方のコストを \(O(W)\) 時間で確かめることができます。

問題の変換にかかる時間も合わせて、全体で \(O(N+W)\) 時間でこの問題を解くことができました。