yukicoder - No.1313 N言っちゃダメゲーム (4)

問題リンク

解説

dp _ {i} := i から始めた時に勝てるかどうか

とすると、

dp _ {i} = 1 \ \ \ (\exists _ {j} \ dp _ {j} = 0 \land s _ j = \mathrm{o} \ (i + 1 \leq j \leq i + K))

dp _ {i} = 0 \ \ \ ( それ以外 )

であるので

dp _ {j} = 0 \land s _ j = \mathrm{o}

となる j をqueueなどで管理することで、 O(N) で解けました

提出コード

yukicoder.me