コンテンツにスキップ

ABC483 B - Flip Card Stack

サイト
AtCoder
コンテスト
ABC483
問題
B - Flip Card Stack
難易度
75

11 から NN までの番号が書かれたカードが、上から番号順にすべて表向きで積まれています。「上から KiK_i 枚をひとまとめにして裏返す」という操作を QQ 回行い、最後のカードの順序と表裏を求める問題です(N,Q≤100N, Q \le 100)。

各カードについて、表向きなら番号をそのまま、裏向きなら番号にマイナスを付けて、上から順に出力します。

制約が小さいので、操作をそのままシミュレーションします。

リスト ans にカードを上から順に並べ、表裏を符号で表します。最初はすべて表向きなので、[1, 2, ..., N] で初期化します。

上から kk 枚をひとまとめにして裏返すと、その kk 枚の順序が逆になり、それぞれの表裏も反転します。なので、先頭の kk 要素を逆順に取り出し、符号を反転させればよいです。残りのカードを後ろにつなげると、操作後のリストになります。

例えば、[1, 2, 3, 4, 5] の上から 33 枚を裏返すと、[-3, -2, -1, 4, 5] になります。

各操作で長さ NN のリストを作り直すので、計算量は O(NQ)O(NQ) です。

Python
N, Q = map(int, input().split())
K = list(map(int, input().split()))
ans = list(range(1, N + 1))
for k in K:
ans = [-ans[k - i - 1] for i in range(k)] + ans[k:]
for a in ans:
print(a)

k - i - 1 は k−1,k−2,…,0k - 1, k - 2, \dots, 0 と変化するので、先頭の kk 要素を逆順に取り出せます。取り出した値に - を付けて表裏を反転し、操作の対象外である ans[k:] をつなげています。