2019年11月27日水曜日

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

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

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

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

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

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


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

2019年11月20日水曜日

KUPC 2014 I - Rain

KUPC 2014 I - Rain

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

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

  • pv>0p_v>0なら、始点SSからvvに容量pvp_v、コスト00の辺を張る。
  • pv<0p_v<0なら、vvから終点TTに容量pv-p_v、コスト00の辺を張る。
  • bib_iからaia_iに容量\infty、コストdid_iの辺を張る。

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

2019年11月19日火曜日

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

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

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

 2tx1+....+2txk1+txk+2txk+1+...+2txn\ 2|t-x_1| + .... + 2|t-x_{k-1}| + |t-x_{k}| + 2|t-x_{k+1}| + ... +2|t-x_n|

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

tx1,tx1,...,txk1,txk,txk+1,...,txn,txn|t-x_1|, |t-x_1|, ... , |t-x_{k-1}|, |t-x_{k}|, |t-x_{k+1}|, ... , |t-x_n|, |t-x_n|

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

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


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

2019年11月13日水曜日

JAG Summer Camp 2013 Day 2 G - Perm Query

JAG Summer Camp 2013 Day 2 G - Perm Query

与えられた置換ppを巡回置換の合成σ1σ2...σk\sigma_1\sigma_2 ... \sigma_kに分解して、ある巡回置換σ\sigmaに注目する。σ\sigmaの長さがddとすると、

  • σx\sigma xの区間[l,r][l, r]の総和
  • σ2x\sigma^2 xの区間[l,r][l, r]の総和
  • σdx=x\sigma^d x = xの区間[l,r][l, r]の総和

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

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


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

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

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


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


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