Circles of Inversion 解説

• 魔法陣は常に 3 個
  → 「使った魔法陣が出発点へ移る」と考えればよい
• 転移で動く量は d = C − P の 2 倍
  → 座標の偶奇は変わらない
  • 偶奇を変えるには歩くしかない
• 歩くだけだと 1 区間あたり平均 手
  • 1 ケース 151 点 (150 ケースで 点)

• 目的地を順に 1 つずつ訪れる
• 各区間で、次の 4 通りから手数が最小のものを選ぶ
  • 歩くだけ
  • 魔法陣 1 つで転移してから歩く (3 通り)
• 結果: 1 区間 手 (歩くだけ 手)
  • % の区間で転移を使わない

• 魔法陣 C ごとに、目的地 G にぴったり転移できる場所 X = 2C − G まで歩いて転移する
  • 「歩くだけ」と合わせた 4 通りから、手数が最小のものを選ぶ
  • 手数は順向き貪欲と同じ式 |2C − P − G| + 1。違うのは使った魔法陣の行き先 (P ではなく X)
• 結果: 1 区間 手、% の区間で転移を使わない

• 魔法陣が盤面の端に溜まる
  • 使った魔法陣は出発点へ移る
    出発点 (P や X) は盤面全体に散らばる
  • 転移先は、魔法陣をはさんだ反対側
    → 端の魔法陣を使うと、ほぼ盤外
  • 端に置かれた魔法陣は二度と使えず、そのまま残る
• 端から 8 マス以内の魔法陣: 順向き貪欲 %、順向き貪欲 2 % (一様分布なら 23%)
• その結果、区間の始めに盤内に着地できる魔法陣は 3 個中平均 個しかない (順向き貪欲)

• 順向き貪欲と同じことを逆向きに行う
  • 逆順に目的地を 1 つずつ訪れる
  • 各区間で「歩くだけ」と「魔法陣 1 つへワープしてから歩く」のうち、手数が最小のもの
• 逆向きの初期配置: 逆順で次に訪れる 3 つの目的地に置く
• 結果: 1 区間 手
  得点は順向き貪欲の約 倍

右図: seed=0 の区間 26〜29 を最後から逆向きにたどる。青い輪が次の目的地、紫の点線が魔法陣の移動

• 逆向きの転移先は魔法陣のマスそのもの
  • 今どこにいても、3 個のどれかへ 1 手 (+ 偶奇合わせ 0〜2 歩)
  • 盤外に出ない
• 順向きの転移先は魔法陣をはさんだ反対側
  • 今いる位置で変わり、遠い魔法陣ほど遠くへ飛ばされる
  • 盤外に出やすい

右図: 同じ配置 (● 高橋くん、紫の円 魔法陣) から転移を 3 回まで続けたときの着地点

• 高橋くん・魔法陣 3 個・目的地を一様ランダムに置き、1 区間の最良手数を 2 万回平均
• 順向き: 盤内に着地できる転移は 3 個中平均 個。着地点もランダムな位置で、歩きはあまり減らない
• 逆向き: 3 個とも使える。目的地に一番近い魔法陣へワープすれば、歩きがほぼ半分

• 順向き: 出発点へ移る
  • 端に溜まって使えなくなる
• 逆向き: 中点へ移る
  • 使うほど中央に集まる
  • 中央の魔法陣は、どの目的地にもそこそこ近いワープ先

• ワープを 3 回まで続けてから歩く
  • 1 + 3 + 9 + 27 = 40 通りを全部試す
  • ワープのたびに偶奇合わせ 0〜2 歩
• 選び方: この区間の手数 + 先 12 個の見込み手数
  • 見込み: 各目的地で「歩くだけ」と「一番よい魔法陣へワープして歩く」の安い方
  • 魔法陣の移動も反映し、先の目的地ほど 0.8 倍ずつ軽く数える

• 中央寄りへ歩いてから、転移で目的地の近くへ跳ぶ
  • 転移の出発点は盤の端から平均 マス
    (目的地は平均 20.8 マス)
• 着地した後に、偶奇合わせの 1〜2 歩
• 区間 26〜29 は、歩くだけなら 手 → 手
  • (W: 歩く手数、J: 転移)
  • 、、

順向きの改良版・ビームサーチ: 逆向きと同じ探索・評価を順向きに行ったもの

• 同じ方法でも、向きを変えるだけで得点が 3〜10 倍
• 探索を強くするより、向きを変える方がずっと効く
• 逆向き貪欲の解も、順向きに見れば順向き貪欲 2 と同じ「歩いてから転移」の形。違うのは、そこに魔法陣があるかどうか
• 順向きビームサーチは魔法陣を端に溜めずに済む (端から 8 マス以内 %) が、1 区間 手でランダムな配置と同じくらい

• 状態: 逆向きの現在地 (直前の目的地) と魔法陣 3 個の位置
• 遷移: 逆向き貪欲の改良版と同じ 40 通り
• 評価: ここまでの手数 + 先 8 個の見込み手数
• ビーム幅 2,500
• 重複除去: 魔法陣 3 個の座標を 2 で割ると同じになる状態は、良い方だけ残す
• 初期状態: 逆順で最初に訪れる 30 個の目的地から 3 個を選ぶ全通り (4,060 通り) を評価し、上位から始める

実行時間はローカルで 12 ケースを並列に実行したときの平均

重複を除かないと、幅 2,500 で 点 ( 秒)