AtCoder Heuristic Contest 003参加記録
2021/05/22~2021/05/30に開催されていたAtCoder Heuristic Contest 003に参加しました。
結果
2,714,146,570,468点/3,000,000,000,000で、334位/1000でした。
パフォーマンスが1580で、レートが580に上がったのでよかった。
AtCoder Heuristic Contest（AHC）とは？
AtCoderにて新たに定期的に開催されるプログラミングコンテストです。ABC/ARC/AGCなどのアルゴリズムコンテストと異なり、最適解を出すのが難しい問題に対し、出来るだけ良い解を作成するコンテストとなります。
マラソン形式のコンテストですね。
AtCoder Heuristic Contest 003
概要
辺の長さが未知の30×30頂点の無向グリッドグラフ上のスタート地点とゴール地点の座標が1000個のクエリとして与えられる。各クエリに対してスタートからゴールまでのパスを出力せよ。パスの長さが短いほど高い得点が得られ、後半のクエリの方が得点の重みが大きくなる。
各クエリに対してパスを出力するごとに、パスの長さに0.9~1.1の乱数をかけたものをフィードバックとして返す。
各辺の長さがわからない状態から、フィードバックの情報をもとに辺の長さを予想して、スタートからゴールまでのパスのうちなるべく短いものを答えてね。という問題です。
戦略
愚直な解法
とりあえず得点を得るために、縦の座標を合わせる→横の座標を合わせるという遷移でゴールを目指す愚直なアルゴリズムを書きました。
コードは以下みたいな感じ。
int si,sj,ti,tj;
cin >> si >> sj >> ti >> tj;
string path = "";
int ci = si;
int cj = sj;
while(ci!=ti) {
if(ci>ti) {
ci--;
path += "U";
}
else {
ci++;
path += "D";
}
}
while(cj!=tj) {
if(cj>tj) {
cj--;
path += "L";
}
else {
cj++;
path += "R";
}
}
cout << path << endl;得点: 63,179,310,956点/100,000,000,000
ダイクストラ法で最短パスを探索
重みが負でないグラフ上の最短パスを求めたいのでダイクストラ法が使えます。各辺の長さを5000で初期化し、「クエリごとに最短パスを探索→フィードバックされたパスの長さを移動回数で割った平均値で各辺の長さを更新」を繰り返しました。
得点: 83,111,190,986点/100,000,000,000
改善
初期値
各辺の長さの初期値を修正
辺の長さの更新
フィードバックの平均値で辺の長さを更新する際の、元々の辺の長さと平均値の重みを修正
以上2点をローカルのテストケースで組み合わせを試しまくって強いパラメータを探しました。
結局初期値4000、平均値:元々の距離を7:3で更新するようにしたところ、
得点: 90,308,206,390/100,000,000,000まで得点が上がったので、これで確定しました。
反省点
他の人の解法を見て、やったほうが良さそうと思った点
序盤は辺の長さの情報を集める
得点の計算方法的に、序盤のクエリが合計得点に占める割合が小さく、終盤にむけて重みが大きくなるため、序盤100クエリぐらいは愚直なアルゴリズムで辺の長さの情報を集めることに注力した方が良さそう。
フィードバックされたパスの長さの精度を考慮する
辺の長さは、一律で平均値:元々の距離を7:3で更新するようにしていたのですが、移動回数が少ない場合の方が平均値の精度が高くなるので、それを踏まえて重みを決定した方が良さそう。
感想
コドゲに続いてAHCも初参加でしたが、マラソン形式楽しいですね。こねこね試行錯誤して得点が伸びたときに快感があります。（苦労して修正したのに伸びないときはとても悲しいですが）
他の人の解説記事を読んで次回に備えます🙋♂️