문제 개요

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$)을 나타내고 있습니다.

감상

큰 값을 찾는 것이 어쩐지 싫어서 이쪽을 좋아합니다.