Kazun の競プロ記録

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

AtCoder Beginner Contest 256 B問題 Batters

AtCoder ABC ABC256 B問題 200 pts

問題

提出解答

解法1 atcoder.jp

解法2 atcoder.jp

問題の概要

マス $0$ , マス $1$ , マス $2$ , マス $3$ からなるマス目があり, 最初, このマス目の上には何もない.

$P=0$ とする. 次の操作を $i=1,2, \dots, N$ の順に行なったときの最終的な $P$ を求めよ.

マス $0$ にコマを $1$ つ置く.
全てのコマをマス $x$ にある場合, マス $x+A_i$ に移動させる. ただし, $x+A_i \geq 4$ ならば, そのコマは取り除き, 代わりに $P$ に $1$ を加算する.

制約

$1 \leq N \leq 100$
$1 \leq A_i \leq 4$

解法1 (シミュレーション)

この問題は愚直なシミュレーションで正解できる. ただし, コマを移動させる際, 1回の $i$ で複数回移動させることにないように注意すること.

解法2 (累積和)

マス $4$ 以降もあると考える. このとき, $i$ 番目においたコマが最終的にマス $4$ 以降に置かれるための必要十分条件は

$\sum_{j=1}^i A\_j \geq 4$

である. これは愚直に $O(N^2)$ 時間で計上できる. また, 累積和を利用することによって $O(N)$ でも計上できる.