CS Academy Round #76 - Pyramids

• 問題
• AC

ある種の区分線形関数に囲まれた領域の格子点を数える問題。区分線形関数を構成する線分の総数が${\mathcal O}(N)$なので、全部列挙して線分毎に下にある格子点を数えればよさそう。

まずは、与えられた点で折れ線を構成するものだけを左から列挙したい。点を$c$の昇順でソートしてスタックを持ちながら走査する。ある点$(r, c)$による山を処理するとき、スタックの先頭に入っている点（=ひとつ前の山の頂上）による山との関係には次の3通りがある:

1. 前の山に完全に含まれる
2. 前の山を完全に含む
3. 前の山と一部重なるか、遠く離れていて重ならない

今見ている点を$(r, c)$、スタックの先頭に入っている点を$(r', c')$として、

• $c+r \le c' + r'$なら1、つまり前の山に含まれるので無視
• $c-r \le c'-r'$なら2、つまり前の山を含むのでスタックをポップしてさらに前の点を見る
• それ以外は3なので新しい点をスタックにプッシュする

こうするとスタック（の反転）には山の頂点として有効な点だけが左から並ぶので、その間にできる谷に関する格子点をそれぞれ数えればよい。

数え上げパートについて。山の頂点が左から$(r_1, c_1), ..., (r_k, c_k)$と並んでいるとする。頂点$(r_i, c_i)$と$(r_{i+1}, c_{i+1})$の間にできる谷は直線$y=-(x-c_i)+r_i$と直線$y=x-c_{i+1}+r_{i+1}$の交点であり、その$y$座標は$(r_i+r_{i+1}+c_i-c_{i+1})/2$と表せる。そこで、$H= \max(0, \lceil (r_i+r_{i+1}+c_i-c_{i+1})/2 \rceil)$としてまずは下部の長方形の格子点を$H(c_{i+1}-c_i+1)$と数え、さらに上部の三角形の格子点を$(r_i-H)^2 + (r_{i+1}-H)^2$と数える。また、左端の頂点$(r_1, c_1)$の山の左側半分にある格子点$r_1^2$個と右端の頂点$(r_k, c_k)$の山の右側半分にある格子点$r_k^2$個は別に加算する。このとき、各頂点の下にある格子点をちょうど2回ずつ数えているので、$\sum_i r_i$を引けば正しい数になる。

CS Academy Round #79 - Groups

• 問題

計算量の説明がどこにも書かれていなくて困った。以下は自分の理解。

$i$番目のクエリで与えられる$P_i$人の人間について、代表者の人数を$x_i$、代表者以外の人数を$y_i$とする。$x_i$個のグループそれぞれについて、走査して離脱しないメンバーが見つかったら打ち切るのが想定解らしい。$D=10^5$として1つのクエリで調べるノード数は最大で$\min(x_iy_i, D)$なので、計算量は$\sum_{i=1}^Q \min(x_iy_i, D)$と書ける。これを評価したい。

まず、$\sum_{i=1}^Q P_i = \sum_{i=1}^Q (x_i + y_i) \le D$という制約がある。$x_i + y_i$が一定のとき$x_iy_i$は$x_i = y_i$で最大値を取るので、$\sum_{i=1}^Q x_i \le D/2$という条件下で$\sum_{i=1}^Q \min(x_i^2, D)$を評価する問題ということにいなる。面倒なので、代わりに$\sum_{i=1}^Q x_i \le D$としておく。

$x_i + x_j$が一定のとき、$x_i^2 + x_j^2$は$x_j=0$で最大になる^[1]ので、$\sum_{i=1}^Q x_i^2$を大きくするには値をできるだけ偏らせるのが最善である。ただし、1つの変数を$\sqrt D$より大きくしても意味がないので、最大値を取る配分の一つは$(x_1, x_2, ..., x_Q) = (\sqrt D, ..., \sqrt D, 0, ..., 0)$という形になる。$\sum_{i=1}^Q x_i \le D$より、最大で$\sqrt D$個程度の$x_i$を$\sqrt D$にできるから、このとき$\sum_{i=1}^Q \min(x_i^2, D) = D\sqrt D$と見積もれる。

---

1. 平面上で、原点を中心とするマンハッタン距離に関する円と、ユークリッド距離に関する円を思い浮かべればよい。 ↩︎

ARC 108 F - Paint Tree

• 問題

主張: 与えられた木$T$の直径を$D$とし、長さ$D$のあるパスの端点$V_b, V_w$が黒、白に塗られているとする。また、黒に塗られた頂点同士の最大距離を$X$とし、距離$X$の黒に塗られた2頂点$A, B$が与えられているとする。このとき、パス$V_b - A$または$V_b-B$の少なくとも一方は長さ$X$である。

証明: パス$V_b - A, V_b-B$の両方の長さが$X$未満と仮定する。3頂点$V_b, A, B$の間にできる3つのパスに共通して含まれるただ1つの頂点を$c$とすると^[1]、$d(c, A) + d(c, B) = X$だから、$d(c, A), d(c, B)$の少なくともいっぽうは$X/2$以上である。$d(c, A) \ge X/2$としてよい。また、パス$V_b - A$が長さ$X$未満という仮定より

$$d(V_b, c) + d(c, A) < X$$

が成り立つから、$d(V_b, c) < X/2$が導ける。整理すると

$$\begin{aligned} D & \le d(V_w, c) + d(V_b, c) \\ & < d(V_w, c) + \frac{X}{2} \\ & \le d(V_w, c) + d(c, A) \\ & = d(V_w, A) \end{aligned}$$

$d(V_w, A) > D$が導かれたので、直径より長いパスが見つかったことになり、矛盾する。$\square$

---

1. https://en.wikipedia.org/wiki/Tree_(graph_theory)#Properties より、For any three vertices in a tree, the three paths between them have exactly one vertex in common (this vertex is called the median of these three vertices). というやつ。 ↩︎

CODE FESTIVAL 2014 - 宝探し 2

• 問題
• AC

変更なしかつ一次元で考えると種類数の有名問題になるが、お宝が高々100種類しかないので累積和の列を100個用意するだけでよい。また、隣接要素を入れ替える操作が累積和上でどうなっているか考えると、右から左に移動するお宝に関する累積和列の1個所が+1され、左から右に移動するお宝に関する累積和列の同じ個所が-1されるだけなので、特別なデータ構造なしで処理できる。

二次元の場合も、二次元累積和を取って同じことをやればよい。上下の入れ替えでは、下から上に移動するお宝に関する累積和配列の1個所からその行の右方にある数がすべて+1され、上から下に移動するお宝に関する累積和列の同じ個所からその行の右方にある数がすべて-1される。左右の入れ替えも同様に処理できる。計算量は${O}(nmk + q\max(n, m))$。

CS Academy Round #83 - Firestarter

• 問題
• AC

着火クエリ$(T_i, A_i, B_i, X_i)$に対して新しい頂点$V_i$を導入し、辺$\{A_i, B_i\}$を分割して長さ$X_i$の辺$\{A_i, V_i\}$と長さ$L-X_i$の辺$\{V_i, B_i\}$を張る。ひとつの辺上に複数の着火が起こる場合には、3つ以上に分割する。こうしてできたグラフ上で、各頂点に初めて火が到達する時間を求める。具体的には、$V_i$の距離を$d[V_i] := T_i$とセットして多点スタートのダイクストラをする。（形式的には、大頂点$S$を導入して各$V_i$と$S$の間に長さ$T_i$の辺があると考えるのがよさそう。）

こうすると、頂点$v$に初めて火が到達する時間が$d[v]$に入ることになる。ただ、欲しいのはすべての辺が燃えきる時間なので、$\max d[v]$は答えにならない。長さ$l$の辺$\{u, v\}$が燃えきる時刻を$t$とすると$(t-d[u])+(t-d[v]) = l$なので、$t = (l + d[u]+d[v])/2$と求まる。この最大値を答えとすればよい。

---

時刻を決め打って二分探索をやってしまって、さすがにTLEだった。

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

• 問題
• 提出

リアルタイム受験した。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]$を処理した瞬間にしか成り立っていないことに注意。