Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Regular Contest 152 A問題 Seat Occupation

AtCoder ARC152 ARC A問題 400 pts

問題

提出解答

問題の概要

$L$ 個の椅子が横一列にならんでいる. この席に $N$ 組が順番に座っていく. なお, 各組は $1$ 人組か, $2$ 人組で, $i$ 番目の組は $a_i$ 人組である. そして, $L=a_1+\dots+a_N$ である.

この $N$ 組は $i=1,2, \dots, N$ の順に, $i$ 番目の組は次のようにして椅子に座っていく.

連続する $a_i$ 個の空席が存在する場合, そのような場所からランダムに選び, その $a_i$ 席を座る. 存在しない場合, 座らずに帰る.

このとき, 次のことが確実にいえるか?

どの $N$ 組も帰らずに座ることが出来る.

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq a_i \leq 2$
$L=a_1+\dots+a_N$

解法

問題を観察すると, 次のことがわかる.

帰るような組は必ず2人組である.
ある2人組が帰ったら, それ以降の2人組も帰る.

よって, 次のようにすればよい.

2人組が存在しない場合, 必ず可能である.
2人組が存在する場合, 最後に訪れる2人組が確実に座れるかどうかを判定すれば良い.

2人組が存在するとする. 最後に訪れる2人組が $k$ 番目であるとする. このときの $k$ 番目の組を座らせないような最悪のケースは次のような場合である.

左から2番目の席から $a_1$ 人座らせる.
1席空けて $a_2$ 人座らせる.
$\vdots$
1席空けて $a_{k-1}$ 人座らせる.

このとき, 右端に残っている席の数は $\displaystyle L-\sum_{i=1}^{k-1} (a_i+1)$ である. これが $2$ 以上であることが確実に可能であるための必要十分条件である.

なお, $\displaystyle L-\sum_{i=1}^{k-1} (a_i+1) \geq 2$ の両辺に $\displaystyle \sum_{i=k}^N (a_i+1)=3+2(N-k)$ を引いて, 変形すると,

$k \leq \left \lfloor \dfrac{N+1}{2} \right \rfloor=\left \lceil \dfrac{N}{2} \right \rceil$

となる. これは, $A$ の末尾の $\left \lfloor \dfrac{N}{2} \right \rfloor$ 項が $1$ と等しいということを意味している. これは $a_i=2$ となる $i$ が存在しない場合も含んでいる.