AtCoder Heuristic Contest 001に参加し、978,609,236,426点で1407人中108位でした。
競技プログラミング歴はAtCoderで始めてから1年半くらいの水色で、いわゆるマラソン系コンテストは今回が初めての参加となります。
そのため、今後の自分への備忘録も兼ねて、初めてのマラソン系コンテストで考えたことやスコア推移の変化を中心に書いていきたいと思います。
問題設定
厳密な問題定義はhttps://atcoder.jp/contests/ahc001 を見てもらえればと思いますが、
ざっくりいうと、10000×10000の座標系にN(50<=N<=200)個の点(x, y)とそれぞれ指定面積rが与えるので、その頂点を含んだ長方形をN個作り指定された面積rとの差が小さくなるような配置を考える問題です。
出力例
解法要約
最終的な解法(暫定テスト49,019,393,330点)を先に書きます。
- 頂点を含む面積1の長方形をN個作る
- 長方形をランダムに選び、ランダムな方向へ拡張できるなら伸ばす
- 長方形をスライドさせる
- 長方形を縦(or横)に縮めて横(or縦)に伸ばす
- 長方形をランダムに縮める
- 現時点でスコアの低い長方形を優先的に拡張する
- 1~6を制限時間内で複数回繰り返し最良のスコアの結果を選択する
3~6の操作は一定時間が経過したら実行し、実行頻度の比率も処理ごとに調整しました。
焼きなまし法のような温度パラメータは設定せず、「解をちょっとランダムに壊す」→「構築し直す」をひたすら繰り返す感じです。
(このあたりもう少しうまくやればスコアが上げれたのかも...)
取組内容とスコア推移
考えたこととスコアが改善した内容を順番に書いていきます。
載せている点数と可視化内容については全てseed0の0000.txtを使っています。
はじめにやったこと(〜12,461点)
- https://atcoder.jp/contests/intro-heuristics の解説を読んでマラソンの基本的な手順に目を通す
- Rustの環境構築&ビジュアライザの動作確認
- 最低限必要な関数の作成
- 入出力
- Score計算
- 長方形同士が重複していないかの判定
- 指定頂点を内包しているかの判定
- 各頂点を含む面積1の長方形の解の生成
まずはとりあえず、WAにならないような解を出すことを目指しました。
下記が最初に提出した面積1の長方形の解です。
順位表だと同じスコアが並んでいるようだったので、やっぱりみんな初めはこれを提出するようです。
可視化してもほとんど点です。
ランダムな解の生成(〜823,155,925点)
-
考えたこと
- ランダムで適当に長方形を作り続けたらどのくらいのスコアになるのかを確認したい
- 制限時間が5秒なので、なるべく時間内は探索を続けたほうが良さそう
-
やったこと
- 以下の処理を制限時間5秒間繰り返し続ける
- ランダムに長方形を選ぶ
- ランダムに4方向の向きを選ぶ
- 伸ばしてもその頂点のrを超えない範囲でランダムに伸ばす距離を決める(一様分布)
- 長方形が重ならないことが確認できれば拡張する
- 以下の処理を制限時間5秒間繰り返し続ける
3では伸ばせる距離が大きすぎると細長い長方形しかできなかったので、伸ばすときの最大値は平方根をとって極端に大きな値になりすぎないようにしました。
結果が下図で、これでも80%くらいのスコアは出るようでした。
スコア：823,155,925点
改善１(〜881,082,305点)
- 考えたこと
- 8割でも人間の方がまだいい解を作れそう
- 局所解にはまっていそう
- 細長い長方形が青い(指定面積に足りてない)
- 何回か実行しても結果のぶれが大きい
- 解の生成途中のスコア推移を見てみたい
- 複数のテストケースを実行するのが面倒
- やったこと
- 細長くて、指定面積に足りてない長方形を見つけたら縮める処理を追加
- 解の生成を何回も繰り返し実行して一番良い結果を採用するようにした
- 途中スコアや長方形の状態を表示するようにするデバッグ出力の追加
- 50個のテストを順番に実行して結果の平均値を取るスクリプトの作成
今まではひたすらランダムに拡張を続けているだけだったので、局所解から抜けた解をなるべく出せるようにと思い、1と2の処理を追加しました。また、先のことも考えて面倒な部分は省力化するようにしました。結果が下図で90%くらいのスコアになりました。
スコア：881,082,305点
改善２(〜964,331,378点)
- 考えたこと
- 改善1の時点でそこそこいい感じに見える
- 青い長方形はこのままだと動かせないが、周りにスペースが余っている長方形が融通していい感じに移動してほしい(おそらく人間ならそう動かすはず)
- 多くの長方形は0.999〜のスコアだが、スコアの低い長方形は0.5以下なので、これらを改善した方がスコアへの寄与が大きいのではないか
- やったこと
- 長方形の拡張時にランダムに伸ばす距離は時間経過ごとに大きくする
- 一定時間が経過した中盤にのみ下記の処理を入れる
- ランダムに選んだ長方形を縦・横に平行移動可能ならランダムな距離を平行移動させる
- ランダムに選んだ長方形をランダムに縦に縮めて横に伸ばす等積変形(横→縦も同じ)
- スコアの低い長方形から優先的に拡張処理を行う
1、2で動かした後に3の処理を入れることで、スコアの低かった長方形が優先的に改善されないかという意図でした。これはかなり効果があったようでスコアが大きく改善し、96%くらいのスコアになりました。拡張処理に対しての緩和処理の回数などはスコアを見ながら勘で調整しました。(緩和の発生頻度を高く設定しすぎると、拡張処理が間に合わず、解が改善しなくなりました)
スコア：964,331,378点
改善３(〜977,096,587点)
- 考えたこと
- 人間だともう改善できなさそうに見えるが、上位のスコアを見ると、平均99%くらいの結果は出せるはず
- パラメータの調整でスコアを上げられないか
- 制限時間を10倍にして試行したら、スコアの改善がみられたので探索が十分足りていないのではないか
- 高速化して試行回数が増やせないか
- やったこと
- スコア計算の方法を変更
- 変更前：定期的にスコアをO(N)で再計算して確認
- 変更後：頂点ごとにスコアを保持して毎ループで結果をO(1)で確認
- 抜いても問題なさそうな処理を抜いた
- 改善１で入れた細長すぎる長方形を見つけたら縮める処理を削除
- 長方形の拡張処理に時間がかかりすぎだと感じたので、時間経過で変動する幅を大きく、収束までが速くなるようにした
- スコア計算の方法を変更
改善２からはなかなかスコアが上がらず苦労しました。試しに、制限時間を伸ばしたら結果が改善したので、無駄な処理の省略や高速化とそれに伴うパラメータの調整をしたところ、平均98%くらいの解が出せて、最終的に暫定テストで490億のスコアを超すことができました。
スコア：977,096,587点
試したけどうまくいかなかったこと
試したけれども上手くいかなかったことを書きます。
(実装や採用方法が悪い可能性があるので本当に効果が薄いのかは不明です)
- 初期解の生成方法
- 「斜め上などの方向を決めて座標順に解を作っていく」「指定面積rが小さい方から順番に解を作っていく」などを試しましたが、変化があまり見られないように感じたので、私は採用しませんでした。
- 試行中に既にスコアがよく、面積も大きい長方形のrを小さくする
- 面積が大きい長方形は多少他の長方形にスペースを譲っても、全体のスコアは下げずに利用できるスペースを増やせるのではと思いましたが、あまり改善は見られませんでした。
- 長方形の重複判定高速化
- 変形した後の長方形の重複判定はO(N)で行っていました。頂点間の組み合わせのユークリッド距離を事前計算しておいて、近い順に判定していき、重複があった時点で判定を抜けることで実行時間が短くならないかと考えましたが、あまり改善が見られませんでした。(そもそももっといい判定方法がありそうな気もしましたがわかりませんでした)
考えたけどできなかったこと
そもそも可能なのかが不明あるいは、自分の実装力ではうまく実装できなかったことを書きます。
- 長方形を変形したときに他の長方形と重複しているかの判定高速化(O(1)での実装)
- 頂点を変形したときに隣接する長方形のIDの高速な取得(O(1)での実装)
TODO
今後のコンテストに向けて身につけたいことです。
- パラメータ探索の自動化
- マラソン系の代表的なアルゴリズムの習得
まとめ
初めてのマラソン系コンテストでしたが、1週間を通していろいろ考えて楽しめることができました。普段のアルゴリズム系コンテストとはまた違った面白さがあったので、今後開催されるAHC含め、ヒューリスティックコンテストにも参加していこうと思います。
追記
提出したコードのリンクを張っておきます。
参加中は参加記を書くつもりなんて全く無かったので、コードがどんどん汚くなってしまいましたが、次回以降はバグ修正の時間を減らすためにも、コード管理もきちんとできるようにしたいです。