$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年当時なら通ってなさそう。
合計雨量の差にしか興味がないので、費用$d_i$を使って呪文$i$を唱えると地域$b_i$の雨量が$1$減り地域$a_i$の雨量が$1$増える、つまり雨量が$1$移動するとだけ考えればよい。雨量の移動を自由に繰り返して最小コストで雨量を平準化するのは、最小費用流問題そのものである。
最初の雨量はどの地域も$0$とし、呪文$c_1, ..., c_M$を唱えて雨量が$p_1, ..., p_K$になったとする。グラフは次のように作ればよい:
$S$の出容量のぶんだけ$T$に流したときの最小コストが答えであり、必要な量を流せない場合は$-1$である。計算量（の一例）は${O}(KE \log V)$。
ひとまず一次元の問題として考える。つまり、数直線上のある地点$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個しかないので、それを試すだけでよいらしい。途中で気づきたかった。
与えられた置換$p$を巡回置換の合成$\sigma_1\sigma_2 ... \sigma_k$に分解して、ある巡回置換$\sigma$に注目する。$\sigma$の長さが$d$とすると、
をすべて足せばこの巡回置換を一周した場合の総和が求まることになる。この際、巡回置換に現れるすべての数は同じ回数だけ$[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と同時に、それぞれの巡回置換の総和もセグメント木で持てばよいらしい。それはそうか……
lcmの範囲が大きいので逆数のテーブルは用意できない。でも、うまい方法がありそうな気もする。 ↩︎
とりあえずソートしてランレングス圧縮して、同じ距離の頂点グループ毎にグラフを作っていくことを考える。距離は頂点だけとか、距離が飛んでいる部分があってはいけないとか、そういうケースは最初に考慮しておく。
頂点からの距離がの頂点が個あるとする。距離の頂点同士はどうつないでもほかの頂点ととの距離に影響しない。したがって、通りのペアすべてに自由に辺を張れるので、距離に対して通りの辺の張り方があることになる。
次に、距離の頂点グループと距離の頂点グループをつなぐ辺の張り方を考える。これもだいたい自由に辺を張れるのだが、距離の頂点は、距離の個の頂点のうち少なくとも1つにはつながれていなければならないという制約がある。「少なくとも1つ」は包除原理で書ける:
あっ……
包除で求めてから自明な数え方に気づくパターン、これで3回目くらい。