第四回 アルゴリズム実技検定

• 問題
• 提出

リアルタイム受験した。3時間55分で全完。

L - マンションの改築

差分$d_i := a_i - a_{i+1}$に注目すると、$d_i = 0$になる$i$を数えればよいことがわかる。クエリによる$(d_i)$の変動は以下のようになる:

• タイプ1のクエリ: 奇数の$i$について$d_i \mathrel{{+}{=}} v$、偶数の$i$について$d_i \mathrel{{-}{=}} v$。
• タイプ2のクエリ: 奇数の$i$について$d_i \mathrel{{-}{=}} v$、偶数の$i$について$d_i \mathrel{{+}{=}} v$。
• タイプ3のクエリ: $d_{u-1} \mathrel{{-}{=}}v$、$d_{u} \mathrel{{+}{=}} v$。

$d_i = 0$になる$i$を数えたいので、さらに$\operatorname{table}[x] := d_i=x$である$i$の総数、という情報をハッシュテーブルなどで保持しておくとよさそうだ。しかし、$(d_i)$や$\operatorname{table}$をクエリ毎に愚直に操作すると、タイプ1と2については間に合わない。

偶奇にわければタイプ1, 2はまとめて処理できそうなので、$\operatorname{offset}_奇, \operatorname{offset}_偶$という量を保持することにする:

• タイプ1のクエリ: $\operatorname{offset}_奇 \mathrel{{+}{=}} v$、$\operatorname{offset}_偶 \mathrel{{-}{=}} v$。
• タイプ2のクエリ: $\operatorname{offset}_奇 \mathrel{{-}{=}} v$、$\operatorname{offset}_偶 \mathrel{{+}{=}} v$。

$d_i$の真の値は、これらのオフセットを足したものということになる。さらに、$\operatorname{table}_奇[x] := d_i=x$であるような奇数$i$の総数とし、$\operatorname{table}_偶$も同様に定義して、タイプ3のクエリでこれらを更新する:

• タイプ3のクエリ: $d_{u-1} \mathrel{{-}{=}}v$、$d_{u} \mathrel{{+}{=}} v$。さらに$d_{u-1}$と$d_u$の変更に応じて、$\operatorname{table}_奇, \operatorname{table}_偶$を適切に更新する。

こうすると、各クエリを処理したあとの答えは$\operatorname{table}_偶[- \operatorname{offset}_偶] + \operatorname{table}_奇[- \operatorname{offset}_奇]$で求まることになる。

M - 筆塗り

与えられたグラフ$T$を根付き木とみなす。$i$回目でパス$u-v$を塗るとしたとき、$u$から塗りながら木を上昇していって$\operatorname{LCA}(u, v)$の深さ以下になったらそこで塗りは無効になると考えることができて、$v$についても同様である。そこで、事前処理で$\operatorname{q}[v] :=$一方の端が$v$であるすべてのクエリ番号（のリストや可変長配列）、という情報を用意しておくことにする。

そして、$T$を葉からボトムアップに処理する。頂点$v$を処理する際に「子から$v$に上ってきた時点でまだ有効かもしれないクエリ番号」を番号の降順で優先度付きキューに保持する。具体的に手順を書くと、

1. $v$の子$c_1, c_2, ..., c_k$の保持する優先度付きキュー$Q_{c_1}, ..., Q_{c_k}$と$\operatorname{q}[v]$をすべてマージしたキュー$Q_v$を作る。
2. $Q_v$からクエリ番号$i$を取り出し、$i$に対応する$\operatorname{LCA}(u_i, v_i)$の深さを調べ、$v$の深さがそれ以下であれば$i$を捨てることを繰り返す。$v$のほうが深ければストップし、$v$とその親をつなぐ辺がクエリ$i$で塗られていることを確定する。（$Q_v$が空になるまで見つからなければこの辺は一度も塗られていないことになる）

ダブリングでLCAを求めてマージ可能なヒープを使った場合、計算量は${O}((N+Q) (\log N + \log Q))$となる。コンテスト中にはpairing heapを使ったが、二分ヒープでもマージテクをすれば$\log Q$が掛かるだけなので十分間に合う。

操作を逆から見ると簡単になるのは確かに……

O - 宝箱

一読して、セグメント木上でin-placeにDPする方法がありそうに見えたので、うまい更新方法を探した。

以下、0-basedで考えて、鍵屋$i$に対応する区間を半開区間$[l_i, r_i)$で持つことにする。とりあえず愚直なDPを考えると、$\operatorname{dp}[x] :=$ 右端（つまり$r_i$）が$x$以下の鍵屋のみを使って得られる最大利益、とするのがよさそう。右端が$x$と一致する鍵屋$i$がただひとつ存在するケースを例にとると、遷移は

$$\begin{aligned} \operatorname{dp}[x] \leftarrow \max( & \operatorname{dp}[x-1], \\ & \operatorname{dp}[l_i] + a_{l_i} + a_{l_i + 1} + ... + a_{r_i -1}, \\ & \operatorname{dp}[l_i+1] + a_{l_i+1} + ... + a_{r_i -1}, \\ & ... \\ & \operatorname{dp}[r_i - 1] + a_{r_i - 1}) \\ \end{aligned}$$

となる。遷移を見ると、$a_i$を加算している部分が前もって$\operatorname{dp}$に足されていれば、区間$\max$でまとめて処理できそうだ。実際、$\operatorname{dp}[x]$を処理したあとの遷移の式には、$\operatorname{dp}[0], \operatorname{dp}[1], ..., \operatorname{dp}[x]$は常に$a_x$が加算された形しか出てこないので、$\operatorname{dp}$を遅延セグメント木などで持っておいて、必要なタイミングで区間加算すればよい。疑似コードで書くと以下のようになる:

res = 0
for r from 1 to N:
  dp[r] = max(dp[r], dp[r-1])
  dp[0], ..., dp[r-1] += a[r-1] # 区間加算
  for l, c in 右端がrの鍵屋:
    dp[r] = max(dp[r], max(dp[l], ..., dp[r-1]) - c)
  res = max(res, dp[r])

上の$\operatorname{dp}$の定義は$\operatorname{dp}[x]$を処理した瞬間にしか成り立っていないことに注意。