ARC 083 E - Bichrome Tree

• 問題
• AC

頂点$v$が与えられたとき、$v$の部分木で$v$と同じ色の重みの和は$X_v$と決まっているが、もう一方の色の重みの和については割り当て次第である程度動かせるはず。そして、この重みの和は、小さい分には先祖の重みの割り当て方が増えるだけなので、小さければ小さいほど良いはず。

そこで、$f(v)$を次のように定める: 部分木$v$で、$v$と同じ色の重みの和が$X_v$になるように重みを割り当てたときの、もう一方の色の重みの和の最小値。

$f$の漸化式について考える。頂点$v$の子を$c_1, ..., c_k$とする。部分木$c_i$の重みの和は、一方の色が$X_{c_i}$、もう一方の色が少なくとも$f(c_i)$である。つまり、$k$個の部分木の重みの決め方は

$X_{c_1}$	$X_{c_2}$	…	$X_{c_k}$
$f(c_1)$	$f(c_2)$	…	$f(c_k)$

から上下の2択が$k$個あるので$2^k$通り考えられて、一方の色の重みの和を$X_v$以下にするという条件でもう一方の色の重みの和を最小にできれば、その値が$f(v)$である。これはナップサック問題のようなDPで求まる: $g_v(y, z)$を、部分木$c_1, ..., c_y$の一方の色の重みの和が$z$以下であるという条件下でのもう一方の色の重みの和の最小値とする。このとき、$f(v) = g_v(k, X_v)$である。$g_v$の漸化式は次のように書ける:

$g_v(0, z) = 0$

$g_v(y, z) = \min(g_v(y-1, z-X_y)+f(y), \: g_v(y-1, z-f(y))+X_y, \:+\infty)$

途中で$f(v) = +\infty$となったら答えはIMPOSSIBLEである。（ただし、それぞれ$z - X_y \ge 0, z-f(y) \ge 0$でない場合は除いて計算する。また、$v$が子を持たない場合は$f(v) = 0$だが、この計算式のままでも自然に$f(v) = g_v(0, X_v) = 0$となるので特別扱いしなくても書ける。）

計算量について。木のそれぞれの頂点$v$についてDPすることになり、その計算量は${\mathcal O}(vの子の数 \cdot X_v)$である。したがって、全体では${\mathcal O}(N\max_i X_i)$。

yukicoder No.269 見栄っ張りの募金活動

• 問題
• AC

最初に$S$から$0+K+...+(N-1)K = N(N-1)K/2$を引いておくと、１つ前の生徒の金額以上に寄付をするという問題に変わる。定式化すると、総和が$S-N(N-1)K/2$になるような長さ$N$の数列で、単調非減少であるものを数え上げればよいことになる。これは分割数、つまり非負整数$S-N(N-1)K/2$を$N$個の非負整数に分割する方法を数え上げることに等しい。¹ ${\mathcal O}(SN)$。

---

1. $S < N(N-1)K/2$の場合の答えは$0$である。 ↩︎

JAG Spring Contest 2014 C - Decoding Ancient Messages

• 問題
• AC

行と列の間の（辞書式順序に関する）最大重みマッチングを与えればよい……のだが、辞書式順序を単に整数にコーディングすればよいという部分を思いつけなくてけっきょく解説を見た。行・列は高々50でアルファベットは52種類なので、各辺の重みを

• A: $51^{52}$
• B: $51^{51}$
• …
• z: $51^0$

とすれば、「BがどれだけあってもAが1個あるほうが価値が高い」という辞書式の重みを実現できる。

ABC 136 F - Enclosed Points

• 問題
• AC
• AC (range tree)
• AC (range tree with fractional cascading)

各点$i \in S$について、$i$が何回数えられるかを求めればよいので、包除を考えるのがよさそう。点$i$の上下左右の領域にある点の集合$L, R, D, U \in S$を定める:

$L(i) := \{(x, y) \in S| x<x_i\} \\ R(i) := \{(x, y) \in S| x_i < x\} \\ D(i) := \{(x, y) \in S | y<y_i\} \\ U(i) := \{(x, y) \in S| y_i < y\}$

点$i$を含む$S$の部分集合の総数は

$2^N - 2^{|L(i)|}-2^{|R(i)|}-2^{|D(i)|}-2^{|U(i)|} \\ +2^{|L(i) \cap U(i)|}+2^{|L(i) \cap D(i)|}+2^{|R(i) \cap U(i)|}+2^{|R(i) \cap D(i)|}-1$

で求まるので、これを$i \in S$について足し合わせればよい。¹

さて、$|L(i)|, |R(i)|, |D(i)|, |U(i)|$は点を$x$座標や$y$座標についてソートしておけば尺取り法や二分探索等でそれぞれ求まる……が、よく見ると$x_i \neq x_j, y_i \neq y_j (i \neq j)$という条件があるので、単に整数$0, 1, ..., N-1$が1回ずつ現れるだけであった。したがって、

$\begin{aligned} & \sum_{i \in S}\bigl(2^N-1 - 2^{|L(i)|}-2^{|R(i)|}-2^{|D(i)|}-2^{|U(i)|} \bigr) \\ & = N \cdot (2^N-1) - 4 \cdot (2^0 + 2^1 + ... + 2^{N-1}) \\ & = (N-4)(2^N-1) \end{aligned}$

である。

次に$|L(i) \cap D(i)|, |L(i) \cap U(i)|, |R(i) \cap D(i)|, |R(i) \cap U(i)|$を求める。$(x_i, y_i)_{i \in \{1, ..., N\}}$を$x$座標についてソート済み($x_1 \le x_2 \le ... \le x_N$)とする。順序付きの集合$O$を用意して、$y_1, y_2, ..., y_N$の順に$O$に入れていく時、点$i$を処理した時点で$O$の中の$y_i$未満の点の総数は$|L(i) \cap D(i)|$に等しく、$y_i$より大きい点の総数は$|L(i) \cap U(i)|$に等しい。同様のことを逆順$y_N, y_{N-1}, ..., y_1$でやれば$|R(i) \cap D(i)|, |R(i) \cap U(i)|$が求まる。

---

2Dのクエリを処理できるデータ構造があればテクニックが無くてもできそう。2Dセグメント木とかウェーブレット行列とかいろいろあるようだが、このスライドを眺めていて、とりあえずrange treeがすぐに書けそうに見えたので書いた。かなり重いが一応通った。

fractional cascadingでオーダーを落とすやつも書いた。

---

1. 最後の$-1$は空集合を除いている。 ↩︎