Maximum-Cup 2013 F - 3人の騎士と1匹の犬

• 問題
• AC

魔力$0$の保有者はいかなる場合も不要なので最初に取り除き、$M$を$1$以上の魔力の保有者の総数としておく。

$N \ge M$のケースは簡単で、マンハッタン距離をコストにして、$M$個の騎士・魔力保有者のペアを作る最小重みマッチングを求めればよい。

$N < M$のケースが難しかった。魔力保有者をあらかじめ魔力の降順にソートしておいて、上位$N$人の魔力保有者とのマッチングを考えればよいのだけれど、$\operatorname{MAGIC}_N$とちょうど同じ魔力を持つ者が複数人いたときに誰を選ぶかが問題になる。端的には、次のようにすればよい: （$s, t$をフローの始点、終点とする）

• $s$から各騎士に、容量$1$、コスト$0$の辺を張る。
• 各魔力保有者から$t$に、容量$1$、コスト$0$の辺を張る。
• 各騎士から$\operatorname{MAGIC}_N$より大きな魔力の保有者に、容量$1$、コストがマンハッタン距離$-20000$の辺を張る。
• 各騎士からちょうど$\operatorname{MAGIC}_N$の魔力の保有者に、容量$1$、コストがマンハッタン距離の辺を張る。

$\operatorname{MAGIC}_N$より大きな魔力の保有者が必ずマッチングに含まれるようにしたいので、$-20000$の補正を入れている。あとは流量$N$の最小コストを求めて、$20000 \times \operatorname{MAGIC}_Nより大きな魔力の保有者の数$を足して戻せば答えになっている。

Indeedなう E - Page Rank

• 問題
• AC

全部$1$のベクトルからスタートして、漸化式を1000回くらい回せば収束する。

正当性があまりわかってない。漸化式中の行列を$A$としたとき、つまり$PR = 0.1 + A \cdot PR$としたとき、

1. $A$の列毎の絶対値の和が$1$未満なので$\| A \|_1 <1$。$1$ノルムについては$\|A^p\| \le \|A\|^p$が成り立つ。したがって$\lim_{p \rightarrow \infty} A^p$は収束するので漸化式も収束する。（本当に？）¹
2. 収束するなら極限は漸化式の不動点になるから、漸化式を回すだけでよい。

くらいでわかった気になっておいた。

---

1. 式変形で非正則な行列が出てこなければ大丈夫そう。非正則な場合は知らない。 ↩︎

KUPC 2019 D - Maximin Game

• 問題
• AC

とりあえずDPっぽいものから考えた。カード$1$から順にカード$N$まで二人に配っていくとして、千咲さんに$x$枚、月乃瀬さんに$y$枚配った時点で、条件に合っているような配り方の総数を$dp[x][y]$とする。遷移としては

$(S_x=1$かつ$x\le y)$または$(S_x = 0$かつ$x > y)$なら

$dp[x][y] += dp[x-1][y]$

$(S_y=0$かつ$y \le x)$または$(S_y = 1$かつ$y > x)$なら

$dp[x][y] += dp[x][y-1]$

で求まるが、${\mathcal O}(N^2)$なので制約的に無理だし、実はメモ化再帰で枝刈りされるみたいなこともないし、うまい高速化も思いつかないし……となって困っていた。

こういう問題の言い換えとして、原点$O$からスタートして千咲さんがカードを取ったらベクトル$(1, 1)$に沿って進み、月乃瀬さんが取ったらベクトル$(1, -1)$に沿って進むというのがあったなと思い出して実験してみると、次のような性質が見える:

• $O$からスタートして$(2N, 0)$に着く
• $y$座標が正の時は月乃瀬さんが勝っていて、$y$座標が負の時は千咲さんが勝っている。つまり、文字列$S$で勝ち負けが切り替わるところで$x$軸と交わる。

すなわち、$S$中で$0$が連続している部分では$x$軸の上にいなければならず（$x$軸を踏んでも良い）、$1$が連続している部分では下にいなければならない。このパスの数え上げは有名なのがあった気がすると思ってググったらカタラン数だった。同じ要素が連続している各部分列についてカタラン数を求めてかけ合わせれば答えになっている。

JOI2014 予選 F - 財宝

• 問題
• AC

ある財宝の取り方について、Annaの取った財宝の市場価値の総和を$x_A$、Brunoのそれを$x_B$とし、貴重度の総和も同様に$y_A, y_B$とする。$x_A$と$x_B$の差を一定以内におさめつつ、$y_A$と$y_B$の差を最大化する問題である。

総当たりすると間に合わないので、財宝の集合$S$を半分にわけて$S_1$と$S_2$とする。$S$からの財宝の取り方は$3^{|S|}$通りあるので、財宝の取り方全体の集合を$3^S$のように書くことにする。

ある取り方$t \in 3^{S_1}$について、二人の取り分の市場価値の差(Anna - Bruno)を$\Delta x$とし、貴重度の差を$\Delta y$とする。この時、$S_2$からの財宝のある取り方が有効であるのは、その市場価値の差が$[-D -\Delta x, D - \Delta x]$に入っている場合であり、その条件下で貴重度の差は大きければ大きいほどよい。したがって、$3^{S_2}$を市場価値の差の昇順でソートしておけば、区間$[-D -\Delta x, D - \Delta x]$に関して貴重度の差の最大値を求める問題になる。これは平衡二分木で処理できるし、スライド最大値でもできる。ソートが律速で計算量は${\mathcal O}(3^{N/2}N)$。

---

$3^{15} \simeq 1.4 \times 10^7$のソートが想定解の問題を初めて見た……

ARC 059 E - キャンディーとN人の子供

• 問題
• AC

部分点のケースについて考える。$x_i$が一定の場合、
$g(k, y) := \sum_{a_1 + ... + a_N = y} \prod_{i=1}^k x_i^{a_i}$

とすると答えは$g(N, C)$で、漸化式は

$g(k, y) = g(k-1, y) + x_k g(k-1, y-1) + ... + x_k^y g(k-1, 0)$

$g(0, 0) = 1$

$g(0, y) = 0 \qquad (y \neq 0)$

と書ける。DPすれば計算量は${\mathcal O}(NC^2)$。

元の制約についてもだいたい同じように解ける。

$h(k, y) := \sum_{x_1 = A_1}^{B_1} \sum_{x_2 = A_2}^{B_2} ... \sum_{x_N = A_N}^{B_N} \sum_{a_1 + ... + a_N = y} \prod_{i=1}^k x_i^{a_i}$

とするとやはり答えは$h(N, C)$で、

$\begin{aligned} h(k, y) & := \sum_{a_1 + ... + a_N = y} \sum_{x_1 = A_1}^{B_1} \sum_{x_2 = A_2}^{B_2} ... \sum_{x_N = A_N}^{B_N} \prod_{i=1}^k x_i^{a_i} \\ & := \sum_{a_1 + ... + a_N = y} \Bigl( \sum_{x_1 = A_1}^{B_1} x_1^{a_1} \Bigr) \Bigl( \sum_{x_2 = A_2}^{B_2}x_2^{a_2} \Bigr) ... \Bigl( \sum_{x_N = A_N}^{B_N}x_N^{a_N} \Bigr) \end{aligned}$

だから、漸化式は

$h(k, y) = h(k-1, y) + \Bigl( \sum_{x_k = A_k}^{B_k} x_k \Bigr) h(k-1, y-1) + ... + \Bigl( \sum_{x_k = A_k}^{B_k} x_k^y \Bigr) h(k-1, 0)$

となって、やはりDPすれば計算量は${\mathcal O}(NC^2)$。