RECRUIT 日本橋ハーフマラソン 2021（増刊号じゃない方）に参加しました。
問題は2つあり、手順を最適化するものと、組み合わせを最適化するもの。
結果はAが提出478人中79位、Bが提出434人中148位でトータル109位でした。
問題A - 魔法使いXの戦い
300体いるモンスターの強さをバフでオーバーフローさせて弱くしてね。
バフはいずれかのモンスターの強さをいずれかのモンスターに与えて、10^8でModを取るよ。
考察
300体のモンスターに1000回のバフなので、1体あたり3.3回ほど。
バフをかけると次回以降のバフに影響が出るので、静的な評価は無理そう。
5000K、2500K、1250Kに近い値を3つ使えば全てのモンスターを1250K以下に出来そう。
ただスコア計算がLog2(強さ)で決まるので、1250K以下にするだけではスコアが25%にも満たない。
前情報だと日本橋ハーフはいつも貪欲＋ビーム（＋焼き鈍し）ということだけど…。
実装
とりあえずビームで20手読んでは10手動かしてみたいなものを組んでみる。
→2秒で1000手動かせるはずもなく…。（10手強しか動かない）
最終的には5000K、2500K、1250Kを残してその他を1つずつ3手ビームで読む形に。
複数手を復元というのはコドゲOptimizeの2048でやっていたので移植する形で持ってきたのですが、復元結果が2手だったり3手だったりでよく分からない挙動をしていました。動いてるからヨシ！
後日談
とても小さいグループととても大きいグループを作って掛け合わせる方法が強かったみたいです。150:150のグループに分かれて、一方のグループの最悪値を最高値付近まで持っていけるので0orKとの差を1/150に出来るっぽい。
そうすると貪欲というイメージが強いのですが、要は1手あたり1/150相当の改善ができればいいので、2手読みも交えることで350K強(本番1位以上)のスコアが取れました。
また1体ずつ仕上げる場合は半分全列挙という手法が使えるようで、試してみました。今回は重複選択を許す、かつ自分自身を何回も選ぶと計算が狂うので省きたいという要件だったので、元になるモンスターを固定し、全域から選んだものを1回掛け、それに対して(前半グループx2)と(後半グループx2)をそれぞれ二分探索しました。
二分探索するせいで条件などにあまり融通が利かないので、要件に合わせて都度仕様を考えないといけないタイプの手法かなぁと思いました。
問題B - マッサージチェア2021
40x40のグリッド上にマッサージチェアがあるよ。
品質×パワーで嬉しくなるけど、音がうるさいと近くの席が使えないので良い感じに調整してね。
考察
これは焼き鈍しかなぁ。
品質にはかなり偏りがあり、実際に調べてみると品質8以上が100/1600個。品質1をガチャガチャしても実入りが少なそうなので、ある程度高い物に絞った方がよさそう。
近傍はパワーの変更だろうけど、干渉をどうするか。巻き込む場合は相手を消す、巻き込まれている場合は高確率で再考にしつつ、稀に相手を弱める感じかな。パワーの変更も、ランダムな値にするものと、可能な範囲で最大にするものがあると良さそう。
実装
まずは市松模様でパワー1を並べて提出してみる。
点が上位の半分くらい取れていて、あまり爆発的に点が伸びるタイプではないことを理解。
あとは素直に焼き鈍しして、焼き鈍し後に貪欲でパワーを拡張してフィニッシュ。
空いてる場所の品質が低い椅子も使えるようにできたら良かったんだけど、品質が高い椅子だけを管理する構造で作ってしまったのもあり、そこは時間が無かった。
焼き鈍しの途中経過を見守る時間も無かった。
後日談
使用する椅子だけを決めればパワーはとても簡単に最適解が求まるらしい。言われてみれば、それはそう…。
そうなると焼き鈍しじゃなくて探索が使えるんじゃない？という話はちらっと出たものの、品質8で100個あるとなると組み合わせも2^100あるわけで、なかなか大変な気がする。探索の順番を工夫する（品質もだし、なんとなく距離が近いものが探索順も近いと良い気がする）、DFS要素が入った探索を使う（chokudaiサーチやMCTS）、そもそも探索の内容を工夫する（個々のON/OFFでなく1個ずつ順番に付けていく）などなど手を尽くせば出来る余地はあるのかなぁ…。
感想
上に行くには天才の閃きが必要なタイプの問題だったと思いますが、駄目方針なりに楽しくやれたかなと思います。
4時間で2問という特徴もあり、交互に大きい改善から入れていく慌ただしさも新鮮でした。
脳死でビーム！焼き鈍し！でやりましたが、今回はそれに甘えすぎた気がするのでしっかり分析したいですね。
