Atcoder Heuristic Contest とは
AtCoder Heuristic Contest は、AtCoder にて新たに定期的に開催されるプログラミングコンテストです。 ABC/ARC/AGC などのアルゴリズムコンテストと異なり、最適解を出すのが難しい問題に対し、出来るだけ良い解を作成するコンテストとなります。 引用元: AtCoder
基本、アルゴリズムコンテストは問題を解くことが目的ですが、ヒューリスティックコンテストは問題を解く手順等を最適化していくことが目的になります。
AHC034
AHC034 は短期間で行われるヒューリスティックコンテストでした。
短期間のヒューリスティックは提出したすべての結果のスコアの一番良いものが採用されるというルールでした。
問題概要
20×20 の盤面に-100~100 の高さの土地があり、
その土地をトラックで増減させ、最終的に全ての土地の高さを 0 にすることが目標です。
トラックの移動と高さの変更にはコストがかかり、コストを最小化することを目指します。
やったこと
初心者向けの AHC の記事を見て、なんとなくの雰囲気を掴んでから参加しました。
環境
今回は初参加で、何もわからなかったのでアルゴリズムコンテストのための環境(C++)のまま参加してみました。
AHC034 には web ビジュアライザ があったので、それを使って問題を解いていきました。1
(どうやら Rust のビジュアライザしかない場合もあるようなので、Rust の環境も整えておいた方が良いかもしれません。)
本番
提出 1 回目
まずは盤面を左上から右端、下に行って左端、というように交互に進みながら下に移動するようなプログラムを作成しました。
その後、盤面の高さを 0 にするために、その場所の高さが 0 以上であれば高さが 0 になる量トラックに積む。
0 未満であれば 0 にできるだけ近い高さになるように(トラックの積載量を超えないように)トラックから下ろすようなプログラムを作成しました。
このコードでは、トラックに積んだ土がなくなったときに、0 未満の高さを持つ土地はそのままになってしまうという問題がありました。
しかし、AHC ではこのあとプログラムを改善していけばよいのでこのコードで 1 回目の提出を行いました。
提出 2 回目
1 回目の提出で 0 未満の高さを持つ土地がそのままになってしまうという問題があったので、その部分を改善しました。
折り返す部分で通り過ぎた 0 未満の高さを持つ土地に戻り、土地を 0 にするようにプログラムを改善しました。
(他の試みもしたので実際は 3 回目)
1 回目に比べて三倍くらいスコアが上がりましたね。
最も良いスコアが最後に採用されるので改良したらどんどん出すのがコツ。
提出 3 回目～
ここからはもう少し高度なアルゴリズムを考えてみました。
どこかの記事で見た、パラメーターをランダムに生成して、スコアが一番良かったパラメーターと出力を使うという方法を試してみることにしました。
まず、どの部分をパラメーター化するかを考えました。
- トラックの移動方向
- トラックが通り過ぎた高さ 0 未満の土地を埋め立てに行く閾値
この 2 つをパラメーター化して、ランダムに生成してスコアが一番良かったものを採用するようにしました。
トラックの移動方向
これまでは左上から右端、左端と進むようにしましたが、左上から下端、上端、など 4 通りの移動方法をランダムに選ぶようにしました。
閾値
トラックに積んだ土がある数値以上になった場合に、トラックが通り過ぎた高さ 0 未満の土地を埋め立てに行くようにしました。
実行時間もフルに使い、スコアも 1 回目の提出から 4 倍程度になりました。
まとめ
初参加でしたが、初心者向けの記事を見てから参加したおかげで、そこそこの結果になりました。
なんと 300 位以内に入ることができました。
特に難しいアルゴリズムを知らなければできないものではないので、初心者の方にもおすすめできるかと思います。
最初から高順位のプログラムを作るのではなく、最初はとにかく提出し、改善の余地を探していくのがコツだなあと感じました。
Footnotes
-
今回は web ビジュアライザと Rust ビジュアライザがありました。 ↩
