AtCoder Heuristic Contest 051お疲れ様でした。相対スコア1,170,235,007,335点で15位でした。

上位解法とはかなり方針が異なるのですが、この方針で実装しきった人が少なそうでしたので、どのように実現したのかについて解法を書いていきます。

問題概要
解法
感想

問題概要

ゴミをいい感じに分別してね。

分別器は確率的にしか分別できないから頑張ってね。

atcoder.jp

解法

アイデア

分別器の分別確率 $p_i$ は $0.1\le p_i \le 0.9$ の範囲なので、単独の分別器で分別できる精度には限界があります。もっと分別確率の高い、例えば $p_i'=0.99$ を実現する分別器のようなものを作りたいです。

そこで、下図のように繋げて分別ユニットを構成します。このような形で $k$ 個の分別器を繋げると、 $1-p_i^k$ と $p_i^k$ を作ることができます。例えば $p=0.1,k=3$ の場合は $0.999$ と $0.001$ を、 $p=0.7, k=3$ の場合は $0.657$ と $0.343$ を作ることができます。

そしてこれをさらに直列に繋げて分別アセンブリを作り、片方を処理装置に接続することにします。分別ユニットを $t$ 個直列に繋げるとすると、ユニット $t$ 個全てを連続で通り抜ける必要があるので確率は総積の形となり、 $\prod_{i=0}^{t-1}(1-p_i^{k_i})$ を作ることができます。例えば $p=0.1,k=3,t=10$ の場合は $0.99$ と $0.01$ を、 $p=0.7, k=3,t=10$ の場合は $0.015$ と $0.985$ を作ることができます。これならかなりの精度で分別ができそうですね。*1

この分別アセンブリを直列に繋ぎ、1種類ずつ分別していくというのが基本的なアイデアです。

実装方針

アイデア自体は思い付いている人も多そうだったのですが、これを平面グラフ上で実現するのは本当に難しいです。いろいろ悩んだ挙げ句、以下のような方針にしました。

凸包（＝分別アセンブリ）を直列に繋げたものを焼きなましで作る
それぞれの凸包を扇形と思って、扇形の中で $k_i$ 個組分別ユニットをいくつ作れるか嘘DPで求める
ビームサーチを使い、各扇形アセンブリでどのゴミを分別するか、その中の配置をどうするかを決める

各分別アセンブリは扇形となるようにしました。扇形であれば、下図のように出口を中心として偏角ソートし、順番に頂点を訪れることで平面交差を避けることができるためです。

ただ、扇形に絞ると図でいう左端の頂点を入口にしなければならないという制約が付き、今度は扇形同士を繋げるのが困難になるため、まずは凸包を考えることにしました。凸包の周上を移動して偏角ソートの開始地点まで向かう（図の橙色の矢印）ことにすると、無駄な頂点は出てしまいますが平面交差を避けて開始地点に到達し、そこから扇形戦略を使うことができます。

1. 凸包を作成する

凸包を繋げて、これ↓を作ります。

以下のような条件の下焼きなましました。

各凸包は周上に処理機・入口・出口を持たなければならない
番目の凸包は、として個の有効頂点数を含むことを目標にする
- 足りない頂点数の2乗をペナルティとする

この有効頂点数と呼んでいるのは、先述の凸包の周上を移動することで無駄になった頂点を除いた凸包内の頂点数のことを指しています。下図のケースだと、グレーアウトした2つの頂点は扇形に含めることができないため、それ以外の頂点の数をカウントします。

なお、いきなり凸包を作るのは難しいので、まずは三角形（処理機・入口・出口の3点）とそれを繋ぐ順番を焼きなました後で、それぞれの凸包の形状を焼きなますという2段階の焼きなましで求めています。また、本当は凸包の個数は $N-1$ 個で十分なのですが、実装の都合上 $N$ 個で妥協しました。

2. 分別ユニットの作成可能数を求める

最初に示した分別ユニットの例は3個組ユニットでしたが、常に3個組にするのが良いわけではありません。特に頂点数 $M$ が小さいときには、1, 2個組ユニットを使う方が良いことも多いです。

この次のステップで「各扇形アセンブリでどのゴミを分別するか」「その中の配置をどうするか」を決めるのですが、配置を決める際に「 $i$ 番目のアセンブリ内で1, 2, 3個組ユニットを $(c_1, c_2, c_3)$ 個作りたいが、可能か？」というクエリに答えられると便利です。これを予め求めておきましょう。

頂点を偏角ソートしてから、DPを使って求めていきます。比較的分かりやすいDPとして、 $DP\lbrack s\rbrack\lbrack c_1\rbrack\lbrack c_2\rbrack:=$ $s$ 番目の頂点まで使って、1, 2個組ユニットを $(c_1, c_2)$ 個作ったときに3個組ユニットを最大でいくつ作れるか（3個組ユニットが $0$ 個でも $(c_1, c_2)$ 個作れない場合は $-\mathrm{INF}$ ）というDPをしておくと、「 $i$ 番目のアセンブリ内で1, 2, 3個組ユニットを $(c_1, c_2, c_3)$ 個作ることは可能か？」というクエリに高速に答えることができます。

しかし、実はこのDPはユニットの作成効率があまり良くありません。特に3個組ユニットの作成効率が悪いです。なぜなら、頂点 $s, s+1, s+2, s+3$ を使って3個組ユニットを作ろうとした場合、頂点 $s+3$ から見て頂点 $s, s+1, s+2$ が順に反時計回りに並んでいなければならないからです。簡単のため、頂点 $s+3$ を中心とした極座標上で頂点 $s, s+1, s+2$ が一様ランダムな角度に配置されるとざっくり仮定すると、3頂点が所望の順序で配置されている確率は $\frac1{3!}=\frac16$ しかありません。したがって、高い確率で頂点を無駄にしてしまうことになります。

そこで、DPの定義と遷移を変えます。下図のように頂点 $s, t$ と扇形の中心を結ぶ折れ線 $s-t$ ラインを考え、 $DP\lbrack s\rbrack\lbrack t\rbrack\lbrack c_1\rbrack\lbrack c_2\rbrack:=$ 前線が $s-t$ ラインで、1, 2個組ユニットを $(c_1, c_2)$ 個作ったときに3個組ユニットを最大でいくつ作れるかと定めた上で、各ユニット内の頂点順は偏角ソート順でなくても良いことにします。*2

このようにすると、ユニット作成の自由度が上がり、より効率的に頂点を使えるようになります。DPの変更によりだいたい1割程度相対スコアが伸びました。*3

3. アセンブリの担当するゴミと内部構造を求める

ここまで来れば幾何のことは忘れて良いので、あとはそんなに難しくありません。各アセンブリ内で担当するゴミとアセンブリ内の内部ユニット構造を決めましょう。ちなみにコンテスト中は幾何の実装に取り組む前にこのパートだけ取り組んで、「理想的なグラフの埋め込みが可能だったとしてどのくらいのスコアが取れるか？」を見積もってから幾何の実装に移りました。

まず、 $i$ 番目のアセンブリで処理するゴミ $P_i$ を決め打ったとしましょう。このとき、アセンブリ内でどのようにユニットを組み合わせれば良いか求めたいです。

変数として、どの分別器を使うか・何個組のユニットを使うかの組の多重集合を考えます。例えば、「アセンブリ内で分別器5の3個組ユニット・分別器5の3個組ユニット・分別器1の2個組ユニットを設ける」というような感じです。*4 *5

目的関数としては、「このアセンブリを通すことでゴミの誤分別が確定する確率」を最小化することを考えます。下図でいうと、ゴミ $P_i$ が橙色の頂点に誤分別されてしまう確率と、ゴミ $P_i$ 以外が青色の頂点に誤分別されてしまう確率の和を考えて、これを最小化します。

いい感じの解を求めるために、貪欲と山登り法を適用します。以下のような処理を行います。

アセンブリ内のユニット多重集合を空集合で初期化する
「分別器の種類 x (1, 2, 3個組ユニット)」を全探索して、目的関数が最小になるユニットを追加する貪欲を行う
どのようなユニットを追加しても悪化してしまうようになったらそこで貪欲を終了する
多重集合内のユニット全てに対して、「分別器の種類 x (0, 1, 2, 3個組ユニット)」に変更した場合にどうなるかを全探索し、目的関数が改善するなら置き換える山登りを行う*6
山登りが改善しなくなったら終了

だいたい山登りを1～3周くらい回すと局所最適解が得られるので、そこそこ高速にいい感じの解を得ることができます。

これでゴミ $P_i$ を固定したときの内部ユニット構造を決められるようになったので、あとはゴミの順列 $P$ を決めましょう。これにはビームサーチを使いました。各アセンブリをターンと考えて、各ターンでどのゴミ $P_i$ を処理するか全探索すればよいです。山登り法の処理に比べてコピーコストは十分軽いので、ナイーブなビームサーチで十分です。

感想

たまにはAHCに幾何が出ても良いよなと思っていましたが、今回で1年分の幾何処理を実装した気分でした。最終的な提出コードの行数もライブラリ除いて6000行くらいになったので、かなりおなかいっぱいです。

とはいえ、アイデアをなんとか形にすることところまで持って行けたので満足度は高いです。実装がギリギリ可能な範囲でやりたいことが達成できそうな方針を考えるのはなかなか楽しい時間でした。自分なりに凝った解法なので、愛着が湧いてきますね。

今年の長期AHCもおそらくあと2回となりましたが、残り2回も悔いのないように取り組んでいきたいですね。

*1:ここでは説明のため、全てのユニットのpが同じとしていますが、実際は「ゴミ1を大きく減らすユニット、ゴミ2と3を大きく減らすユニット、ゴミ4を大きく減らすユニット」のように複数種類を組み合わせると効果的です。

*2:実際は折れ線s-tでは全ての状態を表現しきれなかったり、計算量の都合上遷移を絞っていたりするので、全ての状態を調べることはできず嘘DPになっています。

*3:幾何が複雑に絡む上にコーナーケースのオンパレードなので、実装は本当に本当に大変です……。

*4:ちなみに、p=0.1の分別器の出力先を反転させるとp=0.9の分別器として扱うことができるので、実質的な分別器は2K個と見なすことができます。

*5:「分別器2, 5, 6の3個組ユニット」のような組み合わせも考えられますが、予備実験でユニット内の分別器の種類は揃えてしまって良さそうなこと、解の構造を絞ることで計算量を削減できることから、ユニット内の分別器は1種類としました。

*6:0個組ユニットは分別器の削除に相当します。

TERRYのブログ

最近は競技プログラミングにお熱。

THIRD プログラミングコンテスト 2025 夏 (AHC051) 解説