Kazun の競プロ記録

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

AtCoder Beginner Contest 267 B問題 Split?

AtCoder ABC267 ABC B問題 200 pts

問題

提出解答

問題の概要

ボウリングのあるフレームにおける第1投終了後の $10$ 本のピンの状況が $S$ で与えられる. $i$ 番ピンが残っているならば, $S$ の $i$ 文字目は ${\tt 1}$ , 倒れていれば $S$ の $i$ 文字目は ${\tt 0}$ である. これはスプリットか (スプリットの定義は問題文参照)?

制約

$S$ は ${\tt 0,1}$ からなる長さ $10$ の文字列.

解法

まず, $S_1={\tt 1}$ ならば, 明らかにスプリットではない.

$S_1={\tt 0}$ とする. このとき, $7$ 個の列について, 各列に立っているピンの数を記録する. その後, スプリットであるために存在すべき左の列, 右の列及び間の列を全探索し, ピンの有無をみることによって判定すれば良い. なお, 3個の列の選び方の候補は $\binom{7}{3}=35$ 通りであり, 十分小さい.