AGC032 A - Limited Insertion

備忘録

問題

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 = ii()
    B = il()

    ret = []
    for i in range(N):
        t = -1
        for j in range(len(B)):
            if B[j] == j+1:
                t = j + 1
        if t == -1:
            print(-1)
            exit()
        ret.append(t)
        B.pop(t-1)
    ret.reverse()
    print(*ret, sep="\n")


if __name__ == '__main__':
    main()

考え方

空の数列aに対して、指示された動作通り数字を追加することで数列bとなります。
これを逆にとらえると、数列bから数字を取り出し続けると、数列a（空）になるとも考えることができます。
どのように数列bから数字を取り出すか考えると、
左から順にj番目かつ値がjとなっている数字のうち、最も右にある数字を取り出すことがベストです。
（そんな気がするだけで証明はできません）

例えば、b = [1, 2, 1]のとき、
j番目かつ値がjの数字で最も右に存在するのは2です。
そのため、2を取り出すとb = [1, 1]となります。
あとは1 -> 1と取り出すことで数列bは空となります。

取り出すことが出来る順番の逆が入れる順番となるので、
取り出した順を逆順としたものが回答となります。
取り出すことが出来ない場合には、作ることができない数列（-1を出力）です。