解法概要

• 座標を考慮しないグラフ構築
  
• 平面上への仮配置
• 交差の解消

を順に行いました．

グラフの構築

ごみ搬入口を根とするグラフから葉としてごみの流れが数本出ている状態に対し，その中の1本を選択して分別器を設置し，2本の流れを出して次の状態とする，ということを繰り返しました．
葉となる流れはごみの種類数と同じ \(N\) 本以下とし，\(N\) 本となっている場合は2本を選んでそれらを合流させる分別器を設置し，1本の流れを出して次の状態としました．
流れや分別器の選択は，すべての組み合わせについて選択後の全体のジニ不純度を計算し，小さくなるものを選択しました．
（基本的には貪欲に1つを選んでいましたが，コンテスト終了直前に5つに変更し気休め程度のビームサーチ化を行いました．）
（例えば \(N=13\) であるシード0では，18回目の（合流＆）分別以降は不純度が下がり止まってしまいました．）

こうして得られた分別回数ごとの一番良い状態を記録し，各状態で葉となっている流れそれぞれを確率が最大となっている要素の処理機へと接続しました．
また，橋となっている各辺に対して，中間に入次数1・出次数1の頂点を1/2の確率で追加しました．

仮配置

根からBFSを行いつつ未使用の座標を親との距離が近い順に見ていき，これまでに配置した辺との交差が生まれない座標を探しました．
10個以内に見つからない場合は一番近い点としました．

交差の解消

ランダムに1つ選択した交差している辺について，座標の交換・移動を \(9:1\) の確率で行いました．
評価の良い状態（基本的には分別回数の多い状態）から順番に見ていきながら，10000回を上限として操作を行うことで解消を試み，解消できた場合は上限を解除し実行時間制限まで1段階良い状態に再挑戦していきました．
再挑戦の際は橋への頂点追加からやり直しました．
（例えばシード0で配置できたのは主に16回分別した状態まででした．）

解法詳細

グラフの構築

評価関数

合流・分別ともにジニ不純度を用います．
具体的には，流れ \(i\) におけるゴミ \(j\) の要素（ゴミ \(j\) の搬入量を \(1\) としたときの割合）を \(p_{i,j}\)，流れ \(i\) における各要素の和を \(w_i\) として，

\[ \sum_{i} w_i \sum_{j} 1- \left( \frac{p_{i,j}}{w_i} \right) ^2 \]

によって評価します．
この値はすべての流れが単一の要素からなるとき \(0\) になります．
早めの段階で同じ2つの流れを合流・分配するループに突入し，不純度が下がり止まっていました．
さらに下がっていくような別の基準もあったのですが，結局この後にある配置の際に分別回数の多いものは失敗してしまっていたため，この評価関数を使用するにとどまりました．

橋への頂点追加

柔軟性を高めることで配置しやすくなることを期待しています．
ビジュアライザを見るとこれが無くとも配置できそうに感じる部分もあり，効果があったのかについてはなんとも言えませんでした．

グラフの配置

座標の管理

kd-tree に scapegoat tree を取り入れたものを用いて使用可能な座標を管理します．

kd-tree として，基準となる座標軸を切り替えながら中央値となる点を親として座標集合を二分していき，木を構築します．
座標軸としては分散が最大となる方向を選択しました．
（コンテスト後に気がついたのですが，要素数1となる葉において切り替えが起こらない実装をしていたため，後に述べる後から追加された頂点について再構築が起こるまでやや効率が悪い（かもしれない）分割となっていました．）

scapegoat tree として，座標の削除時には対応する頂点まで木を下っていきフラグのみを立てて「抜け殻」とし，全体に占める抜け殻の割合が一定以上となった場合に全体を再構築します．
また，挿入時には基本的には葉まで辿りその子として頂点を追加し，もし道中に同じ要素の抜け殻があれば代わりにその削除フラグを下ろします．
新しく追加した頂点の深さが全体の頂点数を元に計算したある値以上であった場合，その追加場所と根との間に左右の部分木サイズが許容値（深さの基準値と対応する値）以上にアンバランスな頂点が存在するため，そこから下を再構築します．
（はじめは削除時には座標インデックスを与えず座標のみを与え，追加時には葉の下に追加するのみの実装としていたのですが，抜け殻や同じ座標の点から正しく下れない等の原因で削除に失敗し，同じ座標が大量に生成されてしまいました．）

交差する線分の発見

確認する線分の順番をシャッフル後，二重ループを回します．

平面走査を行いつつ線分の両端をイベントとして見ていき，イベント時の走査線上で隣にある線分に関するチェックを行うことで，線分の数を \(M\) として \(\Omicron (M \log M)\) で1つ見つけられるようです（Shamos-Hoey）．
また，交点もイベントとして追加することで，交点数を \(K\) として \(\Omicron ((M+K) \log M)\) ですべて列挙できるようです（Bentley-Ottmann）．
これについて実装してみたのですが，後者において（恐らくタイブレークの実装ミスにより）時々発見漏れが発生してしまったため，結局念の為どちらも使用しませんでした．

交差の解消（交換）

90%の確率で行います．
交差する2本の流れ（\(n_1 \to n_2\), \(m_1 \to m_2\)）について，\(n_2\) と \(m_2\) のノードタイプ（搬入口・処理装置・分別器）が等しければその座標を交換し，異なっていれば \((n_1, m_2)\), \((n_2, m_1)\), \((n_1, m_1)\) と順番に見ていきます．

ノードタイプが3種類なため，必ず等しいペアが存在します．
また，（搬入口 \(\to\) 処理装置）という流れや（… \(\to\) 搬入口），（処理装置 \(\to\) …）という流れは存在しないため，\((n_1, m_1)\) まで見ることは（恐らく）なく，\((n_2, m_2)\) の交換とのループは発生しません．
\((n_2, m_2)\) を優先しているのは，交差を葉の方へ動かしていき，最後に処理装置同士で交換して解消することを期待しています．
（確率で優先度の低いものも選ばれるようにした場合，スコアが下がっているようでした．）

交差の解消（移動）

10%の確率で行います．
交差する2本の流れの4点それぞれについて，反対側の端点（\(n_1\) なら \(n_2\)）に近い残っている座標5つを移動先の候補とし，20通りのうち移動後に交差が一番少なくなる移動を行います．

交差を数える際には，着目している1本（\(n_1\) を移動するなら \(n_1n_2\) 間） と他の流れとの交差のみを数えました．
（それをするのであれば定数倍をかけて \(n_1\) に繋がる辺すべて（基本的に高々3本）を見るべきであったように思います．）