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()
関連
