解説：Circulating Stones

石が 2 個以上ある箱を見つけるたびに操作しても、目標の配置に近づいているとは限りません。 また、入力例 3 では一つの箱を 5 億回操作するので、手順を一回ずつ求める方法も使えません。

そこで、まず操作の順番を考えずに「各箱を何回操作するか」を求めます。 その回数を高さとして並べると、山のような形ができます。 あとは、この山をどの順番で削れば、途中で石が足りなくならないかを考えます。

箱の番号は問題文と同じく $1,2,\ldots,N$ とします。 添字は円周上で考え、例えば $f_0=f_N$、$f_{N+1}=f_1$ と読み替えます。

1. 各箱の操作回数を求める

箱 $i$ を $x_i$ 回操作するとします。 自分の操作で石が $2x_i$ 個減り、両隣の操作で $x_{i-1}+x_{i+1}$ 個増えるので、目標の配置にするためには

$$B_i=A_i-2x_i+x_{i-1}+x_{i+1} \tag{1}$$

が必要です。 この式が合っていても、操作の途中で石が足りなくなるかもしれません。 その点はいったん置いて、まず整数の回数が存在するかを調べます。

操作によって石の総数は変わりません。 $\sum_i A_i\ne\sum_i B_i$ なら、この時点で不可能です。 以下では総数が等しいとします。

回数そのものより、隣同士の差を見る

$d_i=A_i-B_i$、$s_i=x_i-x_{i-1}$ と置くと、式 (1) は

$$s_i-s_{i+1}=d_i$$

となります。したがって、最初の差 $s_1$ さえ分かれば、残りの差も順に求まります。

$$D_i=\sum_{j=1}^{i-1}d_j\qquad(D_1=0)$$

と置くと、

$$s_i=s_1-D_i.$$

一周したときの高さの変化は 0 なので、$\sum_{i=1}^N s_i=0$ です。よって

$$\boxed{s_1=\frac{1}{N}\sum_{i=1}^N D_i} \tag{2}$$

と決まります。右辺が整数でなければ、整数の操作回数は存在しません。

整数であれば、まず $x_1=0$ とし、$x_i=x_{i-1}+s_i\ (i=2,\ldots,N)$ によって全体を復元します。 このとき、円のつなぎ目でも式が成り立つことを確認しておきます。 $\sum_i s_i=0$ より $x_1-x_N=s_1$ であり、$\sum_i d_i=0$ より $s_N-d_N=s_1$ です。 したがって、この復元で式 (1) をすべての箱について満たせます。

山の最も低いところを 0 に合わせる

式 (2) によって、隣り合う箱の回数の差はすべて決まっています。 そのため、式 (1) の解同士は、全成分に同じ定数を加えたものに限られます。 逆に、全成分に同じ定数を加えても式 (1) は変わりません。

復元した $x$ は負の成分を持つことがあるので、全成分から最小値を引きます。 こうして得た列を $f$ とします。

$$f_i\ge0,\qquad \min_i f_i=0.$$

$f$ を高さとして描いたものを、ここでは「回数の山」と考えます。 この山は、最も低いところが基準線 $0$ に接しています。

非負整数の解はすべて

$$x_i=f_i+c\qquad(c\text{ は }0\text{ 以上の整数}) \tag{3}$$

と書けます。つまり、どんな手順を使うとしても、箱 $i$ は少なくとも $f_i$ 回操作する必要があります。 まだ、この最小の回数だけで実際に操作できるとは限りません。それができる条件を、ここから考えます。

ただし、$f_i$ がすべて 0 なら、式 (1) より既に $A=B$ です。 この場合はブロック数 0 を出力して終了します。以下では $\max_i f_i>0$ の場合を考えます。

2. 最後に操作する順番を考える

操作を始める側から考えると、箱を選ぶたびに石の個数が変わってしまいます。 そこで、目標の配置に到達できたとして、各箱を最後に操作した時刻に注目します。

$$F=\{i\mid f_i>0\}$$

と置きます。式 (3) より、$F$ に入っている箱は、どんな成功する手順でも必ず一度以上操作されます。 $f_i=0$ の箱を余分に操作する手順もあり得ますが、ここでは $F$ の箱の最後の操作だけを見ます。

$F$ の箱を、最後の操作が早い順に並べてみましょう。 箱 $v$ を最後に操作した後は、この箱の石が減ることはありません。 最後の操作の直後にも、石の個数は 0 以上です。 また、この順番で $v$ より後ろにある隣の箱からは、その箱の最後の操作によって少なくとも 1 個の石が届きます。 したがって、

$B_v$ は、順番が $v$ より後ろにある隣の箱の数以上でなければならない。

という条件が必要です。

この条件を満たす順番を求める

まだ順番を決めていない箱の集合を $R$ とします。 箱 $v$ の両隣のうち、$R$ に含まれる箱の数を $\deg_R(v)$ と書きます。

最初は $R=F$ とし、

$$v\in R,\qquad B_v\ge\deg_R(v) \tag{4}$$

を満たす箱 $v$ を選んで、順番の末尾に追加し、$R$ から除きます。 ここで除くのは順番を管理するための集合からだけで、石の配置はまだ変えません。

条件を満たす箱が複数あれば、どれを選んでも構いません。 実際、一つの箱を除くと、ほかの箱の $\deg_R$ は減ることはあっても増えません。したがって、除く前に式 (4) を満たしていた箱が、除いたことで条件を満たさなくなることはありません。

また、成功する操作列があると仮定すると、$R$ が空でない限り、その操作列で「$R$ の中で最後の操作が最も早い箱」$v$ は式 (4) を満たします。$R$ 内の隣の箱はすべて $v$ より後に最後の操作を行うからです。 よって、成功する操作列があるなら、この手続きが途中で止まることはありません。

したがって、箱が残っているのに一つも選べなくなった場合は不可能です。 $F$ の箱をすべて取り除けた場合は、その順番を $P$ とします。 ここまでで分かったのは必要性です。次に、$P$ が得られれば本当に構築できることを示します。

なお、順番の計算にはキューを使えます。 最初に式 (4) を満たす箱を入れておき、箱を取り除くたびに両隣の $\deg_R$ を減らします。 条件を新たに満たした箱を一度だけキューに入れれば、全体で $O(N)$ です。

3. 山を高い層から削る

順番 $P$ が得られても、そのまま一巡ずつ操作すればよいわけではありません。 例えば入力例 1 では、

$$A=(0,0,4,0,0),\qquad B=(1,0,2,0,1),$$

で、回数の山は $f=(0,1,2,1,0)$ です。 順番 $P$ として $(3,2,4)$ を選べますが、最初からこの順に操作すると、箱 $3$ の操作後に箱 $2$ には石が 1 個しかなく、続けられません。

この例では、回数が多い箱 $3$ を一度操作してから、$(3,2,4)$ の順に操作すれば成功します。 山で見ると、先に高さ 2 の層を削り、その後で高さ 1 の層を削ったことになります。

箱番号       1  2  3  4  5
f            0  1  2  1  0

高さ 2             ■          → 箱 3
高さ 1          ■  ■  ■       → 箱 3, 2, 4
基準線 0     ──────────────

一般の場合も、このように高い層から処理します。 高さ $k$ の層に含まれる箱の集合を

$$F_k=\{i\mid f_i\ge k\}$$

とし、$k=\max_i f_i,\max_i f_i-1,\ldots,1$ の順に、$P$ から $F_k$ の箱だけを抜き出した順番で、それぞれ一回ずつ操作します。 高さが大きい場合の圧縮は後で行うことにして、まず、この手順が必ず合法であることを証明します。

残りの操作回数から、現在の石の個数が分かる

箱 $i$ の残りの操作回数を $r_i$、現在の石の個数を $C_i$ とします。 既に行った操作の回数は $f_i-r_i$ なので、

$$\begin{aligned} C_i &=A_i-2(f_i-r_i)+(f_{i-1}-r_{i-1})+(f_{i+1}-r_{i+1})\\ &=B_i+2r_i-r_{i-1}-r_{i+1}. \end{aligned} \tag{5}$$

この式を使うと、箱 $v$ に石が 2 個以上あるかどうかを、隣の残り回数との比較で調べられます。

一つの層を最後まで処理できることを示す

高さ $k$ の層を始める時点では、

$$r_i=\min(f_i,k) \tag{6}$$

が成り立つものとします。 最初の層 $k=\max_i f_i$ では $r_i=f_i$ なので、確かに成り立ちます。

この層で、次に箱 $v$ を操作するとします。 この層に含まれ、まだ操作していない箱の集合を $R$ とすると、$r_v=k$ です。 隣の箱の残り回数は、$R$ に含まれていれば $k$、含まれていなければ $k-1$ 以下です。

$d=\deg_R(v)$ と置くと、式 (5) より

$$\begin{aligned} C_v &\ge B_v+2k-\bigl(dk+(2-d)(k-1)\bigr)\\ &=B_v+2-d. \end{aligned}$$

一方、$R$ に残る隣の箱は、もとの順番 $P$ でも $v$ より後ろにあります。 $P$ を作ったときの条件から、そのような隣の箱の数は $B_v$ 以下です。 つまり $d\le B_v$ なので、

$$C_v\ge2$$

です。よって、この操作を合法に行えます。

同じ議論を繰り返せば、この層を最後まで処理できます。 層に含まれる箱の残り回数は $k$ から $k-1$ へ減り、ほかの箱の残り回数は変わらないので、処理後は $r_i=\min(f_i,k-1)$ です。 これが次の層に対する式 (6) になります。

以上の帰納法により、すべての操作が合法です。 高さ 1 の層を終えると $r_i=0$ となり、式 (5) から $C_i=B_i$ が従います。

これで、回数の山が求まったときは、削除の手続きで $R$ を空にできることが、到達可能性の必要十分条件だと分かりました。 また、この構築は各箱をちょうど $f_i$ 回操作します。 到達可能なら、山全体を持ち上げる余分な操作を加えなくてもよいことも、ここで示せました。

4. 基準線に接していなければならない場所

ここまでの判定を、山の形として見直してみます。

削除の手続きが途中で止まったとします。 $f_i=0$ の箱が少なくとも一つあるので、残った箱が円全体を占めることはありません。 したがって、残った箱の連結成分は、それぞれ円周上の連続した区間です。

一箱だけの成分なら $\deg_R=0$ なので必ず削除できます。 よって、止まったときの各成分には二箱以上あり、両端の $\deg_R$ は 1、内部の $\deg_R$ は 2 です。 どの箱も式 (4) を満たさないことから、その区間では

• 両端の $B_i$ が 0。
• 内部の $B_i$ が 1 以下。

となります。さらに、残っている箱なので、区間内の $f_i$ はすべて正です。

逆に、$2\le |I|\le N-1$ の巡回区間 $I$ が上の二条件を満たし、区間内の $f_i$ がすべて正だとします。 削除の手続きで $I$ の最初の一箱を取り除こうとすると、その時点では $I$ のほかの箱がすべて残っています。 端点には少なくとも一つ、内部には二つの隣の箱が残るので、どの箱も式 (4) を満たせません。 したがって、このような区間があると $R$ を空にすることはできません。

以上から、整数の回数の山 $f$ が求まった後の到達可能性は、次の条件とも同値です。

円周上の連続した $2$ 箱以上 $N-1$ 箱以下の区間で、両端の $B$ が 0、内部の $B$ が 1 以下なら、その区間には $f_i=0$ の箱が少なくとも一つある。

目標配置がこのような区間を作るとき、回数の山は、その区間のどこかで基準線に接する必要があります。 区間全体が基準線より上に浮いていると、到達できません。

入力例 2 では $f=(1,1,0,0,0)$ です。 箱 $1,2$ はどちらも $B_i=0$ ですが、どちらの高さも正になっています。 この二箱が障害となるため、総数が一致し、整数の回数が求まっても、目標配置には到達できません。

この見方は判定の意味を理解するためのものです。 実装では区間をすべて調べる必要はなく、第 2 節のキューによる手続きで判定と順番の構築を同時に行えます。

5. 同じ層をまとめて出力する

残るのは、非常に高い山を一層ずつ処理しないための工夫です。 $f$ に現れる相異なる正の値を大きい順に

$$h_1>h_2>\cdots>h_t>0$$

と並べ、$h_{t+1}=0$ と置きます。 高さ $h_j$ から $h_{j+1}+1$ までの層では、含まれる箱の集合がすべて $\{i\mid f_i\ge h_j\}$ で共通です。 使う順番も $P$ からこの集合の箱を抜き出したものなので、すべて同じです。

したがって、この部分を一つのブロックにまとめられます。 第 $j$ ブロックでは、$P$ のうち $f_i\ge h_j$ の箱を順に並べ、反復回数を $h_j-h_{j+1}$ として出力します。 圧縮しているだけなので、第 3 節で示した操作の合法性はそのまま成り立ちます。

出力量の制限を満たすこと

$f_i>0$ の箱の数を $p$ とします。 $\min_i f_i=0$ より $p\le N-1$ であり、異なる正の高さの数は $p$ 以下です。 よって、ブロック数は $t\le N-1$ です。

各ブロックの列の長さを $m_1,m_2,\ldots,m_t$ とすると、高さを一段階下げるたびに新しい箱が少なくとも一つ加わるため、

$$1\le m_1<m_2<\cdots<m_t=p$$

です。これらは $1,2,\ldots,p$ のうちの相異なる整数なので、

$$\sum_{j=1}^t m_j \le\sum_{\ell=1}^p\ell =\frac{p(p+1)}2 \le\frac{N(N-1)}2.$$

したがって、列の長さの総和も制限内です。 反復回数の上限については、次節で確認します。

6. アルゴリズムと計算量

実装する処理は次のとおりです。

1. 石の総数を比較する。異なれば -1。
2. $D_i$ を累積和で求める。$\sum_iD_i$ が $N$ で割り切れなければ -1。
3. 隣接差から高さを復元し、最小値を引いて $f$ を求める。
4. $f_i>0$ の箱に対して、$B_v\ge\deg_R(v)$ を満たす箱をキューで取り除く。箱が残ったまま止まれば -1。
5. 得られた順番 $P$ と、降順に並べた相異なる正の高さから、各ブロックを出力する。

回数の復元と順番の構築は $O(N)$、高さのソートは $O(N\log N)$ です。 各ブロックの箱の列を作る処理に $O(N^2)$ かかるので、全体の時間計算量は $O(N^2)$ です。 付属の実装では全ブロックを保持するため、空間計算量も $O(N^2)$ です。 順次出力する実装なら、作業用の空間は $O(N)$ にできます。

整数の範囲

石の総数を $M$ とすると、$M\le N\cdot10^9$ です。 任意の $a<b$ について、

$$D_b-D_a=\sum_{i=a}^{b-1}(A_i-B_i)$$

です。右辺は、どちらも $0$ 以上 $M$ 以下の二つの和の差なので、絶対値は $M$ 以下です。 よって、$D_i$ の最大値と最小値の差も $M$ 以下です。

$s_1$ は $D_i$ の平均なので、$s_i=s_1-D_i$ の絶対値は $M$ 以下です。 最大の高さの箱と最小の高さの箱は、隣り合う箱を高々 $N-1$ 回たどれば結べるため、その高さの差は $(N-1)M$ 以下です。 全体から最小値を引いても高さの差は変わらないので、

$$\max_i f_i\le NM\le4\cdot10^{15}$$

と抑えられます。各ブロックの反復回数は隣り合う $h_j$ の差なので、$1\le q_j\le4\cdot10^{15}<10^{18}$ となり、出力の制限を満たします。 累積和や高さの計算にも、符号付き 64 bit 整数を使えば十分です。