AHC051参加記【最終24位】

解説
参加記

解説

問題

atcoder.jp

解法概要

　以下のような手順で解を出しました

全座標を使ってドロネー三角形分割を行い、交差しないグラフを作成
貪欲法で2分木の初期解作成
焼きなましで2分木の構築を最適化
山登りで処理装置の配置を最適化しつつ、分別器を仮決定
焼きなましで分別器の種類を最適化

ビジュアライザ

前処理

　ドロネー三角形分割による交差しない辺リストの作成は、ChatGPTにお願いしたら書いてくれました

　分別器は完全ランダムに生成されるため、似ている形を削除しました
　ユークリッド距離とコサイン類似度を使って、両方閾値を超えている場合のみ未使用分別器として排除しました

　以下のような組を似ているとして片方を使わないようにしました
　seed=0だと、2, 8, 12, 26, 32, 37が弾かれているようでした

初期解作成

　搬入装置から直接接続するノードは、全処理装置から多始点bfsをして一番遠いノードとしました(搬入装置の隣接ノードのうちで)
　ただ、この後の処理で全処理装置へグラフが伸びなかった場合は、搬入口の隣接ノードからランダムに選びなおしています

　2分木の接続は、bfsの要領で決めていきました
　接続された本数・処理装置への距離・周囲の未確定ノード数を使った評価値で、2つまでのノードへ接続します

　また、サイクルが出来てはいけないのでDAGを維持できるかチェックしながら接続をしました
　接続したいノードが、自身の祖先でないかだけ確認できれば良いです
　実装では、ノードNoを配列に追加しつつトポロジカルソートをしていました

　最後に、子を持たないノードを再帰的に削除して正しい木に修正します

　seed=0では、以下のような2分木が出来ました

2分木構築最適化

　TL1.0秒まで焼きなましによって、2分木構造を改善します
　近傍は、適当にノードを一つ選び今の子の数によって変えています

子0：親ノードを一つ選び、その子ノードとの間に挿入する
子0：親ノードを一つ選び、自身を介して別の隣接ノードへ接続
子1：隣接ノードを一つ選び接続する
子2：子ノードを一つ選び、接続を切る
子2：子ノードを一つ選び接続を切った上で、別の隣接ノードへ接続する

　評価関数は、根から各処理装置の位置へ到達しない確率の推定値の和としました

　 $evaluate \lbrack i\rbrack \lbrack n\rbrack$ ノード $i$ から処理装置位置 $n$ へ到達できる確率として、各処理装置の対応した位置を1.0, その他を-0.1で初期化します
　トポロジカル順の逆に見て、2つの子の内確率の大きい方にx0.7、小さい方にx0.3した値の和をそのノードの値にしました
　-0.1は、到達できないノードへの分別に対するペナルティです

　実際にその確率で分別できる訳ではありませんが、ざっくりの到達確率としては十分機能しました
　計算量としても、 $O((N+M)*N)$ で比較的軽いです

　分かりやすいようにビジュアライザ上で矢印を足しました
　(矢印を足すブックマークレットをChatGPTに作ってもらいました)

処理装置の配置最適化

　 $processors[i$ ] を、 $i$ 番目の位置にどの処理装置を置くか、として探索しました
　1000回or1.7秒で打ち切っています

　近傍は以下の4つにしました

1~N/3 右回転
1~N/3 左回転
2点swap
3点swap

　 $dp \lbrack i\rbrack \lbrack n\rbrack$ ノード $i$ にゴミ種 $n$ が存在する確率として、トポロジカルの順に分別器を全探索して最も良いものを配置していきます

　先ほどのevaluate配列を重みとして使い、dp[i]*evaluate[c1]*P[k] + dp[i]*evaluate[c2]*(1-P[k])　を最大化します（出口1,2を入れ替えた計算も)
　気持ちとしては、evaluate配列が到達期待値を表していると考えて、そのノードで分別した結果の期待値を最大化しようとしています

　スコアは誤分別の確率の和を正しく計算しています
　計算量は、 $O((N+M)*KN)$ と結構重めです

分別器の種類を最適化

　最後に、2分木構造と処理装置の位置を固定して分別器の種類を焼きなましによって最終調整します

　近傍は、まず確率を上げたい処理装置・変更するノードを乱択した上で、分別器の種類を乱択します
　その上で、分別確率が上がりそうな向きに出口を入れ替えて評価します

　スコアは誤分別の確率の和を正しく計算しています
　計算量は $O((N+M)*N)$ ですが、変更ノードより上流のみ更新しているので実際はもう少し軽いです

暫定順位表

参加記

最初の考察

　処理装置を置く場所は最悪固定で考えてみても良さそう
　分別器の種類・配置・接続の自由度が高すぎて大変 & ベルトコンベアが交差してはいけないという制約が結構難しい
　→ドロネー三角分割で得られる辺のみを使えば交差を考えなくてよい

　フィルタリングするような貪欲をしたいが、どう実装したらよいかパッと出ない
　紙で分岐を書いていい感じに特定の種類のゴミだけを分けられないか試したい

　焼きなましをする場合、木構造焼きなましのようになりそう
　→閉路を作ってはいけないため、親リストや深さをノードに持たせることになりそう

分別器の特徴可視化

　分別器の特徴を見たくなったので、ChatGPTにレーダーチャートを書いてもらいました
　極端な値を持つ分別器が良さそう？と何となく思いますが、活用方法が全然思いつきません

　0.5付近の値を持つ分別器はよく無さそうということだけは分かります

2分木構築

　遷移確率は0.1~0.9の範囲で生成されるようなので、全てのゴミを完璧に近い分別をすることは不可能な気がします
　また、分別器の特徴を見ていてもある1つだけ極端に確率が偏っているようなものが作られるのは、あまり無さそうです

　そこから、分岐する毎にゴミをざっくり分けていく2分木の構築をしたいと考えました
　ただ、これがあまりに難しい（ChatGPTに聞いてもあまり筋の良い解法は得られませんでした

　妥協解法として、まず搬入口から適当に近いノードを選んで根とします
　根から2分木を作っていって、不要な葉を最後に削除することにしました

　dpぽくスコア計算するために、経路圧縮したりと地味に大変な実装を乗り越えて、接続を適当に固定して分配器を焼きなます処理が完成しました
　処理装置は、確率の最も高いゴミと場所を順番に決定していく貪欲です

　pythonで実装した上、高速化もしていないので微妙な出来ですが、正しい出力ができていそうです

　提出すると、ACがとれました
　相対スコアは22Gで思ったより低くはありません
　暫定一位は、平均70%くらいは正しく分別出来ているようです

分岐の数を増やす

　DAGを構築しつつ、再帰的に矛盾を解消する処理をすることで、後から有向辺を追加できるようにしました
　これによって、一応2分木構造を探索できるようになりました

処理装置の位置を焼きなまし

　0~N-1のノードに、どの処理装置を置くかを焼きました（2分木構造は固定
　各ノードに処理装置までの距離に基づく評価値を振って、K種類の分別器を評価値によって決めました

構築の検討

　今の解法が伸びる未来が見えないので、どんな形の接続をすれば良さそうか改めて考えてみました

　左のように、0.8/0.2に分けられる分別器をそのまま使うと、正しい分別確率の和は1.6となります
　右のように、間にかますと正しい分別確率の和は1.792まで伸びます
　正しい分別確率を上げるためには、このような形にする必要がありそうです

　今想像しているのは、下のような感じです
　各処理装置へつながるメインの経路があり、経路間は先ほどのように分別器を介して接続されています
　各分別器は、メインの経路に近づくようにゴミを"寄せていく"ことで、正しい分別確率があがる想定です

　これを見ると、根から処理装置へは遠い方が良さそうに見えます
　また、処理装置へのメイン経路同士も離れている必要がありそうです

　平面上でどうやって構築したらいいんでしょうね...

木構造焼きなまし

　良い案が浮かばないため、焼くことにします

　各処理装置から有向辺を逆にbfsして、到達ノード数を出します
　これらの和を最大化するように、辺の貼り方を焼きました

　単純和の最大化・最小値の最大化・ExpSumLogの最大化を試して、ExpSumLogを採用しました
　ただ、構築の評価が微妙らしく実行ごとにスコアが10%程度バラツキます

3段階焼きなまし

　木構造の探索・処理装置の配置の探索・分配器の種類の探索の３つを順番に焼きなましで最適化しようとしています

　出てきた解を見てみると、木構造の出来によってかなりスコアがバラツキます
　そこで、評価が重くても、最初の二つの探索を同時にやってしまうことにしました

　木構造の探索をメインにしつつ、時々処理装置の配置も探索するようにすると小さめの盤面ではスコアが改善しました

理想盤面の検討

　一応焼きなましでそこそこの解が出るようにはなって来たため、長時間かけて実行して高得点が取れる盤面を作ってみます

　seed=3で平均85.6%の解が出来ました
　処理装置には、必ず複数の有向辺が接続されていることは分かります

　試しに、処理装置に3つの有向辺を入れることを許すと、スコアが伸びました
　ただ、seed=0のN=13のようなケースでは逆にスコアが落ちました

　分別の自由度と、処理装置への集約のトレードオフがありそうです

最後の週末

　評価関数の変更など色々試していましたが、記事を書く時間が作れず...
　さぼるために、今の方針を公開されたばかりのGPT5に要約してもらいます

#幾何: 点集合=処理装置N+分別器M+入口(0,5000)。ドロネー三角分割→交差しない候補エッジ集合を得る（平面性担保）。
#有向グラフ生成: 「分別器→隣接」方向に有向化、入口→近傍分別器に出辺。処理装置は終端。
#root選択: 逆BFSで処理装置に遠い（hop長が長い）入口近傍を self.root に。
#初期木/有向DAG: rootから広げて子を貪欲に生やす。checkDagUp でトポ順を保ちつつ閉路回避。浮いた葉を削除。
#評価系:
- getScore は“厳密DP（後ろ向き）”：葉（処理装置ノードj, 対応機種p）に dp1[j,p]=1 を置き、分別器uの dp1[u, i] = p_k[i]*dp1[c1,i]+(1-p_k[i])*dp1[c2,i]。rootの dp1[root,i] が q_i になる。
- calcProb / evaluate1 は簡略値（最大側の子に重み寄せ）で、構造探索/貪欲のガイドに使う。
- getScoreGreedy は forwardに流量(dp1)を持ちながら各分別器で候補Kからタイプkと子の左右を選ぶ近似貪欲。
#最適化:
- sa1: 構造近傍（挿入/付け替え/割り込み）＋ calcProb を目的に〜1.5s。
- sa2: 処理装置の並べ替えを軽い山登り（100手）。
- sa3: 分別器タイプ＋左右スワップをSA（〜残り時間）。