A - Road Repair Editorial /

Time Limit: 6 sec / Memory Limit: 1024 MB

ストーリー

高橋市は老朽化した道路の補修工事を計画している。 高橋市の道路網は、交差点を頂点としてその間の道路を辺とした平面無向グラフとして表現できる。 工事中の道路は通行止めとなるため、目的地に移動するには遠回りする必要が生じ、市民の不満が溜まってしまう。 一日あたりに同時に工事できる辺数の上限と、全ての工事を終えるまでの日数の上限が決まっているので、出来るだけ不満が少なくなるように、各辺を何日目に工事するかの計画を立てて欲しい。

問題文

辺に重みの付いた N 頂点の無向平面グラフが与えられるので、D 日間で各辺をちょうど1回ずつ工事したい。 各辺の工事は 1 日で完了し、同じ日に最大で K 本の辺を同時に工事することが出来る。

工事中でない辺は両方向に通行可能で、辺の重みはその辺上を移動するのにかかる移動距離を表す。 どの辺も工事を行っていない状態における、頂点 i から頂点 j への最短距離を d(i,j) とする。 元のグラフから k 日目に工事する辺を取り除いたグラフにおける、頂点 i から頂点 j への最短距離を d_k(i,j) とする。 ただし、i から j へ到達不能な場合は、d_k(i,j)=10^9 とする。 このとき、k 日目の工事に対する不満度 f_k は、以下のようにランダムな異なる二点間の最短距離の増加量の期待値として定義される。 \[ f_k = \frac{\sum_{i\neq j}(d_k(i,j)-d(i,j))}{N(N-1)} \]

工事全体に対する不満度は、各日の不満度の平均を用いて \[ \mathrm{round}\left(10^3\times \frac{1}{D}\sum_{k=1}^D f_k\right) \] と定義される。 工事全体に対する不満度が出来るだけ低くなるような工事計画を求めよ。

得点

各テストケース毎に、\mathrm{round}(10^9\times \frac{全参加者中の最小不満度}{自身の不満度}) の相対評価スコアが得られ、その和が提出の得点となる。

最終順位はコンテスト終了後に実施されるより多くの入力に対するシステムテストにおける得点で決定される。 暫定テスト、システムテストともに、一部のテストケースで不正な出力や制限時間超過をした場合、そのテストケースの相対評価スコアは0点となり、そのテストケースにおいては「全参加者中の最小不満度」の計算から除外される。 システムテストは CE 以外の結果を得た一番最後の提出に対してのみ行われるため、最終的に提出する解答を間違えないよう注意せよ。

テストケース数

  • 暫定テスト: 50個
  • システムテスト: 2000個、コンテスト終了後にseeds.txt (sha256=0522b6c3da4e413908209488368988ebce3b3809c0d9278dc9adaf804896fa23) を公開

相対評価システムについて

暫定テスト、システムテストともに、CE 以外の結果を得た一番最後の提出のみが順位表に反映される。 相対評価スコアの計算に用いられる各テストケース毎の全参加者中の最小不満度の算出においても、順位表に反映されている最終提出のみが用いられる。

順位表に表示されているスコアは相対評価スコアであり、新規提出があるたびに、相対評価スコアが再計算される。 一方、提出一覧から確認出来る各提出のスコアは各テストケース毎の不満度をそのまま足し合わせたものであり、相対評価スコアは表示されない。 最新以外の提出の、現在の順位表における相対評価スコアを知るためには、再提出が必要である。 不正な出力や制限時間超過をした場合、提出一覧から確認出来るスコアは0となるが、順位表には正解したテストケースに対する相対スコアの和が表示されている。

実行時間について

実行時間には多少のブレが生じます。 また、システムテストでは同時に大量の実行を行うため、暫定テストに比べて数%程度実行時間が伸びる現象が確認されています。 そのため、実行時間制限ギリギリの提出がシステムテストでTLEとなる可能性があります。 プログラム内で時間を計測して処理を打ち切るか、実行時間に余裕を持たせるようお願いします。

入力

入力は以下の形式で標準入力から与えられる。

N M D K
u_1 v_1 w_1
\vdots
u_M v_M w_M
x_1 y_1
\vdots
x_N y_N
  • N、M、D、K はそれぞれ、グラフの頂点数、辺数、日数、一日に工事可能な辺数の上限を表す整数値であり、500\leq N\leq 1000, 500\leq M\leq 3000, 5\leq D\leq 30, \mathrm{ceil}(M/D)< K\leq 2\cdot\mathrm{ceil}(M/D) を満たす。
  • (u_i,v_i,w_i) は i 番目の辺が頂点 u_i と v_i を重み w_i で結んでいることを表し、1\leq u_i<v_i\leq N、1\leq w_i\leq 10^6 を満たす整数値である。各頂点の次数は2以上であることが保証されている。
  • (x_i, y_i) は i 番目の頂点の座標を表し、0\leq x_i,y_i\leq 1000 を満たす整数値である。グラフの生成とビジュアライズに使用されており、不要であれば読み込まなくても構わない。
  • 与えられるグラフは 2-辺連結 な平面グラフであり、頂点 i を座標 (x_i, y_i) に配置し、各辺を両端点を結ぶ線分として描画した時、どの二辺も端点以外に共通点を持たないことが保証されている。

出力

i 番目の辺を r_i (1\leq r_i\leq D) 日目に工事するとしたとき、以下の形式で標準出力に出力せよ。

r_1 r_2 \cdots r_M

例を見る

入力生成方法

L 以上 U 以下の整数値を一様ランダムに生成する関数を \mathrm{rand}(L,U) で表す。

グラフの生成

頂点数 N を N=\mathrm{rand}(500,1000) により生成する。 中心 (500,500)、半径 500 の円に含まれる格子点からランダムに点を一つずつ、合計 N 個選んで (x_1,y_1),\cdots,(x_N,y_N) とする。 ただし、既に選んだ点とのユークリッド距離が 10 以下の場合は選び直す。 これらの点を頂点集合 V とする平面グラフ (V,E) を以下のように作成する。

まず、ドロネー三角形分割を計算し、三角形分割の辺を E とする。 0 以上 0.75 未満の実数 p をランダムに生成する。 各辺 e\in E についてランダムな順に、 「両端点の次数が共に 4 以上であるならば確率 p で E から e を取り除く」という操作を行う。 全ての辺について処理を終えた後、操作後に残った E に対してグラフ (V,E) が 2-辺連結でないならば、E を元に戻して p の生成からやり直す。 各辺 (u,v) の重みは、\mathrm{round}(10^3\times \sqrt{(x_u-x_v)^2+(y_u-y_v)^2}) により決定する。

D, K の生成

D=\mathrm{rand}(5, 30) と生成する。 K'=\mathrm{ceil}(M/D) とし、K=\mathrm{rand}(K'+1,2K') と生成する。

ツール(入力ジェネレータ・ビジュアライザ)

コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。

Story

Takahashi City is planning to repair its dilapidated roads. The city's road network can be represented as a planar undirected graph with intersections as vertices and the roads between them as edges. Because roads under repair are closed to traffic, citizens must take detours to reach their destinations, causing frustration. Given the maximum number of edges that can be repaired per day and the maximum number of days to complete all the repairs, please plan which edges to repair on which day so as to cause as little frustration as possible.

Problem Statement

Given an edge-weighted undirected planar graph with N vertices, we want to perform repair work on each edge exactly once in D days. We can complete the repair work on each edge in a single day, and at most K edges can be repaired simultaneously on the same day.

Edges that are not under repair work are passable in both directions, and the weight of an edge represents the distance it takes to move on that edge. Let d(i,j) be the shortest distance from vertex i to vertex j in the original graph. Let d_k(i,j) be the shortest distance from vertex i to vertex j in the graph obtained by removing the edges to be repaired on day k from the original graph. If j is unreachable from i, we define d_k(i,j)=10^9. The frustration level f_k for the repair work on day k is defined as the expected increase in the shortest distance between two different vertices, as follows. \[ f_k = \frac{\sum_{i\neq j}(d_k(i,j)-d(i,j))}{N(N-1)} \]

Using the average of the frustration levels for each day, the frustration level for the whole repair work is defined as \[ \mathrm{round}\left(10^3\times \frac{1}{D}\sum_{k=1}^D f_k\right) \] Find a repair schedule that causes as little frustration as possible.

Scoring

For each test case, we compute the relative score \mathrm{round}(10^9\times \frac{\mathrm{MIN}}{\mathrm{YOUR}}), where YOUR is your frustration level and MIN is the lowest frustration level among all competitors obtained on that test case. The score of the submission is the sum of the relative scores.

The final ranking will be determined by the system test with more inputs which will be run after the contest is over. In both the provisional/system test, if your submission produces illegal output or exceeds the time limit for some test cases, only the score for those test cases will be zero, and your submission will be excluded from the MIN calculation for those test cases.

The system test will be performed only for the last submission which received a result other than CE . Be careful not to make a mistake in the final submission.

Number of test cases

  • Provisional test: 50
  • System test: 2000. We will publish seeds.txt (sha256=0522b6c3da4e413908209488368988ebce3b3809c0d9278dc9adaf804896fa23) after the contest is over.

About Relative Evaluation System

In both the provisional/system test, the standings will be calculated using only the last submission which received a result other than CE. Only the last submissions are used to calculate the MIN for each test case when calculating the relative scores.

The scores shown in the standings are relative, and whenever a new submission arrives, all relative scores are recalculated. On the other hand, the score for each submission shown on the submissions page is the sum of the frustration levels for each test case, and the relative scores are not shown. In order to know the relative score of submission other than the latest one in the current standings, you need to resubmit it. If your submission produces illegal output or exceeds the time limit for some test cases, the score shown on the submissions page will be 0, but the standings show the sum of the relative scores for the test cases that were answered correctly.

About execution time

Execution time may vary slightly from run to run. In addition, since system tests simultaneously perform a large number of executions, it has been observed that execution time increases by several percent compared to provisional tests. For these reasons, submissions that are very close to the time limit may result in TLE in the system test. Please measure the execution time in your program to terminate the process, or have enough margin in the execution time.

Input

Input is given from Standard Input in the following format:

N M D K
u_1 v_1 w_1
\vdots
u_M v_M w_M
x_1 y_1
\vdots
x_N y_N
  • N, M, D, and K are integers representing the number of vertices, the number of edges, the maximum number of days, and the maximum number of edges that can be repaired per day, respectively. These satisfy 500\leq N\leq 1000, 500\leq M\leq 3000, 5\leq D\leq 30, and \mathrm{ceil}(M/D)< K\leq 2\cdot\mathrm{ceil}(M/D).
  • u_i, v_i, and w_i are integers satisfying 1\leq u_i<v_i\leq N and 1\leq w_i\leq 10^6, and indicate that the i-th edge connects vertices u_i and v_i with weight w_i. The degree of each vertex is guaranteed to be at least 2.
  • (x_i, y_i) represents the coordinates of the i-th vertex, which are integers satisfying 0\leq x_i,y_i\leq 1000. These are used to generate and visualize the graph, and you may skip reading them if you don't need them.
  • It is guaranteed that the given graph is a 2-edge connected planar graph such that if vertex i is placed at coordinates (x_i, y_i) and the edges are drawn as line segments connecting the endpoints, every pair of edges has no common points other than the endpoints.

Output

Let r_i (1\leq r_i\leq D) be the day on which the i-th edge is to be repaired. Then, output to Standard Output in the following format.

r_1 r_2 \cdots r_M

Show example

Input Generation

Let \mathrm{rand}(L,U) be a function that generates a uniform random integer between L and U, inclusive.

Generation of the graph

The number of vertices N is generated by N=\mathrm{rand}(500,1000). Randomly select N points (x_1,y_1),\cdots,(x_N,y_N) from the lattice points contained in a circle with center (500,500) and radius 500. If the Euclidean distance between (x_i,y_i) and an already selected point (x_j,y_j) (j<i) is less than or equal to 10, we select (x_i,y_i) again. A planar graph (V,E) with these points as vertex set V is constructed as follows.

First, compute Delaunay triangulation and set E as the set of edges of the triangulation. Generate a random real value p between 0 and 0.75. For each edge e\in E in random order, perform the following operation: remove e from E with probability p if the degree of both endpoints are at least 4. After completing the process for all edges, if the graph (V,E) is not 2-edge connected, then we restore E and we redo the process from generating p. The weight of each edge (u,v) is determined by \mathrm{round}(10^3\times \sqrt{(x_u-x_v)^2+(y_u-y_v)^2}).

Generation of D and K

D is generated by \mathrm{rand}(5, 30). Let K'=\mathrm{ceil}(M/D). K is generated by \mathrm{rand}(K'+1,2K').

Tools (Input generator and visualizer)

Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.