第2回 ドワンゴからの挑戦状 予選 B - 積み鉛筆

備忘録

問題

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()
    K = il()
    ret = [K[0]]

    for i in range(1, N-1):
        if K[i-1] <= K[i]:
            ret.append(K[i-1])
        else:
            ret.append(K[i])
    ret.append(K[-1])
    print(*ret)


if __name__ == '__main__':
    main()

考え方

土台の鉛筆の長さは、上に乗っている鉛筆の長さから決まります。
つまり、土台の先頭と末尾は上に接している鉛筆が1本しかないことから、
上部の鉛筆の先頭が土台の先頭、上部の鉛筆の末尾が土台の末尾となります。

次に土台の先頭と末尾以外について考えます。
上部の鉛筆の長さは、接している土台の鉛筆のうち長い方の長さとなります。
ただし、既に先頭と末尾が決まっていることから、
接する鉛筆のうち片方が確定している状態にあるため、一意に土台を決めることが出来ます。
土台となる鉛筆は条件から上部に接する鉛筆の小さいほうが土台として使用することが出来ます。