AtCoder Heuristic Contest 005(AHC005) -Patrolling- 参加記
問題
結果
21,784,788点で9位。初赤パフォ。嬉しい。
解法
前処理
- 直線の通路を全て列挙する。各通路にどの交差点が含まれるか記録する。
- 各交差点と開始点を始点にしてダイクストラする。
焼きなまし
全通路を1度ずつ触れば、全マスを視界に入れたことになるので、通路を回る順番を焼きなます。順番を決めた時のスコアは、greedyに一番近い交差点へ移動した際の経路の距離とする。近傍は2-optのみ。通路の総数は100前後だし、差分計算しても速くならなそうだったので、スコア計算は特に工夫せず、毎回開始点から計算し直した。遷移回数は200万回程度。
経路決め
焼きなましのスコア計算はgreedyな経路にしたが、最後に、通路を回る順番は固定して、最短経路を計算して出力する。ただ、greedyと比べて0.2%位しかスコア改善しない。まあやらないよりはマシ。
時系列
問題読み&考察 (0:00〜0:30)
問題読んだ感じTSPだけど、どのマスを視界に入れたかを管理するの大変では、と思う。交差点でTSPするのは諦めて、上手いこと全マス視界に入れる方法を考えていると、交差点じゃなくて通路を順番に回るように考えれば良さそうということに気づく。単純に2-optすれば良さそうだし、この方針でいくことに決定する。自分の実装力だとこの方針で実装した後、方針変更する時間は残されていないだろうから、本当に良さそうかは結構考えた。
実装 (0:30〜2:00)
頑張って実装する。
提出1 (2:02) スコア 18,467,888
とりあえず山登りで提出。
提出2 (2:20) スコア 20,469,123
雑に焼きなます。瞬間3位になってビビる。
提出3 (2:52) スコア 20,516,313
最後の経路をちゃんと最短経路にする。あんまり改善しないだろうなとは思いつつも、他にやることも思いつかなかったので実装する。
焼きなましスケジュール&パラメータ調整 (〜4:00) スコア 21,784,788
残り1時間位で、アルゴリズムの改良は思いつかなかったので、ひたすらパラメータとスケジュール調整した。最終的には線形で冷やすのが良かった。
反省点
他の上位勢の解法見ると自分より明らかに深く考察している。今回はたまたまシンプルで強い解法を引けただけで、もっと考察伸ばせるようにしたい。
AtCoder Heuristic Contest 004(AHC004) -Alien's Genome Assembly- 参加記
問題
結果
6,406,046,257点で30位。限界を感じる。
解法
- 別の文字列に含まれるものは削除する。残った文字列について、何個の別の文字列を含むかをその文字列の重要度とする。その文字列が現れれば、重要度分の文字列が現れたことになる。
- 任意の2つの文字列について重複数を計算する。例えば、ABCB とCBC なら 2、ABCBC とBCBCD なら 4。また、重複数が最大となる相手の文字列を記録しておく。複数ある場合は全て記録する。
- 任意の文字列からスタートして、長さが20になるまで連結するビームサーチを行う。連結は2.で記録した重複数最大の文字列でのみ行う。ソートの評価値は連結した文字列の重要度の和とする。
- 作成した長さ20の文字列の内、出現していない文字列の数が最大のものを選択し、答えの一行として採用する。
- 出現した文字列を削除して、3・4を繰り返し行う。
その他
- 文字列はビット表現する。文字種はA〜Hの8種類なので、1文字3ビットで表現できる。一行20文字なので64ビット整数に収まる。
- 横方向のみ考えて、縦方向の出現は考慮しなかった。seed=0だと縦に出現しているのもあるがたまたまで、長い文字列の場合は横方向のみしか出現しない。
反省点
- ビームの幅調整と時間制御がなんだか上手くいっておらず、結局幅固定で提出結果で時間ギリギリになるように調整した。パラメータによって幅を変えた方が良いのは明らかで、ちゃんとやれば1、2コ順位上がってた気がする…。
AtCoder Heuristic Contest 002(AHC002) -Walking on Tiles- 参加記
問題
結果
4,997,673点で37位。橙パフォ取れたので満足。AHC001は初回だからパフォ低く出てたみたい。
考えたこと
問題見てすぐビームサーチかと思ったが、点数の高いマスを踏むより、できるだけ長いパスを作る方が大事なので、生スコアを評価値にしてビームサーチは上手くないというのは分かる。隙間がないようにパスを作成したいので、パスが空白領域を囲むようにしたらペナルティみたいなことか、と考えるが高速に計算できる気がしない。
提出1(1時間46分): スコア 3,037,491
なのでとりあえず、次に踏むタイルに隣接する使用済みのマスの個数が多い順にDFSする。
提出2(1時間54分): スコア 4,266,096
もっと単純に、中心から先に埋める or 外周から先に埋める、とすれば良いのではと思い、外周からの距離を評価値にしてDFSをする。マス(x, y)の評価値はmin(x, 49-x, y, 49-y)で、外周から埋めた方が良さそうだったので、評価値が低い順に辿る。
提出3(2時間46分): スコア 4,640,617
時間いっぱいDFSしても、おそらくパスの末端を沢山探索することになってスコアが伸びていないと思い、1回のDFSを100msにして、現時点でのベストのパスの途中から別の経路でDFSをやり直す。やり直す地点は、始点からパス長の8割の地点の中からランダムに選択する。
提出4(3時間2分): スコア 4,897,359
パラメータ調整する。1回のDFSに100msもかけなくて良さそうなので、1回3msにする。やり直し地点もパス長の9割からランダムに選択にする(これは適当)。
提出5(3時間14分): スコア 4,921,754
パラメータ調整する。DFSを1回1msにする。
提出6(3時間33分): スコア 4,991,227
パラメータ調整以外に変更できそうなのが、DFSの探索順のための評価値くらいしかないので、そこを変更する。あまり重い計算にすると、探索し直しの回数が稼げないので、O(1)で評価したい。現状min(x, 49-x, y, 49-y)となっているのを、min(x, 49-x) * min(y, 49-y) に変更するとスコアが改善した。O(1)で軽く計算できるのをとりあえず試しただけだったが、辺より隅の方が重要視されて踏み残しが減るということかと思う。
提出7(3時間42分): スコア 4,997,673
評価値を(min(x, 49-x) * min(y, 49-y))2に変更する。
後は乱数のシード変えたり、お祈り提出をするもスコアは上がらずに終了。
反省点
- 最初DFSを時間管理がしやすいようにstackで実装しようとしたが、無限にバグらせて時間を浪費した。結局再帰で実装した。4時間だとアルゴ力必要だよなぁ。。
- パスを部分的に改善は端から無理だと思って考えていなかったけど、それが正解だったらしい。そこら辺の判断ができないと上位行けない。。
AtCoder Heuristic Contest 001(AHC001) -AtCoder Ad- 参加記
問題
結果
989,207,448,084点で33位。パフォーマンスは2385。橙は相当厳しい…。もう少し上に行けるようになりたい。
方針
- 一つの長方形の1辺を拡大
- 一つの長方形の1辺を拡大・1辺を縮小
- 二つの長方形が縦(横)に接していたら横(縦)に接するように変形
の3つの近傍を作り、「1・2で山登り、3で焼き鈍し」を交互に行った。
近傍1
一つの長方形の1辺を拡大する。拡大する方向に別の長方形がある場合は、その長方形は縮小させる。高速化として、各長方形をxmin, xmax, ymin, ymaxそれぞれをキーにしてhash mapに登録しておき、長方形同士の接触判定をするようにした。
近傍2
一つの長方形の1辺を拡大・1辺を縮小する。近傍1だけだと、面積は長辺と短辺の長さ分の増加に限定されるので、長辺-短辺の増加も行えるようにした。
近傍3
二つの長方形が縦(横)に接していたら横(縦)に接するように変形する。近傍1・2だけだと局所解にハマるので、この近傍で焼き鈍しを行った。変更後の1辺の長さは最初は適当なルールで固定にしていたが、乱数で決めるようにしたらスコアが伸びた。1辺の長さを決めたらもう1辺の長さは、他の長方形に干渉しない範囲で目標面積にできるだけ近づける。
その他
- 近傍で選ぶ長方形の候補を、最初は閾値よりスコアが悪い長方形としていたが、近傍1・2ではほぼ全てを候補、近傍3では悪い方から一定の個数とするとスコアが伸びた。
- 他の人の解法によく出てくる、kick(長方形を破壊して再構築する)も途中まで採用していたが、kickを無くして近傍3の試行回数を稼ぐ方がスコア伸びたので不採用とした。
- 面積が大きい長方形の配置が大変なので、大きい長方形を先に配置してしまえば良いかと思ったがスコアは悪くなった。
反省点
- ビジュアライザは配布されたもので最終状態しか見てなかったので、途中の状態をちゃんと可視化して考察するべきだった。そのあたりが素早くできるようになりたい。
- 最終的な方針が固まったのが終了数時間前だったので、パラメータ調整が全くできなかった。最終日はパラメータ調整に費やせるくらいのスケジュールで進めたい。
