Quiz

f:id:peroon:20200415071736p:plain

AC code

dp[i][j][k]
i : まで見て (N)
j : その点を選んだ/選んでいない (0,1)
k : 大ジャンプ回数 (0,1,2)
として配るDP

いいえ、例えばN=4で「○✕✕○」も条件を満たします

いいえ、N=7で「○✕✕○✕✕○」も条件を満たします

f:id:peroon:20200415072240p:plain

dp[i][j]
i : まで見て
j : で最後に選んだ場所の添字

とすると表を埋めるだけでもO(N²)でオーバーです。ただ、今回は「ほぼ飛び飛び」という制限があるので、前回の状態と今回の状態が近い、画像のような状態であり、表全てを埋める必要がないためO(N)に収まると理解しました

{1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1}