例年通り、４時間で２問を解いて各問題の順位の積の小ささを競う方式で、 A問題で87位、B問題で62位を取って、総合順位は 73位 / 478人(?) でした。
それぞれの問題でやったことと、軽い所感を書いていきます。
A問題
300個の数値をmod 108 の世界で互いに足し合わせあって、各数値をできるだけ0に近づけるって感じの問題でした。
途中の操作内容を変更すると、それ以降の操作内容ががっつり影響受けてしまう(はずな)ので、山登り系はやりづらいなあとか、 途中状態の良い感じの評価関数が思いつかないから、ビームサーチ系もやりづらいなあとかを考えてました。
結局よく分からなかった、かつなんとかなりそうなサイズ制約だったので、 とりあえず範囲の上限を設けた全探索投げてみて、悪くなかったのでそのまま採用する感じの流れでした。 内容の詳細は次節です。
解法
先頭の数値から順に、以下の操作を行う。
- 深さ２までの手を全探索して、対象の数値を最も小さくできる手順を見つける。
1で求めた手順を適用する。
input_0.txt のビジュアライズ結果が以下。選択肢が減ってしまう後半の数値が当然やや大きくなってしまっているものの、
全体的にはパッと見結構良さそうだったので、これを採用しました。
探索範囲は 300 * 300^2 = 2.7e8 と結構大きめで、Rustで書いて1,700ms弱でした。
コンテスト後のTLを見ての感想
- スコア関数が、A_i が 0 に近づくほど1の差のスコアへの影響が大きくなるように設計されていることを、コンテスト後に把握しました。
- スコア関数読み解くの大事だよなあと分かってはいるものの、コンテスト時間短いのもあって中々悩ましいですね。
- 実は解法のビジュアライズ結果も、パッと見ほどは良くもないのかなあとか。
- 工夫すると深さ3まで探索できる、みたいな話をTLで見かけた気がするので、あとでちゃんと探したい。
B問題
40x40 の二次元グリッド上のそれぞれのセルに、性能1~30のチェアが置かれていて、パワーを割り当てたチェアから (性能) * (パワー) のスコアを獲得することができます。
チェアは割り当てられたパワー分のマンハッタン距離内のセルを占有するので、パワーを割り当てるチェアが他のチェアの占有領域に入らないように気をつけながら、できるだけ大きいスコアを獲りましょう。
って感じの問題でした。
取り組んだ流れ
まず、貪欲と焼きなましをそれぞれ試してみました。
貪欲は、 性能が大きい椅子から順に、最大4までパワーを上げられるだけ上げるって方針で、18.0万点でした。
焼きなましは、 性能15以上の椅子を対象に、どれか１つをランダムに選んでパワーを1上げるか下げるかするって感じの遷移をして、17.7万点でした。
単に性能が大きいものを優先してくだけでも焼きなましに僅かに勝てていることから、その方針で十分悪くないスコアが取れそうに感じたので、 時間の都合とかも鑑みて貪欲の方を伸ばす方向に決めました。最終的な解法は次節です。
解法
以下の手順を行うことで、性能が高い椅子を優先して拡げようとする意図を表現しました。
- 基準値 b と、基準値の減少値 x を設ける。
- b の初期値を
30-xとする。 - 性能がbポイント以上の椅子の内、できるもの全てのパワーを１上げる。
- b の値を x だけ減じる。
- 2~4 を操作対象の椅子が無くなるまで繰り返す。
上記手順を、x の値が 1~7 のパターンでそれぞれ試して、最もスコアが良いものを選びました。 これが19.8万点でした。
感想
日本橋ハーフマラソンは例年こけているイメージだったんですが*1、今年は２桁順位に入れてよかったです。AHCでハーフマラソン慣れしたのが大きいのかもしれません。
今年は解説動画も有って、復習がしやすくてありがたいです。生で見てたんですが、結構ついていけてなかったので、改めて見直してみようと思っています。
*1:去年の順位を確認したら356位でした..
