Skip to content

第一回マスターズ選手権-予選-

問題概要

  • N*Nマスの盤面があり、マスの間には壁がある場合がある
  • 各マスには1〜N^2 の数字が1つずつ書かれており、以下の一連の操作を最大で4N^2 回行う
    1. 高橋くんと青木くんの現在位置にかかれているマスを交換したければ交換する
    2. 高橋くんを現在の位置の移動可能な隣接マスへ移動したければ移動する
    3. 青木くんを現在の位置の移動可能な隣接マスへ移動したければ移動する
  • スタート地点は好きな場所に設定できる
  • 隣接マス(壁がない隣接)の数字の差の二乗和をスコアとするとき、これをできるだけ小さくせよ

時間

  • 360 分

個人的メモ

問題固有の性質

  • 移動回数の4N^2回から、1マスあたりを修正するの使える手数は平均4回
  • 隣接マスとの差が大きいマスを直す方が改善の寄与が大きい

アプローチ

  • 貪欲(強い貪欲)
    • 任意の2地点について、「その2地点をswapしたときのスコアの改善度合い/現在地からそこまでの移動距離」(ターンあたりの改善量)で最大のものを貪欲に選ぶ
      • 盤面が大きいと厳しいので、それぞれの一定距離内のマスについてだけ計算
  • 理想状態を作って、クイックソート的に処理
    • 焼きなましで理想状態を作る(大域的に良い状態にできる)
      • 近傍は2点swap、など
      • 目的関数を2段階にして、最初は差の和で、次に実スコアで最適化、とかも？
    • クイックソートのように、番号の範囲を半分に分けて、範囲内の数字が矛盾する地点を交換するのを再帰的に繰り返す
      • 矛盾する地点への移動経路は、近いところに移動するgreedyか、TSP、など
  • 経路を固定してswapするかどうかを焼きなまし
    • DFS木、オイラーツアー、などで全部のマスを通るパス生成
    • 問題の制約から、全部のマスを通る、行って戻って来るパスを2周できる
  • 経路を固定しないで焼きなまし
    • swapする地点のペアをリストに持って追加削除交換を焼きなまし＋移動経路は最短経路(or TSP)
  • 目標盤面との二乗誤差を評価関数とした先読み木上ビームサーチ

tの生成

  • 盤面は、20種類
  • 解説放送によると、形状については以下のようなものが用意されていた
    • 直線
    • 木
    • 十字、部屋
    • 渦巻き、2x2マスで渦巻き
    • 過去の問題での壁生成方法

解説

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