日本橋ハーフマラソン 2021

• 提出

A - 魔法使いXの戦い

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

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

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

B - マッサージチェア2021

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

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

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

maximize $E_{i, j}p_{i, j}$
subject to

• $0 \le p_{i, j} \le Nx_{i, j}$
• $p_{i_1, j_1}-N(1-x_{i_2, j_2})\le |i_1-i_2|+|j_1-j_2|-1$

という感じか。

---

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

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

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

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

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

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

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

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

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

$$\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}$$

（$\log 1 = 0$ 問題があるのであまり正確でない。）

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

• 問題
• AC

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

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

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

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

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

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