Skip to content

RECRUIT 日本橋ハーフマラソン 2026冬(AHC060)

問題概要

  • https://atcoder.jp/contests/ahc060
  • N頂点M辺の無向グラフがあり、各頂点は「アイスクリームショップ」か「アイスクリームの木」になっている
  • 「アイスクリームの木」では、その木に設定された種類(バニラアイスかストロベリーアイス)が収穫できる
  • アイスクリームショップからスタートし、以下の行動をTターン繰り返す
    • 行動1(移動, 収穫/納品): 隣接頂点に移動(ただし、1つ前の頂点には戻れない)し、頂点に応じて、以下を行う
      • アイスクリームの木: アイスの収穫し、手元のコーンに積んで多段アイスにする(WとRからなる文字列で表現する)
      • アイスクリームショップ: 手元の多段アイスをすべて納品する
    • 行動2(味変): アイスクリームの木、かつ、設定がバニラアイスになっている場合、ストロベリーアイスに設定し直す(次の訪問から有効)
  • 各アイスクリームショップに納品される多段アイスの種類数を最大化せよ

時間

  • 4 時間

個人的メモ

アイス文字列の長さ

  • コンテスト開始後早い段階で15万点付近が出てたりして、おおよそ必要な納品時のアイス文字列の長さが見積もれる
  • 順位表は150ケースでの結果なので、1ケースあたり1000点ぐらいで、T=10000ターンなので、重複納品がないならば、アイス文字列の長さは平均長さ10以下ぐらいを狙う必要がある
    • 平均長さ9なら166667点、平均長さ8なら187500点ぐらい
  • 味変にもターンを使うので、それを考えると、平均8〜9ぐらいの長さになる必要があり、アイス文字列を伸ばすことで重複しないようにするアプローチはあまり有効ではない

Uターン禁止制約

  • 「直前の頂点には戻れない」という制限がある
  • (解説放送) もし許すと、長さ4のサイクルで任意のアイス文字列が生成可能

アプローチ

  • 「経路をどう選ぶか」と「味変タイミングはどうするか」をある程度分けて考えるのが良かった模様

適当な確率で味変 + BFS

  • あるショップにいるとき、他のショップまでのパスをBFSで生成し、できるだけ短い、かつ、そのショップにないアイス文字列が生成できるようにする
  • 長さを制限して、そこまでで重複なし納品ができるパスが見つけられなければ、適当に味変を入れて移動、を繰り返す
  • 見つけられない時その移動は無駄にしてしまうが、頂点を最後に訪問したタイミングを覚えておけば、その通った時に味変していたとして、今回のパスから有効にすることもできる(過去改変)
  • ここらへんの貪欲をどうするかはバリエーションがありえて、やりかたによってかなり良いスコアが狙えた模様

味変タイミングの探索

  • 味変は、いつ・どこを、するとよいかがよくわからないし、その味変ペースも重要
  • 「いつ赤に変えるか」を状態にして、焼きなましなどで探索する
    • tターン以降に訪問して頂点がWだったら必ずRにする
  • ターンが多いので、試行回数があまりできない(1000回ぐらい？)が、それでもスコアがでるよう
  • 前処理で、各ショップから11ターン以下で移動できるショップまでのパスを全列挙しておく、とか

1手ずつ進める貪欲/ビームサーチ

  • ショップ間パスではなく、1手ずつ進める貪欲/ビームサーチ
  • 状態重いかも？と思ったけど、差分更新ビムサができるよう
  • 評価関数の調整や重複排除など気をつける必要がある

その他

  • 評価関数ベースでランダムウォーク
  • 味変を「k手分」とみなして扱う
  • ローリングホライズン的に解いていく
  • 味変する確率を段階的に高くしていく
  • ターンと頂点でDPする

その他

アイス文字列の持ち方

  • 文字列として持つと無駄が多いので、0,1のビット列で持つとサイズを小さくできる
    • 長さも長くしないなら、16bit整数(ちょっと怪しいかも)や32bit整数で持てる
  • ただ、WとWWの区別がつかないので長さが分かる情報を入れる必要がある
    • 長さを別に持つ(32bitなどだと上の方は空きがあるのでそこにいれるとかも？)
    • (解説放送)
      • 先頭を1にして長さを区別する
      • 長さごとに別配列で管理する
      • bool配列で、該当する数字のindexのところを1にすることで保持

解説

(50位まで&発言を見つけられた方のみ)