AT_ahc051_a [AHC051A] Probabilistic Waste Sorting

高橋市では現在、新たなごみ処理場を建設中である。 この処理場にはさまざまな種類のごみが運び込まれるため、処理を行う前に分別する必要がある。 分別は、例えば磁石によって鉄を含むものとそれ以外を分けるなど、いくつかの機器を使って行うことができる。 ただし、分別器は確率的にごみを二つの経路に振り分ける仕組みであり、ごみの種類を正確に識別することはできない。 そのため、例えば形状によって缶とそれ以外を分けた後に、磁石によってアルミ缶とスチール缶を分けるなど、複数の分別器を適切に組み合わせることが必要である。 複数の分別器をうまく組み合わせることにより、できるだけ正確にごみの分別を行ってほしい。

$ N $ 種類のごみを分別して処理するためのごみ処理場を建設中である。 ごみ処理場は2次元平面上の $ 0\leq x\leq 10^4 $ 、 $ 0\leq y\leq 10^4 $ からなる正方形領域として表現される。 この処理場にはさまざまな種類のごみが**ごみ搬入口**から運び込まれる予定であり、**処理装置**と**分別器**を設置し、それらを**ベルトコンベア**で結ぶことにより、できるだけ正確に分別を行った上で処理を行うことができるようにしたい。 #### ごみ搬入口 処理場内に一つだけ存在し、座標は $ (0,5000) $ である。 搬入口からは一本のベルトコンベアを伸ばし、処理装置または分別器へとごみを運ぶ。 #### 処理装置 処理場内に各ごみの種類ごとに処理装置を $ 1 $ 台ずつ設置する。 各ごみを正しい処理装置に運び込むことが目的である。 ごみ処理場内には処理装置を設置できるスペースがちょうど $ N $ 箇所存在し、 $ i $ 番目の設置場所の座標は $ (x^d_i,y^d_i) $ である。 どの設置場所にどの種類のごみの処理装置を設置するかは自由に選ぶことができる。 #### 分別器 $ K $ 種類のごみ自動分別器がある。 **同じ分別器を複数設置しても構わない。** 各分別器は運び込まれたごみを確率的に2つの経路のいずれかへと振り分け、出口1または出口2から運び出す。 このとき、どの経路に進むかはごみの種類ごとに定まった確率に従う。 $ i $ 番目の自動分別器が種類 $ j $ のごみを出口1から運び出す確率は $ p_{i,j} $ であり、出口2から運び出す確率は $ 1-p_{i,j} $ である。 ごみ処理場内には分別器を設置するためのスペースが $ M $ 箇所存在し、 $ i $ 番目の設置場所の座標は $ (x^s_i,y^s_i) $ である。 各スペースには高々 $ 1 $ 台の分別器を設置することができる。 #### ベルトコンベア ごみ搬入口ならびに各分別器の二つの出口からはベルトコンベアを伸ばし、処理装置もしくは他の分別器へとごみを運ぶ必要がある。 ベルトコンベアは始点と終点を結ぶ線分として敷設され、端点をひとつも共有しない二つのベルトコンベアは共有点を持ってはならない。 この条件では、分別器の二つの出口の行き先が同じであることも許容されている。 ごみ搬入口・処理装置・分別器を頂点、ベルトコンベアを辺とした有向グラフを考えたとき、有向グラフに閉路（自己閉路を含む）が存在してはならない。 #### ヒント: 線分の交差判定について 線分 $ p_1p_2 $ と $ q_1q_2 $ が、共有点を持つかどうかは、以下の疑似コードにより判定できる。 なお、計算される値はすべて整数値のため、誤差は発生しない。 ``` def sign(x): return 1 if x > 0 else -1 if x < 0 else 0 def orientation(a, b, c): cross = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) return sign(cross) def segments_intersect(p1, p2, q1, q2): if (max(p1.x, p2.x) < min(q1.x, q2.x) or max(q1.x, q2.x) < min(p1.x, p2.x) or max(p1.y, p2.y) < min(q1.y, q2.y) or max(q1.y, q2.y) < min(p1.y, p2.y)): return False o1 = orientation(p1, p2, q1) o2 = orientation(p1, p2, q2) o3 = orientation(q1, q2, p1) o4 = orientation(q1, q2, p2) return (o1 * o2

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ x^d_0 $ $ y^d_0 $ $ \vdots $ $ x^d_{N-1} $ $ y^d_{N-1} $ $ x^s_0 $ $ y^s_0 $ $ \vdots $ $ x^s_{M-1} $ $ y^s_{M-1} $ $ p_{0,0} $ $ \cdots $ $ p_{0,N-1} $ $ \vdots $ $ p_{K-1,0} $ $ \cdots $ $ p_{K-1,N-1} $ **制約を修正しました(8/1 19:30)** - ごみの種類数 $ N $ は $ 5\leq N\leq 20 $ を満たす。 - 分別器設置場所の個数 $ M $ は $ 10N\leq M\leq 50N $ を満たす。 - 分別器の種類数 $ K $ は $ N\leq K\leq 4N $ を満たす。 - $ i $ 番目の処理装置設置場所の座標 $ (x^d_i,y^d_i) $ は、 $ 0\leq x^d_i,y^d_i\leq 10^4 $ を満たす整数である。 - $ i $ 番目の分別器設置場所の座標 $ (x^s_i,y^s_i) $ は、 $ 0\leq x^s_i,y^s_i\leq 10^4 $ を満たす整数である。 - 搬入口およびすべての設置場所の座標は互いに異なる。 - $ i $ 番目の分別器が種類 $ j $ のごみを出口1から運び出す確率 $ p_{i,j} $ は実数であり、 $ 0\leq p_{i,j}\leq 1 $ を満たす。

ベルトコンベアの行き先を、以下のように番号で表現する。 - 行き先が $ i $ 番目の処理装置設置場所である場合は $ i $ - 行き先が $ i $ 番目の分別器設置場所である場合は $ N+i $ $ i $ 番目の処理装置設置場所に設置する処理装置の番号を $ d_i $ ( $ 0\leq d_i\leq N-1 $ ) とする。 ごみ搬入口から出るベルトコンベアの行き先を表す番号を $ s $ ( $ 0\leq s\leq N+M-1 $ ) とする。 このとき、以下の形式で標準出力に出力せよ。 > $ d_0 $ $ \cdots $ $ d_{N-1} $ $ s $ 続けて、 $ M $ 行を標準出力に出力せよ。 $ i $ 行目は、 $ i $ 番目の分別器設置場所の状態に応じて以下のように出力する。 - 分別器を設置しない場合： > $ -1 $ - $ k $ 番目 ( $ 0\leq k\leq K-1 $ ) の分別器を設置し、出口1から出るベルトコンベアの行き先を表す番号が $ v_1 $ 、出口2から出るベルトコンベアの行き先を表す番号が $ v_2 $ である場合（ $ 0\leq v_1,v_2\leq N+M-1 $ ）： > $ k $ $ v_1 $ $ v_2 $ ベルトコンベアの行き先が分別器設置場所である場合、そこには分別器が設置されていなければならない。 [例を見る](https://img.atcoder.jp/ahc051/jdd9gfQC.html?lang=ja&seed=0&output=sample)

### 得点 $ i $ 種類目のごみが、それに対応する処理装置に最終的に運び込まれる確率を $ q_i $ と定義する。 このとき、以下の絶対スコアが得られる： \\\[ \\mathrm{round}\\left(10^9\\times \\frac{1}{N}\\sum\_{i=0}^{N-1}(1-q\_i)\\right) \\\] **絶対スコアは小さければ小さいほど良い。** 各テストケース毎に、 $ \mathrm{round}(10^9\times \frac{全参加者中の最小絶対スコア}{自身の絶対スコア}) $ の**相対評価スコア**が得られ、その和が提出の得点となる。 最終順位はコンテスト終了後に実施されるより多くの入力に対するシステムテストにおける得点で決定される。 暫定テスト、システムテストともに、一部のテストケースで不正な出力や制限時間超過をした場合、そのテストケースの相対評価スコアは0点となり、そのテストケースにおいては「全参加者中の最小絶対スコア」の計算から除外される。 システムテストは **CE 以外の結 果を得た一番最後の提出**に対してのみ行われるため、最終的に提出する解答を間違えないよう注意せよ。 #### テストケース数 - 暫定テスト: 50個 - システムテスト: 2000個、コンテスト終了後に [seeds.txt](https://img.atcoder.jp/ahc051/seeds.txt) (sha256=b61fb5678d480a79e25a50141403e14e8e245d5699e90aa53d4fad893e10dee8) を公開 #### 相対評価システムについて 暫定テスト、システムテストともに、CE 以外の結果を得た一番最後の提出のみが順位表に反映される。 相対評価スコアの計算に用いられる各テストケース毎の全参加者中の最小絶対スコアの算出においても、順位表に反映されている最終提出のみが用いられる。 順位表に表示されているスコアは相対評価スコアであり、新規提出があるたびに、相対評価スコアが再計算される。 一方、提出一覧から確認出来る各提出のスコアは各テストケース毎の絶対スコアをそのまま足し合わせたものであり、相対評価スコアは表示されない。 最新以外の提出の、現在の順位表における相対評価スコアを知るためには、再提出が必要である。 不正な出力や制限時間超過をした場合、提出一覧から確認出来るスコアは0となるが、順位表には正解したテストケースに対する相対スコアの和が表示されている。 #### 実行時間について 実行時間には多少のブレが生じます。 また、システムテストでは同時に大量の実行を行うため、暫定テストに比べて数%程度実行時間が伸びる現象が確認されています。 そのため、実行時間制限ギリギリの提出がシステムテストでTLEとなる可能性があります。 プログラム内で時間を計測して処理を打ち切るか、実行時間に余裕を持たせるようお願いします。 ### 入力生成方法 - $ \mathrm{rand}(L,U) $ ： $ L $ 以上 $ U $ 以下の整数を一様ランダムに生成する。 $ N $ 、 $ M $ 、 $ K $ は、それぞれの範囲内から一様ランダムに生成される。 $ N $ 個の処理装置設置場所と $ M $ 個の分別器設置場所の座標は、以下の手順で $ N+M $ 個の座標を順に生成し、前半の $ N $ 個を処理装置設置場所、後半の $ M $ 個を分別器設置場所とする。 使用済み座標集合 $ S $ を $ S=\{(0,5000)\} $ により初期化する。 $ x=\mathrm{rand}(0,10^4), y=\mathrm{rand}(0,10^4) $ により座標 $ (x,y) $ を生成する。 生成した点とのユークリッド距離が $ 100 $ 以下の点が $ S $ に含まれない場合、この点を採用し、 $ S $ に加える。 この操作を $ N+M $ 個の点が生成されるまで繰り返す。 分類確率 $ p_{i,j} $ はそれぞれ独立に、 $ \mathrm{rand}(1000,9000)\times 10^{-4} $ により生成される。 ### サンプルプログラム(Python) Python による解答例を示す。 このプログラムでは、以下の処理を行っている。 1. $ i $ 番の位置に $ i $ 番の処理装置を設置する 2. 搬入口と最も近い分別器設置場所を結ぶ 3. 0 番の分別器を設置し、出口1を最も確率が高いごみ種の処理装置に、出口2を最も確率が低いごみ種の処理装置に接続する ``` import sys import math input = sys.stdin.readline # 入力読み込み N, M, K = map(int, input().split()) processor_positions = [] for _ in range(N): x, y = map(int, input().split()) processor_positions.append((x, y)) sorter_positions = [] for _ in range(M): x, y = map(int, input().split()) sorter_positions.append((x, y)) prob = [] for _ in range(K): row = list(map(float, input().split())) prob.append(row) # i番の位置にi番の処理装置を設置 proc_assign = ' '.join(str(i) for i in range(N)) # 搬入口 (0,5000) と最も近い設置場所を結ぶ inlet = (0, 5000) dist_sq = [((x - inlet[0])**2 + (y - inlet[1])**2, i) for i, (x, y) in enumerate(sorter_positions)] _, nearest_i = min(dist_sq) inlet_conn = N + nearest_i # 0番の分別器を設置し、出口1を一番確率の高いごみ種の処理装置と、出口2を一番確率の低いごみ種の処理装置と結ぶ first_row = prob[0] imax = first_row.index(max(first_row)) imin = first_row.index(min(first_row)) sorter_assigns = [] for i in range(M): if i == nearest_i: sorter_assigns.append(f"0 {imax} {imin}") else: sorter_assigns.append("-1") print(proc_assign) print(inlet_conn) print("\n".join(sorter_assigns)) ``` ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/ahc051/jdd9gfQC.html?lang=ja): ローカル版より高性能でアニメーション表示が可能です。 - [ローカル版](https://img.atcoder.jp/ahc051/jdd9gfQC.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc051/jdd9gfQC_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。