アジの開きを閉じる。

競プロ(AtCoder)中心のブログ

【最終提出編】AHC018 参加記 (RECRUIT 日本橋ハーフマラソン 2023冬

AHC 備忘録

2023/02/18(土)12:00 ~ 02/26(日)19:00 の約1週間，RECRUIT日本橋ハーフマラソン2023冬(AtCoder Heuristic Contest 018) が行われました。

AHC参加3回目，レート帯は茶色(Algorithmは水色)の私は暫定177位，最終188位(パフォ1771)でした。自分の中では3回目にしては好成績だと思ったのと，せっかく1週間頑張ったので参加記を書きました。

 

参加記は2本あります。

この記事は最終提出した解法の説明です。

コンテスト期間中に何をしていたかに興味のある方は，【日記編】AHC018 参加記 (RECRUIT 日本橋ハーフマラソン 2023冬) へどうぞ！

 

目次

 

 

seed=0

 

戦略

ざっくり言えば，「代表点を試し掘りして周囲の硬さを推定し，ダイクストラ」。

  1. 13×13の代表点と家を試し掘り。
    • 累計powerが{32，64，128}になるように順に掘る。壊れたらその時点の累計powerを記録。128でも壊れなければ5000(最大硬さ)と記録。
  2. 結果をもとに周囲の硬さを推定。
    • 各マスの硬さ推定値は，そのマスを中心とする(ユークリッド距離で)半径 ⌈(N/13)*√2⌉ 内の円にある代表点・家の硬さの重み付け平均値。
    • (推定値)=Σ{(重み)*(地点の硬さ)}/(重みの総和)
    • (重み)=(地点とのユークリッド距離切り上げ)*(27/100)
  3. 水流マス(その時点で水が流れているマス)へのコストが最も小さい家と，その水流マスまでのパスを探す。
    • すべてのマスを頂点とするグラフを考える。
    • 各頂点から上下左右へ，終点の堅さ推定値(代表点や家なら記録した値)をコストとする有向辺を張る。
    • 各家について，家を始点とするダイクストラを行い，現時点の水流マスのうちパスが最小コストのものを取得。
    • すべての家の中で水流マスへのコストが最小のものについて，経路復元により実際に通るマスを取得する。
  4. 取得したパスを破壊する。
    • 掘り方は次項。
  5. 3, 4を，水が流れていない家が無くなるまで繰り返す。

 

 

掘り方

ざっくり言えば，「小区間に分けて柔らかい方から掘る」。

  1. 取得したパス(家から水流マスまでの掘るマスの列)を前から21マスずつの区間に分ける。
    • [1, 2, ..., 21], [21, 22, ..., 41], [41, 42, ..., 61], ...
  2. 各区間で常に柔らかい側から掘る。
    • 区間[a, a+1, ..., b-1, b] として，両端のマスa, bを掘る。このとき，累計powerが{32, 64 ,128, 256, 512, 1024, 2048, 5000}になるように順に掘る。壊れたらその時点の累計powerを記録。
    • l=a, r=b, lpower=(aの累計power), rpower=(bの累計power) と初期化。
    • r-l>1の間，以下を繰り返す
      • lpower<rpowerなら，l++した後のマスlを掘る。
        • powerは，一発目はlpowerで削り，壊れなければ壊れるまで50で刻んでいく。
        • lpower=(累計power) と更新。
      • そうでないなら，r--した後のマスrを掘る。
        • 掘り方，rpowerの更新は上と同様。

 

 

結果

上手くハマった例(seed=5)。平坦な岩盤が多いと良い解法っぽい。

成績表

素点6,166,757点，暫定177位，最終188位。

 

補足説明

  • 戦略について
    • 家まで水を引くパス上の岩盤は多くの場合硬さ250以下程度だった。(seed=0では通っているが)それより硬い岩盤はほぼ通らないので，詳しい硬さは知る必要性はあまりない。これを踏まえ，試し掘りの上限は少し厳しめに128とした。
    • 家のマスは必ず掘る&後で同じ掘り方をするので，先に試し掘りをして推定の材料とした。この情報の有無がどう得点に繋がったのかは調べていない。
  • 掘り方について
    • この程度の幅の小区間に分ければ，区間内の硬さの分布が概ね「山(途中が硬い)」「均一」「谷(途中が柔らかい)」「坂(一方が高い単調な傾斜)」のどれかになる。極値のあるn次関数(n>=3)のグラフみたいな分布にはほぼならない。
    • 常に柔らかい側から掘り，その硬さを次のマスの一発目にすることで，「山」「均一」「坂」のコスト削減ができる。
    • 「谷」は無駄なコストが生じてしまう。ここは妥協。終了後に他の方の解法を見ると，前の累計powerの8割程度で次を掘っていくと効率が良いらしい。
  • 各パラメータの値は数個を試し，提出してみて最も良かったものを採用。
  • 手元が「大量のサンプルケースを一瞬で試せる」環境ではなかったため，30分おきに提出→素点で評価するしかなかった。パラメータ調整は詰め切れていない。
  • seed=0だけ見ると硬い岩盤を突っ切ったりしていてスコアが悪そうだが，テストケース全体で見ると良いらしい。

 

 

コメント

  • 学術的に高度なアルゴリズムの使用や詰め切ったパラメータ調整，サンプルケースの統計を取らずとも青パフォを出せた。今回の問題に限った話かどうかはこれだけでは何も言えないが，その一例は示せたのではないかと思う。ABCで鍛えた知識をベースに考察とアイデア次第で誰でも高いパフォーマンスは狙えると思った。もちろん，ヒューリスティックで用いられる手法(山登り法など，焼きなまし法など)を知っている方がもっと強いと思う。