ALGO ARTISさん主催のプログラミングコンテストコンテスト、 ALGO ARTIS プログラミングコンテスト2023（AtCoder Heuristic Contest 020） - AtCoder に参加してきました。
コンテストの場を提供してくださった ALGO ARTIS社、AtCoder社の皆様、本当にありがとうございます。 めっちゃ楽しかったです。
ということで振り返りのメモ。
最終スコア は 338,873,503。最終順位は758位でした。
(最後の提出が30秒間に合わなくて泣いた図)
コード類はこちら
AHCは実装 -> ちゃんと動くか確認 -> スコアが変わってるか確認! のイテレーションを高速に回すのが大事なはず。推測するな、計測せよの精神で挑もう、、、。ということで、テスト実行環境の準備を実施。
Introduction to Heuristics Contest が良いよ、という風のうわさを聞いたので、これを解きながらテスト環境や各種クラス、インターフェースを整備しました。
インターフェースや各種判定処理などは十分に整理しきれていませんが、最低限以下を整えると戦いやすいのかなと思って準備。 1
-
ファイルからサンプル内容を読み込んでテスト実行する環境
-
標準入力からうけとって、標準出力するテスト。テストクラスから標準入力に無理やり書き込んでテストする (E2Eテスト、という名前にしていますが、本当にE2Eか？)
-
Inputクラスを受け取り、Outputクラスを返すインターフェース。
- インターフェースを揃えるのでテストクラスからの入出力が非常に楽だし、評価もしやすい。個別で必要になるパラメータはコンストラクタで渡す想定。
-
ランダムなテストケースの生成処理 2
-
山登り法などをするためのタイマー処理。
-
Rustを読む気持ち。実行環境まではなくてもいいはず。 3
Introduction to Heuristics Contest を解きながら、これらを準備していました。
準備した結果はこちら -> HirokiYoshida837/ahc-intro-heuristics
エナジードリンクとバナナを準備して 開始時刻 15:00 を待ちます。
プロジェクトファイルはちゃんと事前に作っておきましょう。
問題文をよんで、入出力を受け取る処理の作成と、最低限満たせばいい出力内容を把握します。
seed=0 の場合のサンプル出力をビジュアライザのページに貼り付けて、全体の方針をなんとなく考えてみます。
まずは0点以上の動くコードを提出できればいいので、適当に基地局の出力を入力。 辺も全部ONにした状態でSubmitします。
ans.plist = Enumerable.Range(0, n).Select(_ => 100).ToArray();
ans.bList = Enumerable.Range(0, m).Select(_ => 1).ToArray();
かなり微妙な出力な気がしますが、やるべきことのイメージが何となく見えたのでまずこれでOK。以下あたりを考えていました。
- 基地局と、各基地局間をむすぶ辺がそれぞれたくさんあるので、不要な辺はOFFにしていいはず。不要にする辺をどうにかして探すのがよいのかな？
- 基地局は、ONになっている辺を辿って、(0,0)にたどり着ける状態でなければならない。
- 全部の基地局は使う必要がない。
- 基地局のカバーできる範囲はPによって決まる。Pを下げていけば効率があがるのかな？
各基地局の出力を 100 にしてたらスコアがまったく出なかったので、ひとまず出力を最強にしてみます。
var plist = Enumerable.Range(0, input.n).Select(_ => 5000).ToArray();
var bList = Enumerable.Range(0, input.m).Select(_ => 1).ToArray();スコア 309,165,227 となり、かなり上がりました。
基本的に全部の住宅に配信できるように利用する基地局と、辺を設定するのが良さそう。
テスト用に、ビジュアライザから10ケースほどDLしてファイルに保存。
テストケースを書いていつでもファイルから読み込んで実行できるように、各メソッドや構造体を整備します。
山登り法など、スコアの変動をみてパラメータを調節するような解き方をする場合はスコア評価用のコードは必須。
『ビジュアライザの中のコードを移植すればいいよ』と聞いているので、愚直に移植作業をします。
ここからファイルをDLして
このあたりを探す。今回の場合、compute_score メソッドがあったので、これを C# に移植する。
Rustは詳しくないので雰囲気で読み解いて実装。
計算結果が、Web版ビジュアライザと合わなくて四苦八苦。どこが間違えてるのか探す。
アホです。IDEもwarning出してました。それぞれ直してほぼ同じスコアが得られたのでやっと実装完了。
バグ一箇所目
// 桁落ちするよ
var score = (long) (1000000L * (1.0 + (100000000L / (cost + 10000000L))));バグ二箇所目
public static long CalculateCost(Input input, Response response)
{
var cost = 0L;
for (int i = 0; i < input.n; i++)
{
cost += CalculatePowerCost(response, i);
}
for (var j = 0; j < response.bList.Length; j++)
{
var used = response.bList[j] == 1;
if (!used)
{
continue;
}
var edge = input.uvwList[j];
cost += edge.w;
}
// 固定で0かえしてるのなんで！！！？？？
return 0;
}スコア計算処理が実装できたので、山登りを試してみる。
public Response Solve(Input input)
{
// タイマー 1.8 秒
var start = DateTimeOffset.UtcNow.ToUnixTimeMilliseconds();
var timeLimit = 1800L;
// 山登りのベースにする出力内容を準備。 中略
// startから1.8秒までの間、探索し続ける。
while (DateTimeOffset.UtcNow.ToUnixTimeMilliseconds() < start + 1800)
{
// ここの中で山登り処理
}
}スコアがかなり下がる。初期条件の作り方がまずそう。
山登りで変更させるのも、Powerがいいのか、辺のON/OFFなのかいまいちつかめず。どうしようか悩む。
(0,0)をルートにして、そこからBFSで一旦一通りの頂点を繋いで初期の木構造を作ってみようとする。一旦出力は固定。
全部つなぐのは非効率な気がする。辺を新しく繋いだときにスコアが下がるようであれば、探索先にいれずにスキップするようにしてみるので実装。
ちょっとだけだがスコアが上がったので少しテンションが上がる。
BFSの結果を元に、山登り法で時間いっぱい計算してみるようにする。
残り時間を考えても、辺を消すのは実装がむずかしそうだったので各基地局の出力を下げられないかを調整していく方式で試す。
ランダムに選んだ基地局の出力を、500ずつ減らしていったり、0.7倍したりして調整していくイメージで実装。
やったーー！！！！ギリギリで実装できたので、提出、、、、！
27秒たりてないです。残念。
というわけで最後の提出間に合わずに、最終スコア は 338,873,503。最終順位は758位で終了しました。
最低限の目標にしていた正の得点は得られましたが、初期スコアからほぼ伸ばせなくて悔しいです。スコアが伸びてはいましたが、最後の提出に間に合わなかったのも特に残念ですね。(提出できていれば、100位くらいは上がっていたらしい。)
ただ、色々できなかったな！という残念な思いだけではなく、本番の限られた時間の中でも色々ためせた、という点で前向きには考えています。
やはり、アルゴと同じように他の方の実装や解法をみたり、ほかのコンテストのバチャを走ってみるとかで練習してみるのが必要だと感じています。
ひとまず、反省点。
-
実装が遅い
- やっぱりコレが一番。
- テストコードやスコア計算処理部分をバグらせてて時間かけすぎてしまった。
- BFSするのもあわあわして時間がかかってしまったので反省
- そもそも、BFSじゃなくてもっといい方法があるはずでは？他の人の解法のツイートみてても似たような画像の人居ないので方針がかなり間違ってそうな気はする
-
解法の引き出しが少ない
- 「いい感じの木ってどうやって作ればいい！？BFSかDFSか！？ほかに手段はどうしよう、、、」 となり、BFS以外の手段がとれませんでした。
- これはアルゴもヒュも知識/経験が足りてない+その場で実装する実力や胆力がないのが大きい。
-
ビジュアライザを使いこなせてない
『解を複数回出力しても良い。複数出力された場合は一番最後のもののみが採点に用いられる。ビジュアライザでは複数出力された解の比較が可能である。』の記載の意味をわかってなかったですね。- アニメーションでみれてたら、もう少し処理の実装イメージが違ったかも。
- 他のコンテストでも多分おなじ機能あるはずなので次回以降使いこなそう。
今回初めてAHCにちゃんと取り組んでみて、思っていた以上に面白かったので次回以降も参加したいです。
自分でビジュアライザを作ってみるのも面白そうなので試してみたいですね。