関数での表現

まず、

\[ F(i, p, q) = q回目の地殻変動のあとの点(i−1, -p)と点(i, -p)の間の地表が何年前の地層か \]

と定義します。

\(q=0\) は地殻変動が起きる前です。定義より、 \(F(i, p, 0) = p\) となります。

求めたい値は、すべての \(i(1 \leq i \leq N)\) についての \(F(i, 0, Q)\) です。

再帰による解法(小課題1,2)

\(F(i, p, q)\) の再帰によって導出します。

\(q=Q\) から遡っていくので地殻変動を新しい順に見ていくことになります。

地殻変動の影響を受ける境界条件が混乱しやすいので注意が必要です。

\(D_q=1\) のとき

地殻変動は直線\(y=x-X_q\)で表されます。

地殻変動の左側が影響を受けるので、\(-p \geq i-X_q\)となるときに地殻変動の影響を受けます。

地殻変動は右方向と上方向にそれぞれ \(L_q\) だけ動くので、

\[ F(i, p, q) = \left\{ \begin{array}{ll} F(i - L_q, p + L_q, q - 1) & (i + p \leq X_q)\\ F(i, p, q - 1) & (i + p > X_q) \end{array} \right. \]

と再帰的に表現できます。

\(D_q=2\) のとき

地殻変動は直線\(y=-x+X_q\)で表されます。

地殻変動の左側が影響を受けるので、\(-p > -i+X_q\)となるときに地殻変動の影響を受けます。

地殻変動は左方向と上方向にそれぞれ \(L_q\) だけ動くので、

\[ F(i, p, q) = \left\{ \begin{array}{ll} F(i, p, q - 1) & (i - p \leq X_q)\\ F(i + L_q, p + L_q, q - 1) & (i - p > X_q) \end{array} \right. \]

と再帰的に表現できます。

計算量

\(F(i, p, Q)\)は\(Q\)回の再帰が行われます。これを\(N\)回実行するので、全体の計算量は\(O(NQ)\)となります。

公式解説の余談について

ところで、公式解説の国旗の余談のスライドのタイトルが「閑話休題」となっていますが、これは誤用です。

「閑話休題」は余談から本題に戻る際に使う言葉です。

「閑話」が余談や無駄話という意味です。それを「休題」するので、「無駄話はさておき」といった意味になります。

閑話休題。解説に戻ります。

再帰による解法2(小課題1,2)

\(F(i, p, q)\) は再帰するごとに\(i, p\)が増減するので扱いづらいです。変化が単調となるような操作ができれば扱いやすそうです。

そこで、\(u=i+p, v=i-p\)という変形を考えます。

すると、関数\(G(u, v, q)\)を\(G(i, i, Q) = F(i, 0, Q)\)となるよう下記のように定義します。

\[ G(u, v, 0) = \frac{u-v}{2} \]

\[ q > 0 かつ D_q = 1 のとき \ G(u, v, q) = \left\{ \begin{array}{ll} G(u, v - 2 L_q, q - 1) & (u \leq X_q)\\ G(u, v, q - 1) & (u > X_q) \end{array} \right. \]

\[ q > 0 かつ D_q = 2 のとき \ G(u, v, q) = \left\{ \begin{array}{ll} G(u, v, q - 1) & (v \leq X_q)\\ G(u + 2 L_q, v, q - 1) & (v > X_q) \end{array} \right. \]

求めたい値は、すべての \(i(1 \leq i \leq N)\) についての \(G(i, i, Q)\) です。

\(G\)を直接使うと計算量は\(O(NQ)\)のままです。

単調性の検討

\(G(i, i, Q)\) を呼んだときに、\(q=x\)となるときの\(u, v\)の値は一意に定まります。

よって、その値を\(u_x(i), v_x(i)\)として検討してみます。

初期状態では \(u_Q(i)=i, v_Q(i)=i\) なので\(i\)について単調増加関数です。

\(D_q=1\) のとき、\(u_q(i)\)が単調増加関数ならば\(v_{q-1}(i)\)は\(i\)について単調増加関数となります。

\(D_q=2\) のとき、\(v_q(i)\)が単調増加関数ならば\(u_{q-1}(i)\)は\(i\)について単調増加関数となります。

以上のことから、数学的帰納法により\(u_q(i), v_q(i)\)は\(i\)について単調増加関数であることがわかります。

単調性を利用した解答(満点解)

\(u, v\)について、

• 区間加算
• ある値\(x\)について、\(x\)よりも大きな値となる最小のインデックスを取得

を高速に行えるデータ構造があれば、この問題を解くことができます。

これは更新区間加算・取得区間minが可能な遅延セグ木などで可能です。累積和をとるセグ木でも可能ですが、遅延セグ木で実装する方が直感的でしょう。

ACLのlazy_segtreeでは 「\(func\) をみたす最小のインデックス」を min_left メソッドによって、\(O(\log N)\)で取得できます。

よって、\(O(Q \log N)\) ですべての地殻変動の影響を導出できます。

\(O(N)\) で解を出力する必要があるので、あわせて\(O(Q \log N + N)\) で処理することができます。

解答例(C#): https://atcoder.jp/contests/joi2016ho/submissions/23661455