ごらくらいふ

プログラミングしたりゲームしたり

AHC030 に参加した

AtCoder 感想 雑記

AHC030 に参加してみて、ついでに参加記録を書いてみようと思い立った。

問題

atcoder.jp

  • N x N マスの島に埋蔵されている油田プールの形状を答えよ
  • 油田はポリオミノ型をしており、事前に形状と向きが判明している
  • 掘削は確定した埋蔵量が得られるが、コスト 1 かかる
  • 占いは指定したマスの集合の数に基づいたコスト 1/√k で合計埋蔵量を得られるが、マスの数が増えるほど情報の分散も大きくなる

単純に解く

  • サンプルコードいわく、全セルを一度掘ってもコスト超過になることはない
  • (0, 0) から1セルずつ掘る
  • Score: 12_696_000_000

https://atcoder.jp/contests/ahc030/submissions/50134670

油田だけを掘れば十分である

  • ルールによれば、ポリオミノ油田の形状は4セル以上かつ隣接している
  • BFSで油田だけを掘削すれば、無駄なコストを削減できる
  • (0, 0) から順番に掘っているので、まだコスト削減の余地がある
  • Score: 9_369_000_000

https://atcoder.jp/contests/ahc030/submissions/50198163

占うコスト感を考えた

  • まとめて占ったセル数の平方根だけコストが安くなる
  • 当たるも八卦当たらぬも八卦
    • エラー率がある (0.01 ~ 0.20)
  • 飛び飛びで選んだほうがいいのか？まとめたほうがいいのか？
    • 3x3 の四隅だけを選択して占っても、2回占えばコストが1になる
    • 3x3 全部を選択すれば、3回占ってコストが1になる
    • 不安定なのは変わらない
  • 「kが16で、埋蔵量が0のとき…エラー率は…」と事例別に計算してみて、16セルは埋蔵量0でさえ完全な精度は出ないが、十分に埋蔵量を感じられそうだった
    • 肌感として、2x2 や 3x3 は占う回数も多くなり、総コストが高すぎると思った

新しい油田を少し効率的に探す

失敗：占う軸を増やす

  • 16セルずつの占いを、水平方向の線形に選んだセルだけで行っていたため、鉛直にも追加してみた
  • 結果はスコアの悪化となり、目をそらしている問題点がこっちを見つめている
    • 続きから占う実装になっていない
    • 水平と鉛直を交互に占っているため、重複して占っているセルがある
  • ただ、占いの端数が綺麗になったので、占いが油田を見逃すことはなくなったらしい
    • 中途半端なセル数で占わないため
  • Score: 7_822_500_000
  • https://atcoder.jp/contests/ahc030/submissions/50202670

ABC340 に参加する

事前に占って素早く油田を探す

  • ABC340 で「そういえばヒープ使えば優先度順に取り出せるな」と気づく
  • 4x4 の区画であらかじめ占い、濃いところから油田を掘り返す
    • ようやくコスト計算に平方根を使う出題意図に沿ってきた
  • 区画を掘り返すときも渦を描くように、外周から＆各辺を均等に掘るようにした
  • この時点で、"無駄な空白セルを掘らない"というコスト削減は限界になったと判断した
    • ワーストケースでもほぼ無駄がない
  • Score: 6_714_250_000
  • https://atcoder.jp/contests/ahc030/submissions/50205955

ToDo

  • 空白セルの見込みが油田より少ない見込みがある場合は？
    • 油田が重なっていないケース
    • 油田と違って空白地帯は飛び地セルがありうる
      • 回答失敗は十分ありうる
      • 濃厚に重なってるセルの隣に空白セルがあると最悪
    • 油田の重なりもある程度占える
      • 確定している空白セル数にどれだけ上乗せするか
    • 空白をすべて埋めるか、縁取りするか
  • 油田の縁取りをする？
    • 2x2 の中央を基点にすれば次に確認する区画がわかる
      • 飛び地を掴んでしまった場合は？
        • 最も端の地点を確認すれば、ドーナツの穴か輪郭か判断できる
    • 判明している油田情報とのすり合わせをしなければ答えは分からない
      • 端からマッチしていく
        • ないはずの場所に油田がある->他の油田があるかも
        • あるはずの場所に油田がない->それはマッチしない油田
      • ちぎれた油田プールを補完していく縁取りが必要になるだろう
        • 完全に埋まってる油田は？ -> 回答時には無視できる
          • 行き場の分からない油田がある中、どうやって探査を終了する？
    • 油田プールの中に隙間があったりするとめんどい
    • 油田のBFSよりコストが安くなりやすい
      • 小物は面倒
        • 細い油田の場合、角の縁取りでコストがむしろ増える
  • 意外とエッジケースが来ない
    • 油田の幅と高さがNと一致して自明になっている油田
    • 油田の幅と高さがNの半分を超えて自明になっている油田のマス

しめきり。

  • 締め切り時点で、順位は 382位 でした。

最終結果

最終結果は、439位でした。