competitive: 日本橋ハーフマラソン 2021

A - 魔法使いXの戦い

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

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

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

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

という感じか。

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