AHC 018 参加期

2023.02.21

競技プログラミング

問題

概要

$ 200 \times 200 $ のマス目があり、$ W $ 箇所に水源が、$ K $ 箇所に家があります。各セルの岩盤には $ 10 $ 以上 $ 5000 $ 以下の整数で表される頑丈さ $ S_{i, j} $ があらかじめ決まっています(が、この値は与えられません)。

水源が存在するセルの岩盤が破壊されると、そのセルに水が流れます。また、水が流れるとそのセルの上下左右のセルにも流れます。

岩盤を破壊するためには、以下の掘削を繰り返し行います。

まだ破壊されていないセル $ (i, j) $ とパワーを表す5000以下の正の整数 $ P $ を1つ選ぶ。
体力を $ C + P $ ($ C $ は入力で与えられる正の整数) を消費して、岩盤の頑丈さ $ S_{i, j} $ を $ P $ 減らす。
この操作で $ S_{i, j} \leq 0 $ になった場合、セル $ (i, j) $ の岩盤が破壊される。

いくつかの岩盤を破壊し、家が存在するすべてのセルに水が流れるようにします。なるべく消費する体力が少なくなるように掘削を行ってくね。

1日目

AHC始まると言えないので先に行っておくか

今回のAHCはRustで頑張ります！！！！
— きょ (@Kyo_s_s) February 17, 2023

宣言したので、Rustで頑張ります。今回はC++のサンプルコードがあったのでまずはこれを移植します。また、Pythonをつかって500ケース実行するコードも書いておきます。以降、500回実行した時の合計点等が記載されている場合は、このコードで実行した結果です。

サンプルコードは、「家から1番目の水源をマンハッタン距離が最小になるように繋ぎ、毎回100のパワーで掘削を行う」というものでした。サンプルコードを移植し実行すると、

500/500
total: 261194177
max: (2193816, '0187')
ave: 522388.354
min: (8383, '0347')

でした。いいケースを見に行くと家が1つしかないケースだったりして、家や水源の個数にだいぶ依存しそうだなぁ、ということが分かります。

とりあえず「マンハッタン距離を重みとしてクラスカル法のように水源と連結していない場合連結させる、毎回100のパワーで掘削を行う」のを実装します。

500/500
total: 145620533
max: (1453500, '0187')
ave: 291241.066
min: (8383, '0347')

いい感じな気がしたので提出します。50ケースの結果は14,764,704点でした。意外と良い気がしたのですが、全然でした…。

2日目

昨日書いたクラスカル法みたいなのがバグっていました。クラスカル法になっていました(連結しなくていい箇所を連結していました)。修正します。

500/500
total: 131960329
max: (937600, '0449')
ave: 263920.658
min: (8383, '0347')

マンハッタン距離を重みとしていましたが、本来は頑丈さを含めないといけません。しかし、頑丈さは与えられないので、いくつかの間隔で実際に掘削を行い頑丈さを調べ、その結果を元に盤面を推測して最短経路を重みとしてクラスカル法をしてみます。推測は、「まず20おきに100個掘削を行い、掘削を行っていないセルは一番近い掘削を行ったセルの頑丈さ」として、上下左右の平均を取るのを40回程度繰り返したものを使用しました。

500/500
total: 131424894
max: (943944, '0253')
ave: 262849.788
min: (23331, '0347')

掘削は、パワー100で壊れるまで叩く、としていたのですが、例えば $ C = 128 $ の時、だいぶもったいないので推測をするときは毎回パワー500で叩くようにし、また家/水源からとても離れているようなサンプリング点は掘削を行わないようにしました。

500/500
total: 127000954
max: (916756, '0187')
ave: 254001.908
min: (30432, '0300')

提出すると12,176,969点で微妙です。提出した時はこれで250位相当だったので、何か見落としている気がします…。

3日目

ビジュアライザーを眺めます。

field

よく見ると、頑丈さがが低いセルのほうが多そうです。実際、全体の $ 50\% $ が頑丈さ500以下でした。この分布を考慮し、掘削を行うようにしました。 (盤面の頑丈さの生成方法を見れば分かるのかもしれないのですが、数式多すぎて嫌になって読んでいませんでした…><)

500/500
total: 115730666
max: (1078022, '0449')
ave: 231461.332
min: (48975, '0482')

提出, 10,564,394 点と少しずつ改善できています。この後、サンプリングの掘削では2500以上であることが分かったら掘削をあきらめて高いと推測するようにしたり、$ C $ の値によって掘削を行うパワーを調整したりして、

500/500
total: 85017972
max: (839560, '0449')
ave: 170035.944
min: (36764, '0026')

提出, 7,933,536 点まで改善しました。

4日目

ビジュアライザーを眺めると、家が1つしかないケース等では半分以上の体力をサンプリングするのに使っていることに気づきました。「頑丈さ500以下のセルが半分以上」ということが分かっているので、これを考慮してサンプリングの掘削で500以上でもう諦めてしまうようにしました。

500/500
total: 73184233
max: (733262, '0029')
ave: 146368.466
min: (15923, '0347')

これがだいぶ効いたらしく、提出すると 6,846,202点で上位50位に入ることが出来ました(一瞬で落ちてしまいましたが…)。

5日目(水)

インターンでした、環境を破壊してしまいとても困りました。環境破壊のプロです。

6日目(木)

$W, K, C$ の値別に平均を求めるようにpythonコードを弄りました。また、パラメータを弄りまくっていました。最終的に

500/500
total: 65534146
max: (637202, '0449')
ave: 131068.292
min: (21568, '0332')

くらいに落ち着きました。ここから具体的な改善が余り浮かばず、こまっています。

7日目(金)

インターンでした。環境構築をやり直しました。

8日目(土)

パラメータを弄ることくらいしか思い浮かばず、特にスコアが上がりませんでした…。

9日目(日)

起きたら17時でした。何もできずに終了…。

暫定158位でした。

seed0(230982点)はこんな感じでした:

seed0

方針は間違えていなかったのですが、

サンプル点が足りない -> 無駄な経路を選んでしまう
必要ない箇所もサンプリングしている
$200 \times 200$ の盤面についてDijkstraを行っているため、そのパートの実行時間が長い
1クエリ行うたびに更新…するといったことができていない

などが原因で、なかなかスコアが伸びませんでした。悔しい…。

強い方はOptunaを使ったりしているそうです。初めて聞きました、弄ってみようと思います。