ARC152 A - Seat Occupation (400)
$ n = 1なら1通りしかないので明らかにOK
ランダムな場合を全部考える必要は無く最悪ケースで達成できるかだけ考えれば良い
可能なら隣と一つ開けて座るケースが最悪
左から一つ空けて座っていくと考える
残りの右の連続部分の長さと1つ空いている個数を持っておく
順に以下のように考える
二人組の場合
最後の連続部分が長さ2無ければ不可能
可能なら1つ空いている個数を1増やし、連続部分の長さを3減らす
一人組の場合
最後の連続部分が長さ2以上なら一つ開けて座る
1つ空いている個数を1増やし、連続部分の長さを2減らす
ちょうど1だったらそこに入る
それ以外なら今まで飛ばしていたどこかに入る
それぞれの人で定数時間で行動を求められるので$ \mathcal{O}(N)