JOI2008 春合宿 - ナイルドットコム

• 問題
• AC

$f(x) := x$日目を終えた時点での最小金額 とするとき、

$$f(x) = \min \begin{cases} f(x-1) + 1日間同じ店で購入する場合の最小金額 \\ f(x-2) + 2日間同じ店で購入する場合の最小金額 \\ ... \\ f(0) + x日間同じ店で購入する場合の最小金額 \end{cases}$$

となっている。上から順に、つまり$k=1, 2, ..., x$という順に$k$日間同じ店で購入する場合の最小金額を求めていくのは、ひとつ前の情報を利用すれば${O}(N)$で可能なので、全体の計算量は${O}(ND^2)$になる。

この方針だと割り算を排除しないと通らなかった。実際のループ回数は$2 \times 10^8$くらい？

---

もっとましな方法があるらしいのであとで確認する。というか、2008年当時なら通ってなさそう。

KUPC 2014 I - Rain

• 問題
• AC

合計雨量の差にしか興味がないので、費用$d_i$を使って呪文$i$を唱えると地域$b_i$の雨量が$1$減り地域$a_i$の雨量が$1$増える、つまり雨量が$1$移動するとだけ考えればよい。雨量の移動を自由に繰り返して最小コストで雨量を平準化するのは、最小費用流問題そのものである。

最初の雨量はどの地域も$0$とし、呪文$c_1, ..., c_M$を唱えて雨量が$p_1, ..., p_K$になったとする。グラフは次のように作ればよい:

• $p_v>0$なら、始点$S$から$v$に容量$p_v$、コスト$0$の辺を張る。
• $p_v<0$なら、$v$から終点$T$に容量$-p_v$、コスト$0$の辺を張る。
• 各$b_i$から$a_i$に容量$\infty$、コスト$d_i$の辺を張る。

$S$の出容量のぶんだけ$T$に流したときの最小コストが答えであり、必要な量を流せない場合は$-1$である。計算量（の一例）は${O}(KE \log V)$。

JOI2011 本戦 D - 歩くサンタクロース

• 問題
• AC

ひとまず一次元の問題として考える。つまり、数直線上のある地点$t$に降り立って、各点$x_1, x_2, ..., x_n$に行って帰る問題である。さらに$x_1 \le x_2 \le ...\le x_n$と仮定する。最後に訪れる点を$x_k$とする時、総距離は

$$\ 2|t-x_1| + .... + 2|t-x_{k-1}| + |t-x_{k}| + 2|t-x_{k+1}| + ... +2|t-x_n|$$

となる。絶対値関数の和は下に凸になり、区分する点の中央値で最小値を取ることを使えそうな気がする。しかし、係数が邪魔なので開いて並べる:

$$|t-x_1|, |t-x_1|, ... , |t-x_{k-1}|, |t-x_{k}|, |t-x_{k+1}|, ... , |t-x_n|, |t-x_n|$$

これら$2n-1$個の点の真ん中にある点$x_l$は（奇数個だから）一点に定まるので、上の式に$t=x_l$を代入すると最小値が求まる。具体的には、右側にある$n-1$個の$x_i$を足して左側にある$n-1$個の$x_i$を引けばよい。最後に訪れる点を$n$通り試せば答えがわかる。二次元の場合もまったく同じで、$x$方向と$y$方向について独立に求めてから和を取ればよい。

実装について。いろいろやり方はありそうだけど、ソートされた列に順序を保って挿入・削除する操作があって、さらに区間の和が高速に求まれば直接的にシミュレーションできるのでそれがもっとも簡単に見える。平衡二分木ならどちらも${O}(\log N)$でできる。

---

けっきょく真ん中になりえる点は1個か2個しかないので、それを試すだけでよいらしい。途中で気づきたかった。

JAG Summer Camp 2013 Day 2 G - Perm Query

• 問題
• AC

与えられた置換$p$を巡回置換の合成$\sigma_1\sigma_2 ... \sigma_k$に分解して、ある巡回置換$\sigma$に注目する。$\sigma$の長さが$d$とすると、

• 列$\sigma x$の区間$[l, r]$の総和
• 列$\sigma^2 x$の区間$[l, r]$の総和
• ...
• 列$\sigma^d x = x$の区間$[l, r]$の総和

をすべて足せばこの巡回置換を一周した場合の総和が求まることになる。この際、巡回置換に現れるすべての数は同じ回数だけ$[l ,r]$に現れるので、上の総和は巡回置換に登場する数の総和の倍数になっている。

また、問題のようにすべての巡回置換を同時に適用した場合、次にもとに戻るのは（区間$[l, r]$に登場する）すべての巡回置換の長さの最小公倍数である。これを$\operatorname{LCM}(l, r)$とすると、$\operatorname{LCM}(l, r)$回の操作を行う場合、長さ$d$の巡回置換については$\operatorname{LCM}(l, r)/d$周することになる。この際、巡回置換に登場する数で最初に区間$[l, r]$に含まれていたものが$q$個であるとすると、巡回置換に登場する数はそれぞれ$q\operatorname{LCM}(l, r)/d$回足されることになる。

---

実装で迷った末に、Moのアルゴリズムを使った。

区間$[l, r]$についての値がわかっているとき、$[l, r+1]$の値を考える。まず、区間が伸びたことによって操作回数が$\operatorname{LCM}(l, r)$から$\operatorname{LCM}(l, r+1)$に伸びるので、既存の値が$\operatorname{LCM}(l, r+1)/\operatorname{LCM}(l, r)$倍になる。また、位置$r+1$が追加されるので、この位置を含む巡回置換$\sigma$の長さ$d$について、$(巡回置換 \sigma に登場する数の総和) \times \operatorname{LCM}(l, r+1)/d$が加算されることになり、新しい値が求まる。区間が縮む場合も同様に書ける。

$\operatorname{LCM}(l, r)$の値を得るのにsparse tableが使えるから計算量の問題はないと思って書き出したのだが、伸縮の際にmodの割り算が必要になるので結局$\log$がついて${O}(N \sqrt{Q} \log N)$だった。^[1]

---

lcmと同時に、それぞれの巡回置換の総和もセグメント木で持てばよいらしい。それはそうか……

---

1. lcmの範囲が大きいので逆数のテーブルは用意できない。でも、うまい方法がありそうな気もする。 ↩︎

ARC 014 - 魂の還る場所

• 問題
• AC

隣り合う同じ色の2つのボールは即消せるので、その部分は最初から存在しないものとしてよい。また、GBGのように1つ挟んで同じ色のボールも消すことができて、間のBは左右の好きなほうに置くことができるので、やはり2つのGは最初から存在しないものとしてよい。これらのパターンを連鎖的に消していけば、残るのは距離2以内に同じ色のボールがない並びのみで、これはRGBRGBRGB...のように周期3の列になっている。そしてやはりこのパターンも各色の偶数個分は全部消せる。つまり、各色の偶奇を判定して$0$から$3$までのいずれかを答えにすればよい。

ARC 049 B - 高橋ノルム君

• 問題
• AC

時間$t$が与えられたとき、$i$人目のノルム君の行ける範囲は$[x_i-t/c_i, x_i + t/c_i] \times [y_i -t/c_i, y_i + t/c_i]$となる。これらの$N$個の区間の共通部分が空でないことと、時間$t$内にすべてのノルム君が一点に到達できることは同値である。したがって、$t$について二分探索すればよい。

---

判定の部分を深く考えずに平衡二分木上のいもす法でやってしまったのだが、よく考えると区間の両端を保持するだけでよかった。

ARC 044 B - 最短路問題

• 問題
• AC

とりあえずソートしてランレングス圧縮して、同じ距離の頂点グループ毎にグラフを作っていくことを考える。距離$0$は頂点$1$だけとか、距離が飛んでいる部分があってはいけないとか、そういうケースは最初に考慮しておく。

頂点$1$からの距離が$i$の頂点が$B_i$個あるとする。距離$i$の頂点同士はどうつないでもほかの頂点と$1$との距離に影響しない。したがって、$\binom{B_i}{2}$通りのペアすべてに自由に辺を張れるので、距離$i$に対して$2^{\binom{B_i}{2}}$通りの辺の張り方があることになる。

次に、距離$i-1$の頂点グループと距離$i$の頂点グループをつなぐ辺の張り方を考える。これもだいたい自由に辺を張れるのだが、距離$i$の頂点は、距離$i-1$の$B_{i-1}$個の頂点のうち少なくとも1つにはつながれていなければならないという制約がある。「少なくとも1つ」は包除原理で書ける:

$\begin{aligned} & 2^{B_{i-1}B_i} - \binom{B_i}{1}2^{B_{i-1}(B_i-1)} + \binom{B_i}{2}2^{B_{i-1}(B_i-2)} - ... + (-1)^{B_i}\binom{B_i}{B_i}2^{B_{i-1} \cdot 0} \\ = & \sum_{k=0}^{B_i} \binom{B_i}{k}(-1)^k(2^{B_{i-1}})^{B_i-k} \\ = & (2^{B_{i-1}}-1)^{B_i} \end{aligned}$

あっ……

---

包除で求めてから自明な数え方に気づくパターン、これで3回目くらい。