Kazun の競プロ記録

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

AtCoder Beginner Contest 286 A問題 Range Swap

AtCoder ABC286 ABC A問題 100 pts

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

問題

提出解答

(解法 1)

(解法 2)

問題の概要

長さ $N$ の整数列 $A=(A_1, \dots, A_N)$ が与えられる. $A$ の第 $P$ 項から第 $Q$ 項と第 $R$ 項から第 $S$ 項を入れ替えた整数列を $B$ とする.

$B$ を求めよ.

制約

$1 \leq N \leq 100$
$1 \leq A_i \leq 100$
$1 \leq P \leq Q \lt R \leq S \leq N$
$Q-P=R-S$

解法1

$B$ の第 $i$ 項 $B_i$ は次のようにして求められる.

$B_i=\begin{cases} A_{R+(i-P)} & (P \leq i \leq Q) \\ A_{P+(i-R)} & (R \leq i \leq S) \\ A_i & ({\rm otherwise}) \end{cases}$

解法2

解法1 のように, $B_i$ を具体的に求めなくても, $A$ に対して以下のようなアルゴリズムを実行し, 終了後の $A$ が求めるべき $B$ である.

に対して以下を実行する.
- $A_{P+k}$ と $A_{R+k}$ を入れ替える.