Kazun の競プロ記録

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

AtCoder Beginner Contest 301 B問題 Fill the Gaps

AtCoder ABC ABC301 B問題 200 pts

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

問題

提出解答

問題の概要

長さ $N$ の整数列 $A=(A_1, \dots, A_N)$ がある. ここで, 隣り合う項は全て異なることが証明できる.

このとき, $A$ に対して, 以下の操作を行う.

$A$ の隣り合う項の差の絶対値が $1$ である場合は操作を終了する.
において, 隣り合う項の差の絶対値がでない最初の箇所をとする.
- $A_i \lt A_{i+1}$ ならば, $A_i, A_{i+1}$ の間に $A_i+1, A_i+2, \dots, A_{i+1}-1$ を挿入する.
- $A_i \gt A_{i+1}$ ならば, $A_i, A_{i+1}$ の間に $A_i-1, A_i-2, \dots, A_{i+1}+1$ を挿入する.

操作後の $A$ を求めよ.

制約

$1 \leq N \leq 100$ .
$1 \leq A_i \leq 100$ .
$A_i \neq A_{i+1}$ .

解法

次のようにして操作後の $A$ を求めることができる.

$B$ を空列とする.
$B$ に $A_1$ を挿入する.
に対して, 以下を行う.
- $A_i \lt A_{i+1}$ ならば, $B$ の末尾に $(A_i+1, A_i+2, \dots, A_{i+1}-1)$ を挿入する.
- $A_i \gt A_{i+1}$ ならば, $B$ の末尾に $(A_i-1, A_i-2, \dots, A_{i+1}+1)$ を挿入する.
$B$ が答え.