🥤
AHC037振り返り

2024/09/25に公開
 はじめにAsprova プログラミングコンテスト(AtCoder Heuristic Contest 037)に参加した。制限時間4時間のAHCとしては「短期間」に分類されるもので、正直言うと苦手である。今回も500番台といまいちだったので、解説動画や上位のソースコードを読みながら振り返ってみる。

 問題問題としては、炭酸とシロップを混ぜてN種類の炭酸飲料（ターゲット炭酸飲料と呼ぶ）を作る。ただし、炭酸やシロップを「引く」ことはできない。最初、「混ぜる」ので、「割合」なのかな？と思ったら絶対値であった。ビジュアライザで分かるように、N個の点を通る木の中で、エッジのマンハッタン距離が一番小さいものという問題が近い。「混ぜる」回数にコストがかからないので、中間ノードをうまく配置するのがポイントになる問題である。
また、後からでてくるが、それぞれの座標は相異なるのと、0になる点が存在することが問題を解くのを容易にしている。

 自分の解法振り返りとして、考えた順に記載していく。

 最小値から作っていく炭酸飲料(A_i, B_i)を、(A_j, B_j)から作るためには、A_i > A_j, B_i > B_jが成り立つ必要がある。これから、ある時点で「次に作らないといけない炭酸飲料」は未作成の炭酸飲料のうち、AかBが最小値のものであると考えた。さらに、とあるノードから2つの炭酸飲料を作るときは、それぞれの最小値のポイントの炭酸飲料をまずつくり、そこから2つを作成した方がコストが少ない。

最小値を持つ2つを、中間状態を経由して作成する
このため、以下のようにして生成することとした。

\min(A), \min(B)を持つ未作成の炭酸飲料をX, Yとする。

(\min(A), \min(B))の炭酸飲料をZとして、作成済とする。

X, Y, Z をそれぞれ、作成済の炭酸飲料から一番近い炭酸飲料から作成する。
A_i, B_iが相異なるので、X, Y, Zは一意に決まるため、実装はさほど難しくない。

最小値から順番に作っていく (Score: 23,064,446)
赤い点がターゲット炭酸飲料で、青い丸が中間状態として作成した炭酸飲料。赤い点が均等にばらつきがあるため、青い点は対角線上に並んでしまっており、効果的に中間状態を作成していないように見える。振り返って見ると、次に作らないといけないのは、A_i, B_iが最小の2つではなく、どちらかであったのだと思う。

 最も近い炭酸飲料から作成する上記の出力結果を見ると、作成順など関係なく、純粋に「一番近い炭酸飲料」から作ればいいような気がする。そこで、(0, 0)の炭酸飲料を含めて、一番近い炭酸飲料から生成するようにする。どのような順番で処理しても、グラフでいくと左下の炭酸飲料からしか生成できないので、ループは発生しない。

最も近い炭酸飲料から作る (Score: 22,803,065)
スコアとしては 0.2M程度下がったが、ベースとしてはこれで良い気がする。

 中間状態を乱数で追加するこの後、中間状態となる炭酸飲料を追加していくが、ターゲット炭酸飲料と炭酸もしくはシロップの量が等しいものしか意味がない。つまり最大で 1000 \times 1000 - 1000種類から最適な組み合わせを選ぶことになる。そこで、乱数で中間状態を選び、スコアが上昇するなら採用、上昇しないなら不採用というルールで作ってみた。

乱数で中間状態を作る (Score: 23,836,311)
最初のものとそんなにスコアは変わっていないが、結局時間切れでこれが提出版となった。

 延長戦
 2つ以上の炭酸飲料を作る時に中間状態を生成乱数でおこなうよりは、最も近い炭酸飲料を結んだ木を最適化する方が良いのでは？と考えた。

最初の図に書いたように、2つの炭酸飲料を作るときは、それぞれの最小値の点を経由した方がコストが低いので、以下のようにして中間状態を作る。
1つの炭酸飲料から複数の炭酸飲料を生成している場合、(\min(A), \min(B))の炭酸飲料をZとして生成し、それをベースに他の炭酸飲料を生成するようにする。

2つ以上の炭酸飲料を生成するときに中間状態を作成する (Score: 28,149,357)
スコアとしては大きく上がった。ただ、1つの炭酸飲料から3つ以上の炭酸飲料を生成している箇所もあり、そこは改善の余地がある。

 3つ以上の場合の対応
3つ以上の場合は以下のように処理することとした。

\min(A), \min(B)を持つターゲット炭酸飲料をX, Yとする。

(\min(A), \min(B))の炭酸飲料をZとして、生成する。

X, Y以外の炭酸飲料は、Z-X, Z-Yの線上に中間状態を生成し、近い方から生成する

3つ以上の炭酸飲料を生成するときに、2つずつに分ける (Score: 31,182,689)
時間内にここまでいけたらなと思う。2分木にした方がスコアが低くなるのは最初に気づいていたのだから、分割するように考えていれば辿り着けたと思う。

 解説動画を見て
 小さい二分木を組み合わせる自分のアプローチはとりあえず木を作ってそれを2分木に集約していく方法をとっていた。一方、解説動画を見ると小さい2分木を作ってそれらを組み合わせる方法が紹介されていた。2つの炭酸飲料(A_i, B_i), (A_j, B_j)を使ってできる2分木のコストは以下のようになる。

A_i - \min(A_i, A_j) + A_j - \min(A_i, A_j) + B_i - \min(B_i, B_j) + B_j - \min(B_i, B_j)
このコストが小さい順に2分木を作っていくと最終的には大きな木ができる...となるはずであるが、実はこの方法はうまくいかない。

小さい二分木を組み合わせる (Score: 23,324,861)
一部「うまく周りとくっつけなかった」炭酸飲料が残ってしまい、長い線ができてしまっている。とはいいつつ私の提出版とそんなに変わらないスコアとなっているのが悲しい。

 右上から生成するそこでバラバラに作成されないように右上の二分木程コストが小さくなるような項を追加する。具体的には前述のcostに対して以下の項を追加する

\textrm{cost} - (A_i + B_i + A_j + B_j)
それは計算すると以下のようになる

-2 * \left( \min(A_i, A_j) + \min(B_i, B_j) \right)
このコストが小さい順に処理をする。つまり、\min(A_i, A_j) + \min(B_i, B_j)が大きい順に

2分木を作っていくと最終的には大きな木になる。ちなみに、A_i = 0 と B_i = 0になる点が存在するため、必ず木の根は(0, 0)になる。

右上から二分木を作る (Score: 35,665,958)

 ビームサーチ上の方法では「もっともコストが小さい木」を順に作っていくが、「コストの小さいk個の木」を候補として残していくように拡張したものをビームサーチと呼ぶ。ただ、これまでの実装は状態を1つしか持てないようになっていたので、作り直さないといけなかった。
「コストの小さい二分木」を見つける方法はO(N^2)なので、時間がかかってしまう。どうしているんだろう？と思って上位の方のソースコードを読んでいたら、右上M個の点だけを対象にしていた。具体的には以下のような感じ。
ノードをA_i + B_iの大きい順にソートする
上位M個のノードを切り出す。
ビームサーチを1ステップ進める（2個ノードを消して、1個ノードを足す）
2.での残りノードから1個入れて3.に戻る
こうすると「コストの小さい二分木」はM個のノードから見つけることになるのでO(M^2)で、トータルの計算量はO(N M^2)．Mを小さくとれば問題ない計算量になる。

ビームサーチ (Score: 36,150,291)

 おわりになんとなく、焼きなまし法や山登り法のイメージを持って取り組んでしまったため、乱数を使った解法にこだわってしまい、時間を浪費してしまった気がする。上位の方々はビームサーチの後に焼きなまし法を適用していたりするが、まだまだだなぁと感じた問題であった。