Kazun の競プロ記録

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

AtCoder Beginner Contest 278 A問題 Shift

AtCoder ABC278 ABC A問題 100 pts

問題

atcoder.jp

提出解答

(解法 1) atcoder.jp

(解法 2) atcoder.jp

(解法 3) atcoder.jp

(解法 4) atcoder.jp

問題の概要

整数列 A が与えられる. 次の操作を K 回行った後に得られる整数列を求めよ.

  • A の先頭を削除し, A の末尾に 0 を加える.

制約

  • 1 \leq N \leq 100
  • 1 \leq K \leq 100
  • 1 \leq A_i \leq 100

解法

1回の操作は次と同等である.

  • i=1,2, \dots, N-1 の順に A_i \gets A_{i+1} とする. その後, A_N \gets 0 とする.

これは i に関する for 文で実装できる. これを K 回回す for 文で繰り返すことによって, 正解の整数列を求めることが出来る (解法 1).

なお, Python の場合, スライスとリストの連結を利用することによって, A に対する1回の操作後の整数列は {\tt A[1:]+[0]} で表すことができる. これを K 回 for 文で回せば良い (解法 2).

実は, for 文を回さなくても, N,K の大小関係による場合分けによって, 次のように求めることが出来る (解法 3).

\begin{cases} (A_{K+1}, A_{K+2}, \dots, A_N, \underbrace{0, \dots, 0}_{K} ) & (K \lt N) \\ (\underbrace{0, 0, \dots, 0, 0}_{N} ) & (K \geq N) \end{cases}

そして, (N+1) 回目以降では操作前後ではその整数列は変わらない. よって, K を \min(N,K) に置き換えることによって, (解法 3) における場合分けをなくすことが出来る.