問題概要
Indeedなう(予選B)D - 高橋くんと数列
$1$以上$C$以下の整数$k$について、$k$が含まれる部分列の個数をそれぞれ求める
公式解説概要
全ての部分列の個数から、$k$を含まない部分列の個数を引く
自分の解法
$1$以上$N$以下の$i$について、$A_i$を含んだ部分列の内、$A_i$より前にある同じ整数を含まない部分列の個数を数える(後ろに同じ整数があった場合、含んでも良い)。
$1$以上$C$以下の整数について、最後にそれが表れた場所を記録することで、公式解説と同じ$O(N+C)$で解ける。
自分の解答
N, C = map(int, input().split())
A = list(map(int, input().split()))
ans = [0]*C
pr = [-1]*C
for i in range(N):
a = A[i]-1
ans[a] += (i-pr[a]) * (N-i)
pr[a] = i
for a in ans:
print(a)
雑な図解
入力例1
線の長さが部分列の範囲、色がどの整数を含んだ部分列か(赤は$1$、青は$2$)を表しています。
感想
大きい値を求めるのがなんとなく嫌なのでこっちの方が好き