거리의 비용
다이아몬드 II의견: 0
길이 \(N\)의 정수 수열 \(A_1, A_2, \dots, A_N\)이 주어진다.
각 위치 \(i\) (\(1 \le i \le N\))에 대해 다음 값을 정의한다.
$$ B_i = \min_{1 \le j \le N} \left( A_j + (i - j)^2 \right) $$
즉 각 \(i\)에 대해, 어떤 \(j\)를 골라 \(A_j\)에 두 위치의 거리의 제곱 \((i-j)^2\) 을 더한 값을 최소화한다. \(B_1, B_2, \dots, B_N\) 을 모두 구해야 한다.
출력은 \(B\) 수열의 체크섬 하나로만 받는다. 체크섬은 다음과 같이 계산한다. \(M = 2^{61} - 1\) 로 두고, \(h_0 = 0\), \(h_k = \left( h_{k-1} \cdot 1000003 + (B_k \bmod M) + 1 \right) \bmod M\) (\(k = 1, 2, \dots, N\)) 을 차례로 계산한 뒤 최종 값 \(h_N\) 을 출력한다. (\(B_k\) 는 항상 \(0\) 이상이므로 \(B_k \bmod M\) 은 그냥 그 값을 \(M\) 으로 나눈 나머지이다.)
\(1 \le N \le 200{,}000\)
\(0 \le A_i \le 10^{12}\)
첫 줄에 정수 \(N\)이 주어진다.
둘째 줄에 \(N\)개의 정수 \(A_1, \dots, A_N\)이 주어진다.
위 정의에 따른 체크섬 \(h_N\) 한 개를 출력한다.
4
5 0 9 1
2000019000062000071A=[5,0,9,1]. B_1=min(5, 0+1, 9+4, 1+9)=1 (j=2). B_2=min(5+1,0,9+1,1+4)=0 (j=2). B_3=min(5+4,0+1,9,1+1)=1 (j=2). B_4=min(5+9,0+4,9+1,1)=1 (j=4). B=[1,0,1,1] 의 체크섬을 출력.
3
3 3 3
4000028000052A=[3,3,3]. 모든 i에서 j=i 가 최적이라 (i-j)^2=0, B_i=3. B=[3,3,3] 의 체크섬을 출력.
riseoj 작성
출처 Original
평가 및 의견
거리의 비용
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
거리의 비용