2021年8月28日土曜日

日本橋ハーフマラソン 2021

A - 魔法使いXの戦い

308662点。1つのモンスターにつき、だいたい3回くらいパワーアップできる計算で、3回ならひとつずつ最適な組み合わせを貪欲に取っていけそう。素朴にやるとO(N4){O}(N^4)だが、最後は二分探索でよいのでO(N3logN){O}(N^3 \log N)

まだ回数に余裕があるので、末尾に近いモンスターは4回パワーアップしたいが、これは素朴に探索すると間に合わない。qqに選ぶモンスターから近い数値で固まっているものを省いたりして間に合う程度のノード数に減らした。

探索する順番を工夫すれば少し伸びるかもと思っていろいろ試したが伸びず。

B - マッサージチェア2021

210901点。一点のパワーを変更して干渉する点のパワーを減らすだけの山登りをした。すぐに収束してしまうが、簡単に書けそうな他の遷移もないので多点スタートなどで時間を使い切ることにした。一点のパワーを下がるほうに変更するような完全に無駄な遷移も入れてしまっているなど、いろいろ詰めが甘かった。

AtCoder Adのように、1つのノードを大きくして周りのノードを小さくする操作と、1つのノードを小さくして周りを大きくするような操作を組み合わせて再帰的に頑張るともう少しよくなるかもと思ったが、この時間では書ける気がしなかった。

マス(i,j)(i, j)のパワーを表す変数をpi,jp_{i,j}とし、マス(i,j)(i, j)に正のパワーを与えることをバイナリ変数xi,jx_{i, j}で表すと、素朴なMIP定式化は

maximize Ei,jpi,jE_{i, j}p_{i, j}
subject to

  • 0pi,jNxi,j0 \le p_{i, j} \le Nx_{i, j}
  • pi1,j1N(1xi2,j2)i1i2+j1j21p_{i_1, j_1}-N(1-x_{i_2, j_2})\le |i_1-i_2|+|j_1-j_2|-1

という感じか。


解説を見ると全然問題の性質をとらえられていないなと思う。短時間コンテストは自明な方針を手早く実装したあと細部の詰めで同方針の人にちょっと勝つだけでそれなりの順位がとれてしまうことがありそう。

2021年8月25日水曜日

Treapのunionの計算量に関するメモ

https://www.cs.cmu.edu/~scandal/papers/treaps-spaa98.pdfm,n (mn)m, n \ (m \le n)要素のTreapのunionで期待計算量がO(mlog(n/m)){O}(m \log (n/m))であるものが紹介されている。これを使うと次のことができる:

1要素のTreapがNN個与えられたとし、これらのTreapに任意の順番でN1N-1回unionを適用してNN要素のTreapを作るとする。この時、全体の期待計算量はO(NlogN){O}(N \log N)である。

これはマージテクと同じように理解できる:

まず、定数BBが存在してm,n (mn)m, n\ (m \le n)要素のTreapのunionの期待計算量はBmlog(n/m)B m \log (n/m)以下である。

求める計算量をT(N)T(N)とする。C>0C>0が存在してNN未満の整数xxについてはT(x)CxlogxT(x) \le C x \log xが成り立っていると仮定する。このとき、T(N)CNlogNT(N) \le C N\log Nであることを示せばよい。この際、CBC \ge Bとしてよい。

T(N)maxm+n=N(Bmlognm+T(m)+T(n)) T(N) \le \max_{m+n = N} \bigl (Bm \log \frac{n}{m}+ T(m) + T(n) \bigr)

であるから、任意の分割N=m+n (0<mn)N = m+n \ (0 < m \le n)についてBmlog(n/m)+T(m)+T(n)CNlogNBm \log (n/m) + T(m) + T(n) \le C N \log Nが成り立つことを示せばよい。実際、次のように示せる:

Bmlognm+T(m)+T(n) Bmlognm+Cmlogm+Cnlogn C(mlognm+mlogm+nlogn)= C(mlognm+mlogm+nlognmm)= C(mlognm+mlogm+nlognm+nlogm)= C((m+n)lognm+(m+n)logm)= C(Nlognm+Nlogm)= C(NlognNlogm+Nlogm)= CNlogn CNlogN \begin{aligned}& Bm \log \frac{n}{m}+ T(m) + T(n) \\ \le \ & B m \log \frac{n}{m} + Cm\log m + C n \log n \\ \le \ & C \bigl (m\log\frac{n}{m} + m\log m + n \log n \bigr ) \\ = \ & C \bigl (m \log \frac{n}{m} + m\log m + n \log \frac{n}{m}m \bigr ) \\ = \ & C \bigl (m \log \frac{n}{m} + m\log m + n\log \frac{n}{m} + n \log m \bigr ) \\ = \ & C \bigl ((m+n) \log \frac{n}{m} + (m+n)\log m \bigr ) \\ = \ & C \bigl (N\log \frac{n}{m} + N \log m \bigr) \\ = \ & C(N\log n - N\log m+ N \log m) \\ = \ & CN\log n \\ \le \ & CN\log N \\ \end{aligned}

log1=0\log 1 = 0 問題があるのであまり正確でない。)

2021年8月12日木曜日

JAG Summer Camp 2017 Day 1 C - すごろく

まずはBiB_iがすべて00であるような問題を考える。ループがない、つまり同じマスに二回止まることがないので、ゴール以前の各マスに止まる確率を足し合わせたものが求める期待値になっている。

p(i)=p(i) = サイコロを振ってiiが書かれた面が出る確率 dp[x]=\operatorname{dp}[x] =マスxxに止まる確率

とするとき、0-basedで考えると遷移は

dp[x]=0kxdp[xk]p(k)\operatorname{dp}[x] = \sum_{0 \le k \le x}\operatorname{dp}[x-k]p(k)

となって、これはオンラインFFTで解ける形になっている。

BiB_iが必ずしも0でない場合について考える。Bx>0B_x > 0であるようなマスxxについては、オンラインFFT中にdp[x]\operatorname{dp}[x]に加算する時に、代わりにdp[x+Bx]\operatorname{dp}[x+B_x]に加算すればよい。また、Bx<0B_x < 0、つまり休みのマスについては、そのようなマスに止まる確率×Bx\times |B_x|を結果に足せばよさそう……だが、他のマスからBBの影響で進んできた場合は休まないので、dp\operatorname{dp}を構成し終えてからdp[x]×Bx\operatorname{dp}[x] \times |B_x|を後で足すと正しく計算できない。やはりオンラインFFT中にdp[x]\operatorname{dp}[x]に加算する瞬間に結果に足す必要がある。