Skip to content

ALGO ARTISプログラミングコンテスト2024夏(AHC035)

問題概要

  • N * Nマス(N=6)の畑があり、マスに種子を植えると、隣り合うマスについて1つの種子の特性を受け継いだ種子が2*N*(N-1)個収穫できる
  • 各種子は、M個(M=15)の評価項目があり、2つの種子からできる新しい種子は各評価項目についてどちらかの値をランダムに選んだものになる
  • 最初に2*N*(N-1)個の種子が与えられるので、T回(T=10)の収穫後にできるだけ評価項目の合計が大きい種子を作り出せ

時間

  • 4 時間

個人的メモ

問題固有の性質

  • 最終的に、最強の種子を1個作り出せば良い
    • 最初の種子集合での各評価項目の最大値を持つような種子が最強で、1,000,000点が得られる
    • (盤面全体を最大化するわけではない)
  • 評価項目のいずれかで最大値を持つ種子はかなり大事
    • それが消えてしまうと最終的に可能なスコアの最大値が減少してしまう
  • 植える種子はN*N個なので、種子のうち半分程度は毎回破棄される

植えた種子の評価項目が次の世代に引き継がれる可能性

  • 植えた種子の評価項目xが次の世代に残る可能性は、基本的には上下左右との4つの種子に引き継がれるため、1-すべての種子で引き継がれない½^4=93.75%ぐらいとかなり高い
  • そのため、ある項目について最大値に近い値を持つ種子同士を組み合わせて残すことよりも、異なる項目で強い異種同士を組み合わせてより強い種子を作るのを狙う感じでよい模様

評価関数ベースのアプローチ

  • 種子や植え方に関する評価関数を考え、各ターンで評価関数が高くなるように植える

種子に関する評価関数

  • 平均的に高い種子よりも、どれかの評価項目で最大値(またはそれに近い値)を持つような種子が重要
  • そこで、最大値に近いところが大きく評価されるような評価関数を考える
  • n乗和
    • 最大値付近以外のはほとんど無視しても良いため、差をつけるためにn乗した値を使う
      • 2乗、3乗、10乗、25乗とか
  • 最大値(またはそれに近い値)を持つか、または、ボーナスを加える
    • 最大値なら1、そうでないなら0
    • sigmoid関数
    • 大きい方*0.8+小さい方*0.2
    • など
  • 各項目の順位
  • 目標との差
    • 最大値との差
    • 目標ベクトルとの差
  • 特定の評価項目の最大値付近の種子の数が多すぎる場合はマイナス
    • 他の評価項目の評価値が高い種子が消えないようにしたい
  • ターンによって値を変える
    • 最後の方のターンになるにつれ、最大値以外の値も重要になるので、ターンに応じて補正を変える

植え方に関する評価関数

  • 植えた場合の隣接種子(ペア)との組み合わせに対する評価関数を考える
  • ペアの各評価値での大きい方の値の合計(の総和)
    • 理想的に評価項目が良い方を引き継いだ場合で考える
  • 内積(の総和)
    • ベクトルとして見たとき、内積が小さいほうが異なる種子同士の組み合わせになっていてよい

植え方

  • グリッドの端の方だと種子の数が少なくなってしまうため、「強い種子」はできるだけ中心付近に置きたい
  • グリッドの中心付近から、貪欲に評価値が高い種子を選んで植える方法でも強い
    • 渦巻き配置にしていた人が多いっぽい
  • 貪欲法だと時間はかなり余るので、焼きなまし、など
    • 種子の交換、2点位置交換

その他

最終ターンだけ別処理

  • 最終ターンは、どれかのペアが最強の種子を作れていればよいので、できるだけ最強の種子の生成確率が高そうな配置にする
    • 最大値を残すというより、できる種子の期待値が最大になるようにする

logsumexp関数 / Smooth maximum

AI活用

  • 渦巻き配置などパターン生成にchatGPTなどを使う

解説

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