暫定: 28,285,318,300点、121位
システムテスト: 1,739,788,605,739点、117位
- サイズを1/√2にしながら、格子点に試し掘りをする
- 試し掘りをする場所は、前のサイズでの試し掘りの結果からルートを決め、そのルートの周囲
- サイズを1/√2とかの話は後述
- 最後に決めたルートを掘削ときは、直前のマスの頑丈さを一定の割合で減らしたパワーで掘削する
- 掘れなかったら当然追加で掘削
- なるべく頑丈さに近いパワーで掘削することが目的
- 諸々のパラメタをOptunaで探索
17日（金）
コンテスト開始の前日。
このイベントに行って、本を買って読んだ。
ヒューリスティックコンテストのために買おうとしている人への注意として、これは「探索アルゴリズム」の本であり、ヒューリスティックコンテストだけの本ではない。 ゲームAIの話も多いので、全編ヒューリスティックコンテストの話だと思っていると「あれ？」となるかもしれない。 とはいえ、ちゃんとヒューリスティックコンテスト向けの話もある。
問題を分類してそれぞれに使うアルゴリズムが解説されており、「実践」だからソースコードもしっかりと載っている。 明日のヒューリスティックコンテストでも、「この問題はどういう種類の問題なのかな？」と見分けて、該当するソースコードをコピペすれば、良いスタートダッシュが切れるだろう（フラグ）。
18日（土）
問題を読む。
これ、進研ゼミでやったところ……ではないw あー、未知の情報があるタイプの問題か。 未知の情報はこちらに敵対的というわけではないので、対戦ゲームともまた違うよね。
パーリンノイズって最近どこかで見たような……SECCONだ。
この問題は解いておらず、パーリンノイズの詳細を知らないのでまずは調べてみた。 このページが詳しい。
いくつかバージョンがあるらしい？
テスターで使われているのはこれで、上の記事の「改良パーリンノイズ」だろうか。
ソースコードに「procedural noiseに暗号論的乱数なんて要らないよ」みたいなことが書かれている。
テスターは乱数推測を防ぐためにちゃんと暗号論的乱数を使っているけど、ここは弱いのか。
たとえ暗号論的乱数を使っていたとしても、改良パーリンノイズではパターンが少ないらしい。
問題の入力生成方法 f0 や f1 が一定で dy0 とかが整数だったら何か所か採掘してパーリンノイズを当てるのも現実的だったかもしれん。
入力の段階ごとに出力しながら、 S を自前で計算してみた。
何かややこしいことをしているなと思っていたけど、なるほど、値の小さい領域が広くなるようになっているのか。
19日（日）
インタラクティブ問題で入出力がややこしいので、とりあえずテスターとの通信部分を実装し、サンプルプログラムと同じ（と思っている）アルゴリズムを実装した。
とりあえずサンプルプログラムを出している人は多いと思うのだけど、サンプルプログラムと思われる同じスコアの塊とは微妙にスコアが異なり、tek1031さんと同じスコアになった。 はて……。 まあ、すぐに書き換えるプログラムなので、気にする必要はないだろう。
#AHC018 @tek1031 さんに並んだ👀
— kusanoさん@がんばらない (@kusano_k) 2023年2月19日
RECRUIT 日本橋ハーフマラソン 2023冬（AtCoder Heuristic Contest 018） - AtCoderhttps://t.co/DeKux5MpLQ pic.twitter.com/k41fFmZeMp
8,449,216,639点。
どのくらい改善したのかが分かるように以降もそのときのスコアを書いていく。 相対スコアなので、減ったからといってプログラムが悪くなったとは限らない。 相対スコアの計算に使われる最高スコアが更新されているかもしれないから。
テスター経由で動かすのが面倒なので、テスターを内包し、インタラクティブではない問題と同様に、標準入力に入力を渡すだけで動くようにした。
fprintf(stderr, "%1d %2d %3d %.3f %6d %8lld\n", W, K, C, time, n, score);
のようにスコアなどを標準エラー出力に出力し、
set -e
g++ -O2 A.cpp -o A
for i in $(seq 0 99)
do
f=$(printf %04d.txt ${i})
echo -n "${f} "
./A < tools/in/${f} > output/${f}
done
こんな感じのシェルスクリプトで動かすと、
0000.txt 1 9 2 0.929 8728 890256 0001.txt 3 2 1 0.193 1804 182204 0002.txt 1 4 32 0.641 6088 803616 0003.txt 3 1 1 0.117 1157 116857 :
こういう出力が出てくる。 お手軽にスコアの傾向が見られて便利。
10マス間隔でパワー100で5回叩き、その結果から線型補間で頑丈さを予測し、ダイクストラ法で掘ってみる。
13,498,197,845点。
2日目の結果としては悪くないだろう。
21日（火）
どう考えても通らないところを試し掘りしているのは無駄。 最初は粗く試し掘りをして、その状態で経路を求め、通ったところを細かく試し掘りする……ということを繰り返して細かくしていくのが良いのではないだろうか。
赤いところを掘ってから、1/2に細かくして青いところを掘ると、赤の結果が使えず無駄である。 1/3に細かくすれば良いけど、ちょっと段階が開きすぎる気がする。
次の段階を斜め45°傾けることを思いついた。 天才か？
20,492,778,007点。
この記事を書いている今思いついたのだけど、単に位置をずらせば良いだけだった……。 補間の端の処理とか面倒だったのに。
そもそも段階的に細かくしていくというのはあまり良くなさそう。 パーリンノイズが2種類の周波数だけなので、大きなサイズでは少しだけ頑丈さに相関があり、小さくなるにつれて徐々に相関が上がっていくという感じにはならなそう。
22日（水）
今まで最後に掘削するときは、パワー100固定で掘っていた。 この100はサンプルプログラムそのままだけど、100が意外と良い感じ。 とはいえ、無駄は大きい。 頑丈さくらいの力で掘りたい。 隣のマスを掘ったときのパワーの合計に適当な定数を掛けて少し減らしたパワーで掘るようにした。 徐々にパワー減らし、掘れなかったら追加で掘るのでパワーが増えて、という感じで頑丈さの変化に追従してくれるはず。
23,562,994,313点。
この問題はパラメタ調整が難しい。 いつもは上記の100ケース動かした結果の一覧を見ながら適当に人力で調整していた。 この問題はたまたま経路が変化したことによってスコアが大きく変わってしまう。
Optunaを召喚。
パラメタ調整は C 別に行った。
そういえば、Optunaも本が出ていた。 買ったけどまだ読んでいない。 次のAHCまでには読みたい。
28,810,425,261点。
23日（木）
今までは、家の順番は固定で、各家ごとに水場か今までに掘削した水路までの最短経路を求めていた。 家ごとに独立に計算するのではなく、複数の家を同時に考慮するともっと良い経路もあるよね。 良くある問題っぽいけど、探せない……。 頭の良いアルゴリズムを探すことは諦めた。 水場からダイクストラをして最初の家に到達したらその家までの水路を掘る。 距離をリセットして、水路の距離は0とし、ダイクストラをやり直して最初の家以外に到達したらその家までの水路を掘り……。 でちょっと良くなった。
28,277,377,437点。
提出した相対スコアは下がっているが、手元で実行したローカルスコアは良くなっている。
この家（と水場）を全部繋ぎたいなという問題はシュタイナー木と言うらしい。 コンテスト後の感想タイムラインで知った。 へー。 これを知っていたからといってスコアが大きく改善するわけでもなさそうで、まあ良かった。
25日（土）
試し掘りを徐々に細かくしていくという方針に限界を感じる。 試し掘り後の水路を作る部分のパワーを完璧に調整できたとしても、上位陣に及ばない。
まず、全ての頑丈さが同じと仮定して最短経路を求めます。 最短経路上で得られる情報が多そうなところを試し掘りします。 頑丈さの予測値が更新されるので、最短経路も更新します。 という方針が良いのでは？ と思い実装。 上手く動かない。 最初の最短経路の周りばかり無駄に掘る感じになる。 諦め。
これはこれで正解の方針だったっぽい。 ちゃんと実装していれば……というか、最初からこの方針を取っていれば……。
頑丈さの予測を、単なる線型補間ではなく、p 乗根を取ってから線型補完して p 乗してみる。
入力の生成方法的にこのほうが正しいはず。
p の値は分からないので、間を取って3。
ダイクストラ法で頑丈さに追加の値として C を加えていたけど、1回で掘れるとは限らない……というか、C が小さいときにはパラメタ探索で積極的に回数を増やそうとするので、ここも可変にしてみる。
26日（日）
もう思いつくことも無いので、適当にOptunaを回す。
Optunaのスコアが良くなっても、別のテストケースだと悪くなるので、過学習しているっぽいな。
W , K, C それぞれに10ケースずつ、合計3,200ケースで調整していた。
C 1個あたり400ケースだから、まあ足りないか。
C ごとの各パラメタの値を見比べ、おかしそうなところを適当に人力で変更して最終提出。
もうダメ。
28日（火）
システムテストの結果を見たら、WAが3個、TLEが7個。 なんで？？？ 試し掘りをするところに家があったりとかのパターンだとは思うのだけど、システムテストでこれだけダメなら、確率的に手元で動かしているときにも起こったと思うんだよな……。 テスターを組み込んだ版でずっと動かしていたからWAの見逃しはありえるにしても、TLEが謎。
色々ダメだったので、次回は頑張ろう。
