AtCoder Beginner Contest 038 C – 単調増加 をPython3で解く

Share

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

出典:
AtCoder Beginner Contest 038 C – 単調増加

実際に数え上げる前に、ちょっとした考察が必要な問題。要素数\(N\)の数列の全連続部分区間の数を数えるのに、少しコツがいるかもしれない。

一応補足しておくと、Lを含みRを含まないような半開放区間\([L, R)\)として考えるとより分かりやすい。この場合、\(0 \le L \lt R \le N\)となり、N+1個の要素から2個選ぶ組み合わせ数と等しくなる。すなわち、\((N+1)N/2\)となる。

# AtCoder Beginner Contest 038 C - 単調増加
# https://atcoder.jp/contests/abc038/tasks/abc038_c
# 数列 考察 順列・組み合わせ 連続部分列 数え上げ

# 単調増加になる [l, r] の組み合わせ数を求める。
# 制約が 1 <= N <= 10^5 なので、[l, r] の全探索では間に合わない。
# が、ある最大の長さの部分単調増加列 [al, ..., ar] が存在する時、
# その中には要素数を N として、 (N+1) * N // 2 個の
# 単調増加列が存在することが分かる。
# (区間の左端と右端を、N 種類から 2 個 重複ありで選ぶ組み合わせ数)
# よって、端から順番に単調増加列を探していき、途切れたところで
# その中の組み合わせ数を足していけばいい。

def main():
    N = int(input())
    A  = list(map(int, input().split()))

    # 適当な初期値を設定してやる。
    # seq = 連続中の単調増加列の要素数
    # prev = 前回の数
    prev = 0
    seq = 0
    result = 0

    for a in A:
        # 単調増加が続いていれば、要素数に 1 足す
        if a > prev:
            seq += 1
            prev = a
        else:
        # 単調増加が途切れたところで、組み合わせ数を足して
        # 次の単調増加列をスタートさせる
            result += (seq + 1) * seq // 2
            prev = a
            seq = 1

    # 最後に残っている分を足してやること
    result += (seq + 1) * seq // 2

    print(result)

main()
Share

コメントを残す

メールアドレスが公開されることはありません。