AHC035解説

AtCoder Heuristic Contest 035（ https://atcoder.jp/contests/ahc035 ）の解説放送で使用した解説スライドです。

Transcript

1. AHC035 解説 2024/7/21 writer : terry_u16
2. 考察
3. 考察：どのような種を残すべきか 最終ターンは単純に種の価値を最大化すればよい 途中のターンはどのような種を残していくべきか？
4. 考察：どのような種を残すべきか 平均的に高い種 一部項目が尖った種 価値 𝑉 = 347 価値 𝑉 = 286 平均的に高い種と一部項目が尖った種のどちらを残すべきか？
5. 考察：どのような種を残すべきか 各次元ごとに、最大値に近い値を持つ種を残していきたい （𝑥𝑖,0 = 100 の種を捨ててしまうと、二度と 𝑥𝑖,0 = 100 を作れなくなってしまう） 1個の種の要素が平均で2つの種に遺伝するので、うまく増やしていきたい ※ 𝑥𝑖,0 の値で色分け
6. 解法例の紹介
7. ① サンプルコード 左上から順番に並べるだけ 143,047,940点 （本番907位相当）
8. ② 価値の高い順に貪欲 種ごとに価値を計算して、価値の高い順に植えていく 植える場所は左上から順番 209,765,695点 （本番765位相当）
9. ② 価値の高い順に貪欲 種ごとに価値を計算して、価値の高い順に植えていく 植える場所は左上から順番 209,765,695点 （本番765位相当） 一番良い種が 2つとしか隣接しておらず もったいない！
10. ③ 価値の高い順に貪欲 種ごとに価値を計算して、価値の高い順に植えていく 植える場所は中央から順番 216,518,056点 （本番655位相当）
11. ④ 序盤は要素ごとに強い種を増やす 最初の3ターンは、𝑗 = 0, 1, ⋯ , 𝑀 − 1, 0, ⋯ の順に 𝒙𝒊,𝒋 が最大のものを植える 残りのターンは③と同様に価値の高い順に貪欲 251,547,278点 （本番243位相当） 𝑥𝑖,0 最大 𝑥𝑖,1 最大 𝑥𝑖,2 最大
12. ⑤ モンテカルロ 貪欲ができたので、モンテカルロに発展させてみる 最終ターンまで貪欲するモンテカルロを評価関数にして山登り 250,550,916点 （本番252位相当） あんまり強くない……
13. 植え方に対する評価関数 毎ターン植え方を焼きなます方針を考える。どのような評価関数が良さそう？ • 隣接する種のペア 𝑒 = 𝑢, 𝑣 に対する評価関数 𝑔 𝑒 を考えて、 全てのペア 𝐸 に対する 𝑔(𝑒) の和を焼きなましの評価関数 𝑓 𝐸 とする • ペア 𝑒 = 𝑢, 𝑣 のベクトルの要素 𝑥𝑢,𝑗 , 𝑥𝑣,𝑗 に対する評価関数 ℎ 𝑥𝑢,𝑗 , 𝑥𝑣,𝑗 を考え、 𝑔 𝑒 = σ𝑗=0 𝑀−1 ℎ 𝑥𝑢,𝑗 , 𝑥𝑣,𝑗 とする • 𝑓 𝐸 = σ𝑒∈𝐸 𝑔 𝑒 = σ𝑒∈𝐸 σ𝑗=0 𝑀−1 ℎ 𝑥𝑢,𝑗 , 𝑥𝑣,𝑗 • まんべんなく値の大きい種よりも いくつかの要素が突出して大きい種の方が評価が高い • 𝐦𝐢𝐧 𝒙𝒖,𝒋 , 𝒙𝒗,𝒋 よりも 𝐦𝐚𝐱 𝒙𝒖,𝒋 , 𝒙𝒗,𝒋 の方を重視したい （最終的に多数の種の価値の最大値で評価されるため） 𝑔 𝑒 ℎ 𝑥𝑢,𝑗 , 𝑥𝑣,𝑗
14. ⑥ 焼きなまし + 評価関数その1 要素ごとの評価関数を ℎ 𝑥𝑢,𝑗 , 𝑥𝑣,𝑗 = max 𝑥𝑢,𝑗 , 𝑥𝑣,𝑗 2 としてみる • いくつかの要素が突出して大きい種の方が評価が高い → 一応OK （2乗しているため） • min 𝑥𝑢,𝑗 , 𝑥𝑣,𝑗 よりも max 𝑥𝑢,𝑗 , 𝑥𝑣,𝑗 の方を重視したい → 一応OK （maxのみを考慮） 257,341,896点 （本番147位相当） 要素0 要素1 要素2 𝑥𝑢,𝑗 50 10 20 𝑥𝑣,𝑗 30 60 30 max 𝑥𝑢,𝑗 , 𝑥𝑣,𝑗 50 60 30 max 𝑥𝑢,𝑗 , 𝑥𝑣,𝑗 2 2500 3600 900 𝑔 𝑒 = σ𝑗=0 𝑀−1 ℎ 𝑥𝑢,𝑗 , 𝑥𝑣,𝑗 = 2500 + 3600 + 900 = 7000 0 10 20 30 40 50 𝑓 𝑥 = 𝑥2
15. ⑦ 焼きなまし + 評価関数その2 要素ごとの最大値を集めた目標ベクトルを 𝒚 = (𝑦0 , 𝑦1 , ⋯ , 𝑦𝑀−1 ) 、 目標との差分を 𝑎𝑗 = min 𝑦𝑗 − 𝑥𝑢,𝑗 , 𝑦𝑗 − 𝑥𝑣,𝑗 , 𝑏𝑗 = max 𝑦𝑗 − 𝑥𝑢,𝑗 , 𝑦𝑗 − 𝑥𝑣,𝑗 とし、 ℎ 𝑥𝑢,𝑗 , 𝑥𝑣,𝑗 = 𝛽 × 1 Δ+𝑎𝑗 + 1 − 𝛽 × 1 Δ+𝑏𝑗 としてみる 267,929,188点 （本番26位相当） 要素0 要素1 要素2 𝑥𝑢,𝑗 50 10 20 𝑥𝑣,𝑗 30 60 30 𝑦𝑗 70 60 50 𝑎𝑗 20 0 20 𝑏𝑗 40 50 30 ※ 𝛽, Δ はハイパーパラメータ 𝑔 𝑒 = σ𝑗=0 𝑀−1 ℎ 𝑥𝑢,𝑗 , 𝑥𝑣,𝑗 = σ𝑗=0 𝑀−1 𝛽 × 1 Δ+𝑎𝑗 + 1 − 𝛽 × 1 Δ+𝑏𝑗 0 10 20 30 40 50 𝑓 𝑥 = 𝑥2 𝑓 𝑥 = 1 Δ + 𝑦 − 𝑥
16. logsumexp関数 足し算とmaxの中間くらいの性質の演算が欲しい • 足し算だとmax以外の値も大きく影響する （最終的なスコア関数はmaxなのに……） • maxだと最大値以外は全く影響してこない （2番目・3番目の値もある程度考慮したい……） logsumexp関数という関数を使ってみる • HTTF2022で優勝したeivourさんが使っていた関数で、「滑らかなmax」が得られる logsumexp 𝑥1 , 𝑥2 , ⋯ , 𝑥𝑁 = 𝜅 log ෍ 𝑖=1 𝑁 exp 𝑥𝑖 𝜅 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 𝑓 𝑥 = max 𝑥, 5 𝑓 𝑥 = logsumexp 𝑥, 5 ※ 𝜅 は正の値を取るパラメータ
17. ⑧ 焼きなまし + 評価関数その3 評価関数を以下で定めてみる • 𝑓 𝐸 = σ𝑒∈𝐸 𝑔 𝑒 logsumexp𝑒∈𝐸 𝑔 𝑒 • 𝑔 𝑒 = σ𝑗=0 𝑀−1 ℎ 𝑥𝑢,𝑗 , 𝑥𝑣,𝑗 • ℎ 𝑥𝑢,𝑗 , 𝑥𝑣,𝑗 = 𝛽 × 1 Δ+𝑎𝑗 + 1 − 𝛽 × 1 Δ+𝑏𝑗 logsumexp 1 Δ+𝑎𝑗 , 1 Δ+𝑏𝑗 • 𝑦𝑗 = max 𝑖 𝑥𝑖,𝑗 logsumexp𝑖 𝑥𝑖,𝑗 279,183,266点 （本番1位相当） 評価値が最大の種以外は 評価の重みを減らしたい maxとminを いい感じに混ぜたい max付近の値が多い次元よりも max付近の値が少ない次元の方が maxを達成する価値が高い
18. ⑨ 最終ターンの期待値最大化 実は最終ターンの価値の期待値は厳密に求められる • 各ペア 𝑒 について、価値が 𝑣 未満の種が生まれる確率 𝑝𝑒,𝑣 を求めておく 𝑑𝑝 𝑗 𝑣 ≔ 次元 𝑗 まで見て、価値が 𝑣 となる場合の数 というDPを行うことで計算可能 • 使用するペア集合が 𝐸 のとき、最大の価値が 𝑣 以上となる確率 𝑞𝑣 は 余事象を考えることで 𝑞𝑣 = 1 − ς𝑒∈𝐸 𝑝𝑒,𝑣 となる • このとき、価値の期待値は σ𝑣 𝑣 𝑞𝑣 − 𝑞𝑣+1 = σ𝑣 𝑞𝑣 = σ𝑣 1 − ς𝑒∈𝐸 𝑝𝑒,𝑣 • ln ς𝑒∈𝐸 𝑝𝑒,𝑣 = σ𝑒∈𝐸 ln 𝑝𝑒,𝑣 を保存しておくと、焼きなまし中にスコアの差分計算ができる • これを評価関数として焼きなまし 279,774,397点 （本番1位相当） ※実装上は 𝑝𝑒,𝑣 = 0 のケースを特別扱いする必要がある