Skip to content

TOYOTA Programming Contest 2023 Summer (AtCoder Heuristic Contest 021)

問題概要

  • N(=30)段のピラミッド型にボールが並んでいる
  • 各ボールには、0からN*(N+1)/2-1の数字が書かれており、すべてのボールの数字は異なる
  • 1回の操作で、あるボールについて、隣接する左上、右上、左、右、左下、右下の6方向にあるボールと入れ替えられる
  • 最下層以外で、どのボールについても左下と右下のボールの数字よりも小さい状態になるようにしたい
  • できるだけ操作回数を少なくなるような操作列を求めて、目的の状態になるようにせよ

時間

  • 4 時間

個人的メモ

  • いろいろ貪欲解を試して、良い性質を押さえて、さらなる工夫を試す、というのができるとよかった模様
  • 特に、今回は強い貪欲解があり、それを見つけられるだけで予選通過ラインの200位以上が取れていた
    • 重要な性質を押さえられてない状態では、高スコアを出すのは難しかった

問題固有の性質

  • ソートっぽい雰囲気
    • バブルソート的な感じ？
  • 手順が間に合えば、上から順番に番号を埋めていくことで条件を違反している数を0にできるので、50000点以上は取れる
    • 基本、間に合うので、最終状態で、条件を違反しているようなものはないものとして考えるとよい
  • ボールの番号は、最終状態では、小さいものが上の方、大きいものが下の方になるはず
  • 隣接2ボールのswapは、小さいものが上に＆大きなものが下に来るようなものを同時に行えるようなものが効率がよい
    • 横方向のswapは判断が難しい

有効な最終状態(完成状態)

  • 条件の「どのボールについても左下と右下のボールの数字よりも小さい状態」というのを満たす状態として、自明には、上＆左から0,1,2,...という状態になっていれば満たせている

  • しかし、これ以外にも条件を満たす形があり、上の図のような「下部中心に向かって数字が大きくなるような配置」なども条件を満たせている
    • むしろ、こちらの形になる方が手数は少なくなるため、上から行を順番に埋めていくようなアプローチではスコアが出せなかった
    • 一番下の行に「29」番のボールが来るようなのもvalid
    • 問題文にある4段の場合のgif動画の最終状態も5が最下段に来ているが有効なケース
  • 解の形を決め打ちせず、いろんな貪欲解がうまくいくかを試せていれば、気づけていたはず、、、

性質

  • 最終状態では、ある番号について、そこより上方向にひし形の領域では、その数字よりも小さいもののみで構成される
  • ピラミッドの端の方では、その数字より小さいボールの数が少なくて済むため、小さい番号のボールが下の方に来てもvalidになる
    • 下の方にある小さい番号のボールの移動距離が短くて済む
    • 端の方が小さい数字でも許されやすいので、全体的な形として「下部中心付近に数字が大きいものが集まっている」状態になるのは自然

貪欲解

  • いくつか単純なルールを繰り返す貪欲解を試すことで、良い性質を探れる(ここで、最終状態を決め打ちしないことも大切)
    • 上/下、右/左から順番に「違反しているもの」をswapしていく、ことを繰り返す
    • 小さい/大きい番号のボールから「違反している場合swap」を繰り返す
    • あるボールについて、上/下のペアで大きい方/小さい方とswap
    • 差が大きいペアをswap
    • 上/下方向だけ使う、横方向も使う
    • できるだけ左右に寄せる
    • など

停止性

  • 繰り返す系の解法では、最終的に停止するか？も問題になる
  • 解説放送では、ポテンシャル\sum_x h(x) * b(x)を考えて、swapによって増加して、これは有限なので停止する、というのが紹介されていた
    • xはピラミッドでの位置、h(x)は位置xの高さ、b(x)は位置xのボールの番号
    • 違反しているところでは、上側が大きい番号で下側が小さい番号なので、h*大+(h+1)*小がh*小+(h+1)*大となって大小関係的には後者が大きい

番号が小さい方から/大きい方から、の違いの考察

  • 解説放送では、「ある行まで決まったとして、残りのボールがランダムに配置されていると仮定した場合」でおおよその期待step数を見積もる方法が紹介されていた
    • 小さい方からの方が期待step数が小さい
    • (ただし、実際はランダムな配置ではないなどで、あくまで近似の値)

強い貪欲解(13,426,585点)

  • 「小さい番号から、上に向かって番号が大きければ交換する、を繰り返す。上のどちらも大きい場合は、番号が大きい方と交換する」という貪欲が強い
    • 「小さい番号から」「大きい番号と交換」などが強い性質
  • これは、順位表で、開始後早い段階から同スコアで並んでいることから、シンプルで強い貪欲解がある可能性があることを示唆
  • 平均89,511点/ケース
  • (上図はこの解法でのSeed=0の最終状態)

貪欲解の改善

  • 上の強い貪欲解や「差が大きいペアをswap」などが良い解を作っているので、これを改善することを考える
  • 強い貪欲解法で考えると、小さい番号のボールから処理するとして、ボールの動かし方に探索の余地がある
  • あるボールを上に持っていくときの経路で、貪欲解では直近しか見ていないが、経路上で番号が大きいものが多いほどよさそうに思われる
  • また、経路をどうするかで、最終地点の位置や他のボールの配置も変わりうるので、後の方で嬉しい配置になるものを選ぶのも大事そうに思われる

評価値が良い経路を選ぶ

  • ボールを上方向に動かすときの経路で、できるだけ大きい番号を多く下にさげるような経路を探したい
  • DP/ダイクストラ等で、ピラミッドの上方向に向かって探索して、経路復元
  • 辺や頂点の重みは、基本は、「移動回数が最小で、番号の大きさの合計が一番大きいもの」的な感じだが、他にもバリエーションが考えられる
    • 通った数字の和/平均値
    • 移動回数(swap回数)
    • 移動方向に応じた重み(横方向も許すが大きめの重みを追加、など)
    • 最終地点の中央からのズレ具合/端への近さ
    • など

盤面の評価値が良くなる状態を選ぶ

途中状態を変える

  • swapするときに一定確率でswapするものを変える、乱択
    • 全体で適用、最初の方だけ適用、など
  • 手順の途中を変えて、それ以降は貪欲したもので完成させ、山登り
    • greedy解を評価関数にする
    • 「過去に戻ってワープ/過去改変」(解説放送)
      • ある経路のボールの移動について、対象のボールの隣接ボールのswapを先におこなっておくと、1手で移動するボールを入れ替えられる
      • 条件付き「離れたボールの交換」的な感じにできる

その他

完成形を焼き鈍す

  • AHC011では「完成形を決めて操作列を作る」というアプローチが強かった
  • 今回、同様のアプローチが考えられたが、実際に良いスコアが出るかは見積もるのが難しかった
    • (というか、完成形を作るところからうまくいかずコンテスト時間を無駄にしてしまっていた、、、)
    • 初期状態からスタートして2点swapとかだと違反数を0にできないし、自明な違反0の状態から違反0を保ったままの移動だとあまり盤面が変わらない
    • さらに、単純に各ボールの距離合計とかを最小化しようとしても、実際は移動によって最初の位置からずれるため結構無駄移動が発生してしまっていた
  • 解説放送では、スライドパズルの場合は、今回とは違って順番に決めるのが難しかったが、今回は順番に決めていけたり、決めたものが後の操作で邪魔にならないなどの良い性質がある、など違いがあったことが紹介されていた
    • 実装量も多く、うまく動くかわからないため、結構博打なアプローチだった

ビジュアライザ

  • ボールのクリックで経路の表示のON/OFFが切り替えられた

解説

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