Kazun の競プロ記録

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

AtCoder Beginner Contest 257 B問題 1D Pawn

問題

atcoder.jp

提出解答

(マス中心) atcoder.jp

(コマ中心) atcoder.jp

問題の概要

 N 個からなるマスが1列に並んでいる. 左から  i 番目のマスをマス  i と呼ぶことにする.

 K 個のコマがあり, 最初, 左下から  k 番目のコマはマス  A_k にある.

次の操作を  q=1,2, \dots, Q の順に行なった場合,  Q 回の操作を終えた後における各コマがあるマスの番号を答えよ.

  • 左から  L_q 番目のコマについて, 次の2条件を満たす時, そのコマを1つ右のマスに移動させる.
    • 一番右のマス目ではない.
    • 1つ右のマスにコマがない.

制約

  •  1 \leq K \leq N \leq 200
  •  1 \leq A_1 \lt A_2 \lt \dots \lt A_K \leq N
  •  1 \leq Q \leq 1000
  •  1 \leq L_q \leq K

解法

この問題は  N,Q が比較的小さめなので, 愚直なシミュレーションで正解できる. そして, 最初に左から  k 番目だったコマはずっと左から  k 番目であることに注意する.

また, シミュレーションにおいてもマス目を中心に実装する方法と, コマを中心に実装する方法がある. なお, コマ中心に実装する場合,  (K+1) 個目のコマがマス  (N+1) にあると思って実装すると場合分けを減らせる.