HACK TO THE FUTURE 2023 本戦オープン参加記(7位)

競技プログラミング

atcoder.jp 1,297,045点でオープン7位でした。（点数を得た参加者は83人）。

ビジュアライザも使いやすくて楽しいコンテストでした。問題が面白くて、レートも賞金ももらえないのに6時間くらいやってしまいました。

問題概要

Dowsing Rodという問題でした。

円形の島の中を探索して宝を探します。ある点を調査すると半径D以内に宝があれば発見、なければ距離に反比例する確率で選ばれた未発見の宝の向きが誤差付きで分かるので、できるだけ少ない回数で全部見つけなさいという問題です。

インタラクティブで情報が隠されていて誤差もあるタイプの問題です。HTTFっぽい感じがしますね。

ビジュアライザはこんな感じ。

方針

  • ランダムに点をうち、その方向に一定歩幅で探索を進めていく
    • 初期点の決め方
      • 発見した宝が半分以下の場合は円周上のどこかからスタートする
      • 発見した宝が半分以上の場合は円の内側半径9割のうちどこかからスタートする。
    • 向きが逆転したら二分探索の要領で歩幅を0.5倍する
    • 直前の点よりもその前の点のほうが宝に近かった（1> <3 <2 のような）パターンが現れたら、同じ位置に戻るのを防ぐために0.8倍する
      • 0.5倍より0.8倍の方がスコア出るんですね
    • 歩幅が一定以下になると探索打ち切りでランダムに点を打つところからやり直す
  • 逆転判定の範囲は標準偏差が大きいほうが広がるようにした

悪いケースでも全ての宝を集められるくらいのプログラムになりました。

実装

特に面白い実装はありませんが、各関数が更新する変数は少ないので読みやすいはず。

atcoder.jp

試したがうまくいかなかった方針

  • 円周上に100個の点を打つと直線が100本得られるので、交点の座標を求めて近いものをunionfindする。誤差の前に無力でした。
  • 直前の点と大きく向きが違う場合に無視する。手損でした。