Skip to content

toona note

AHC013 参戦記

はじめに

AtCoder Heuristic Contest 013 に参加しました。
ヒューリスティック系のコンテストの参加は初めてです。
今回の参加目的は、マラソン系のコンテストがどのような物か知ることと、rust を書くことです。
お仕事では python を使っています。 rust は趣味で触っています。

初回提出

まず、正の得点を得る事から始めました。
python c++ のサンプルプログラムが提供されているので、python プログラムを rust で書き直して提出します。
クレートと rust のバージョンの問題で CE を何度か出しましたが、 CE のメッセージが読めるので問題ありません。
rust は AtCoder では 2018 であることに気が付かず、2020 で書いていました。

書き直しながら、改善ポイントを考えました。
pc を移動するのは、移動作業の順番の依存性があるので、難易度が高そうです。移動先を決めていれば何とかなりそうなので、同一 pc の濃度を高める方針でできないかな? と考えました。
pc の接続は、とりあえず、なるべく得点が高くなるように焼きなましてみる方針でやってみます。

pc の移動とあきらめ (スコア 20K)

同一種類 pc の濃度 を考えたいので、盤面に 5 つのポイントを用意しました。4 隅と中心です。 このポイントでボロノイ図を作ります。
次に初期状態で、各エリア内に存在する同一種類の pc の個数をカウントして、エリア内の同一 pc の濃度としました。
その後、エリア内の pc の濃度を向上する方向にエリア間で pc の移動を繰り返した後、適当な回数で移動を打ち切ってケーブルを接続しました。
濃度が高いので大きなクラスターができる可能性が上がるはず。 という考えでした。
が、得点は向上しませんでした。
そこで、濃度の向上は移動回数が多くなりすぎるのだと考えました。つまり移動回数が少なくなるような濃度の向上方法があれば問題ありません。
イメージとしてはレインボーカクテルのように複数個のエリアを作ってあげて、そこに指定の種類の pc を集める感じならできるかな? と考えました。 しかし、先の濃度向上移動により点数が上がらなかったため、臆病になって、いったん諦めました。

ケーブル接続の焼きなまし (スコア 30K)

移動はいったん諦めて、ケーブル接続の焼きなまし作業を開始します。
最初に盤面をなめて、同一種類の pc を接続できるケーブルの組を vector に入れていきます。次に、vector からケーブルを選択する焼きなましをしました。
ケーブルの vector には、交差するケーブルも入っていますが、焼きなましによる選択時は、交差するケーブルは許容しません。
簡単なことしかしていませんが提出スコアが 20K -> 30K 程度に向上したので気分がよくなります。

pc の簡単な移動を採用 (スコア 100K)

ケーブル焼きなましで、更にスコアを伸ばす方法を考えました。
焼きなます時のケーブルの選択肢を増やしてあげればよさそうです。
つまり、同一種類の pc を接続可能なケーブルの数を増やせばよいはずです。 この程度の pc 移動処理でしたら簡単にできます。
pc を上下左右 1 マス移動した際に、接続可能なケーブル数が増加するならば移動する。 というルールで移動処理を行い、ケーブル接続を行います。 移動、接続処理の回数の比率は 2:8 としました。
これでスコア 100K を超えました。

pc 移動の評価方法の検討と失敗

pc 移動の評価をケーブルの本数で行っていましたが、よりよい方法がないか考えます。
評価関数の性質として、より大きなクラスターを作るのがよいので、なるべくケーブル候補のクロスが少なく、1 つの pc から多くのケーブルが生えている状態が良いはずです。
この考えに基づいて評価関数を作ってみました。
まず、盤面のケーブルの端点となる pc がある部分を +1, pc を除くケーブル部分を-1 します。 全てのケーブル候補にこの処理を施すと、出来上がった盤面上の数字は、交差する候補がある部分では -2, 同一 pc が複数のケーブルの始点として用いられる場合は +2 以上になるはずです。
盤面上の -2, +2 以上の数字の和を評価関数として、この評価関数が最大になる方向に 1 マス pc を貪欲に移動しました。
が、スコアは改善せず。
では 2 マスの移動も許容してみてはどうでしょう?
試してみましたが全く改善しません。
どうやら筋が悪いようです。

最終調整 (スコア 120K)

pc の移動とケーブル接続の回数の比率は適当に決めていたので、そこだけ比率を変更して、 3:7 がよさそうかな? として終了しました。

GitHub

コンテスト後

twitter に流れる解法を見ていると学びがありますね。
ただ、私は AHC 初心者なのでコード読むのはサボってはいけないですね。
あと、rust の log 出力方法を知らずにサボってしまったのが反省点です。 調べてみたところ、簡単にできそうです。 コンテスト中は点数に繋がらない施策を打つ気になれなかったので、このあたりの環境面のを次回までに固めます。

雑感

初回提出のハードルが低いのが素晴らしいです。
過去に kaggle の submisson error で 1 週間溶かして撤退したことがあります。 kaggle は error 内容が出力されないので、推測するしかありません。 推測はプログラマではなくエスパーの仕事です。
その記憶と照らし合わせて参加しやすさに感銘を受けていました。
ビジュアライザが用意されているのも至れり尽くせりですね。

残念だった点は rust のバージョンです。
AtCoder 参加 はプログラム言語のお勉強も兼ねているつもりでしたので、最新版を使いたい。
この辺りの事情は全く知りませんので、複数言語でジャッジサーバー立てるのは、AtCoder 所属の凄腕プログラマをして難しいのに素人の私がかなり勝手なこと言っているかも…