OrBiTal (easy)

입자 하나가 더하는 세기의 합은 $K^2$이다. 따라서 $S=\sum A_i$에 대해 $K^2\mid S$인 후보만 확인한다. 입자의 최고 세기는 $K$이므로 $K\leq\max A_i$도 필요하다.

$K$를 고정하고 왼쪽부터 보자. 이미 시작한 삼각형을 제외하면 현재 칸에 남은 값만큼 현재 칸에서 시작하는 삼각형을 넣어야 한다. 왼쪽 끝 계수가 $1$이므로 횟수가 유일하게 정해진다. 음수 횟수가 필요하거나 길이 $2K-1$이 남지 않은 곳에서 새 삼각형이 필요하면 불가능하다.

이 처리를 빠르게 하려면 $A_0=A_{-1}=0$으로 두고 $C_i=A_i-2A_{i-1}+A_{i-2}$를 만든다. 를 번 칸에서 시작하는 삼각형의 개수라 하자. 범위 밖 는 으로 두면

$$X_i=C_i+2X_{i-K}-X_{i-2K}$$

를 왼쪽부터 계산할 수 있다. $0\leq X_i\leq A_i$인지, $i>N-2K+2$이면 인지 확인한다.

후보 수를 $D$라 하면 시간 복잡도는 $O(ND+N)$, 공간 복잡도는 $O(N)$이다. 서브태스크 1에서는 $K\leq10$인 모든 후보를 확인해 에 해결할 수 있다. 서브태스크 2에서는 합 조건으로 거르지 않고 모든 를 확인하는 풀이도 충분하다.

증명

왼쪽부터 처음으로 아직 맞추지 않은 칸을 $i$라 하자. 뒤에서 시작하는 삼각형은 $i$에 영향을 주지 않는다. 따라서 이미 시작한 삼각형의 기여를 제외한 잔여값은 $i$에서 시작하는 삼각형으로만 채울 수 있다. 그 계수가 $1$이므로 횟수가 강제된다. 이 선택을 모든 칸에서 반복하면 가능한 해를 놓치지 않는다.

삼각형의 이차 차분은 시작점에 $1$, $K$칸 뒤에 , 칸 뒤에 이다. 따라서 위 점화식은 강제된 횟수를 정확히 계산한다. 모든 횟수가 비음수이고 허용된 시작 위치에만 존재하면 전체 삼각형이 선형 구간 안에 놓인다. 생성된 값과 목표값은 첫 두 경계값 및 이차 차분이 같으므로 모든 칸에서 일치한다.

Solution written by GPT6