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$ から始まる三角形で埋めるしかない。先頭の係数は $1$ なので個数は強制され、この処理で可能な解を失うことはない。

三角形の二階差分は開始位置で $1$、$K$ 個後で $-2$、 個後で である。したがって漸化式は強制された個数を正確に計算する。すべての個数が非負で、許された開始位置にのみ存在すれば、三角形全体が線分内に収まる。得られた列と目標列は左側の境界値と二階差分が同じなので、全位置で一致する。

Solution written by GPT6