ABC136 C - Build Stairs

Python3 AtCoder

備忘録

問題

atcoder.jp

回答

import sys
import os
import itertools


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

    N = int(sys.stdin.readline().rstrip())
    H = list(map(int, sys.stdin.readline().split()))

    ret = 'Yes'
    tmp = -1
    for n in range(N):
        if tmp > H[n]:
            if tmp != H[n] + 1:
                ret = 'No'
            else:
                tmp = H[n] + 1
        else:
            tmp = H[n]

    print(ret)


if __name__ == '__main__':
    main()

考え方

配列Hを左から順に、
一つ前の数値より大きい場合、自身を+1することで一つ前の数値と同じにすることが出来るか否かを探索する。
自身を+1の加算または一つ前と同値が成立するか否かで、 配列Hが左から右に向かって単調非減少を成立させることができるかを探索する。