AHC051振り返り

はじめに

AtCoder Heuristic Contest 051に参加した。10日間の長期物であるが、旅行が入ったのであまり取り組めてはいない。順位としては提出時は180番台だったと思うが、最終的には340番台だった。

問題

問題は、ゴミの分別問題。搬入口から入っていくゴミを、確率的に分別する分別装置で分別しつつ特定の種類のゴミのみを処理する処理装置まで持っていく問題。分別装置が設置可能な場所は指定されており、それぞれの装置の間のリンクは交わってはいけない。

問題を読んで、分別装置の種類$K$個しか分別装置を設置できないという勘違いをしてしまっていた。ゴミの種類$K$は、処理装置の数$N$に対して $N \leq K \leq 4N$なので、リーフノード$N$に対して中間ノードとして最低$N$個の木を作成しないといけないと考えた。中間ノードは最大2個までしか子を持てないので、小さい木が基本的なトポロジになると考えた。実際には、同じ種類の分別装置を設置可能なので、設置可能な場所$M$ $(10N\leq M\leq 50N)$ 全部を中間ノードとしてしまって構わない。これが、最初の方針決定に少し影響してしまっているかもしれない。

方針

確率の問題なので、ある程度最適解を求めて...とも思ったが解けそうにないので以下の順番の処理を考えた。

1. 分別装置をリーフ、搬入口をルートとした中間ノードが$N$個の2分木を作る
2. スコアを元に焼きなましで最適化をする

実装

最初の２分木を作る

一番苦労したのはここの部分。以下の2つで作成した。

右側から作る

搬入口が左端なので、右端の装置とそれに一番近い装置を分別装置を挟んで繋げる。分別装置の位置は新たに設置するベルトコンベアの距離が一番短くなるようにした。最終的に1つの装置になったところで搬入口とつなげる。分別装置の位置候補として上位5つを保持しておき深さ優先探索で検索する。サンブルにある100個の入力で、この方法で見つからないことはなかった。

右側から作る手法（Seed = 1）

搬入口から2分割しながら作る

上記の作り方だと、どうしても左側の処理装置が深さが深く、右側が浅くなってしまう。なんとなく深さが同じぐらいに配置させた方が良さそうだったので、綺麗な木になるような方法も考えてみた。

• 処理装置の重心を求め、Y軸方向で2つのグループに分割する
• Y軸が重心に近い設置場所候補を求め、そこに分別装置を配置、それぞれのグループに対して枝を張る

単純にY軸を基準として2等分していくようなイメージである。

2分割しながら作る手法（Seed = 0）

期待通り、こちらの方が高いスコアがでるのだが、導出に時間がかかってしまう場合があった。このため、あまり深くは求めずに答えが出なかった場合は右側から作る方法で作ったトポロジを初期値とすることにした。

処理装置の配置

処理装置の配置は、最初から決めるのではなくて到着するゴミの種類が確定してから、最も量が多い種類の処理装置を設置することにした。ハンガリアン法で最適解を求めるのが正しいのだとは思う。

近接解の導出

近接解は以下の4つの処理で生成した。

1. 分別装置を別の装置に置き換える
2. 子ノードを入れ替える（$p$と$1-p$の入れ替え）
3. ノードを追加する
4. ノードの順番を入れ替える

3と4は図で示した方が分かりやすいので図で。「装置間のベルトコンベアが交差しない」のチェックが重いので、そこはサボって採用が決まった後でチェックすることにした。

ノードの追加と順番の入替

実際のスコアをそのまま使って焼きなましで最適を行った。そんなに変わってはいないようには見える。

焼きなましの結果（Seed = 0）

おわりに

完成したトポロジを見ると使っていない部分が多いので、最初にメッシュ的なグラフを作ってしまってからの方が良さそうな気がしたが、
そこまでの方針変更を行なっている時間がなかった。できるだけ小さいトポロジを作らないといけないという最初の勘違いがちょっと影響してしまったかな...というのが反省点ではある。