ARC007 B - 迷子のCDケース

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import numpy as np
from numpy import linalg as LA

# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()

    cd = 0
    cd_position = list(range(0, N+1))
    cd_position[cd] = -1
    for i in range(M):
        n = ii()
        if cd_position[n] == -1:
            continue
        cd_position[cd] = cd_position[n]
        cd_position[n] = -1
        cd = n

    for i in range(1, N+1):
        print(cd_position.index(i))


if __name__ == '__main__':
    main()

考え方

基本的には問題の指示通り、
「新しくCDを取り出す」->「既に出ているCDを取り出したCDが存在していた位置に格納する」を繰り返します。

この時、保持しておくデータの形式は、
indexの番号をCDの番号として、値を格納されている位置とした配列を用いました。
つまり、index = 0に3が入っている場合には0番目のCDはケース3に格納されていると考えます。

保持するデータの形式さえ決まれば、計算量は多くないため、
指示通りの操作を愚直にシミュレートするだけです。
ただし、既に外に出ているCDを連続して聞く場合がある点に注意が必要です。
この場合には、CDの移動は行われません。