ABC483 B - Flip Card Stack
- サイト
- AtCoder
- コンテスト
- ABC483
- 問題
- B - Flip Card Stack
- 難易度
- 75
から までの番号が書かれたカードが、上から番号順にすべて表向きで積まれています。「上から 枚をひとまとめにして裏返す」という操作を 回行い、最後のカードの順序と表裏を求める問題です()。
各カードについて、表向きなら番号をそのまま、裏向きなら番号にマイナスを付けて、上から順に出力します。
制約が小さいので、操作をそのままシミュレーションします。
リスト ans にカードを上から順に並べ、表裏を符号で表します。最初はすべて表向きなので、[1, 2, ..., N] で初期化します。
上から 枚をひとまとめにして裏返すと、その 枚の順序が逆になり、それぞれの表裏も反転します。なので、先頭の 要素を逆順に取り出し、符号を反転させればよいです。残りのカードを後ろにつなげると、操作後のリストになります。
例えば、[1, 2, 3, 4, 5] の上から 枚を裏返すと、[-3, -2, -1, 4, 5] になります。
各操作で長さ のリストを作り直すので、計算量は です。
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 は と変化するので、先頭の 要素を逆順に取り出せます。取り出した値に - を付けて表裏を反転し、操作の対象外である ans[k:] をつなげています。