ABC455Dを解いた【双方向リスト】

筆者はレート800前後の茶～緑コーダ

ABC455のD問題を解いていく

実装コード

カードの上下の関係性を双方向リストとしてc,pの入力で付け替える

解答はi番目の山の土台のカードN+iを用意して、該当する山から辿ればOK

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

def main():
    N, Q = rLI()
    
    upper = [ -1 for _ in range(N)] + [ i for i in range(N)]
    lower = [N+i for i in range(N)] + [-1 for _ in range(N)]
    
    for _ in range(Q):
        c, p = rLI1()
        d = lower[c]
        lower[c] = p
        upper[p] = c
        upper[d] = -1
        
    ans = [0]*N
    for i in range(N):
        j = N+i
        while upper[j] != -1:
            ans[i] += 1
            j = upper[j]
        
    print(*ans)
    
if __name__ == '__main__':
    main()

感想

カードの山の配置だけ考えていたが
上下の関係性に注目する発想は学びになった