AtCoder Regular Contest 036 B – 山のデータをPython3で解く

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典：
AtCoder Regular Contest 036 B – 山のデータ

この問題については、たぶん公式解説より分かりやすい解き方ではないかと思う。

# AtCoder Regular Contest 036 B - 山のデータ
# https://atcoder.jp/contests/arc036/tasks/arc036_b
# tag: 数列 考察

# 高さの等しい地点は存在しないので、
# 数列は必ず連続増加→連続減少を繰り返す形になる。
# （連続数は 1 以上とする）

# つまり、
# ...(増加, 減少), (増加, 減少), ....
# となっていると考えれば、数列全体を山が連続しているものと
# みなすことが出来る。

# 山の境界条件は、数列の両端と、減少→増加と転じているところ。

def main():
    N = int(input())
    field = [int(input()) for _ in range(N)]

    result = 0

    # N <= 2 ならそのまま返す。
    if N <= 2:
        print(N)
        return

    # 境界を確認していく。
    # 左端
    borders = [0]

    # 減少→増加と転じている地点
    for i in range(1, N-1):
        if field[i-1] > field[i] < field[i+1]:
            borders.append(i)

    # 右端
    borders.append(N-1)

    # 求めた境界を元に、各山の幅を求めていく。
    result = 0
    for i in range(len(borders)-1):
        width = borders[i+1] - borders[i] + 1
        if result < width:
            result = width

    print(result)

main()

arc036_b.py view raw

関連

コメントを残すコメントをキャンセル