Kazun の競プロ記録

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

AtCoder Beginner Contest 289 B問題レ

AtCoder ABC289 ABC 200 pts B問題

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

漢文のある行 (競技プログラミング的には列) には $N$ 個の感じが書かれている. また, その行には $M$ 個のレ点があり, 上から $i$ 番目のレ点は $A_i$ 文字目と $(A_i+1)$ 文字目の間に打たれている.

この漢文を読む場合, どのような順番で読むことになるか?

制約

$1 \leq N \leq 100$
$0 \leq M \leq N-1$
$1 \leq A_1 \lt A_2 \lt \dots \lt A_M \leq N-1$

解法

次のようにすることで正解することができる.

である限り以下を繰り返す.
- $j \gets i$
- $j=N$ または ( $j$ 文字目と $(j+1)$ 文字目の間にレ点が打たれていない) 場合, $j$ 文字目から $i$ 文字目を (下から上に) 読む. そして, 繰り返しから抜ける.
- そうでない場合, $j \gets j+1$ として繰り返す.

これにより, 計算量 $O(N)$ 時間で読むことができる.