第3回 RCO日本橋ハーフマラソン予選

A - ツーリストXの旅行計画

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

旅をこよなく愛するXは、N 個の都市を1日に1つずつ訪れて最初の都市に戻る巡回旅行の計画を立てようとしています。

具体的には、0日目にスタートの都市に宿泊し、1日目から N 日目間の毎日、今いる都市からその日に訪れる都市へ移動して観光と宿泊をします。
ここで、N 日目に訪れる都市はスタートの都市と決めています。

Xは管理しやすくするため各都市に 0 〜 N - 1 の番号を重複なくつけました。
しかし、訪れる順番をまだ決められていません。

歩くのが大好きなXは、都市間を徒歩で移動したいと考えています。
さらに、毎日の移動時間を一定にしてスケジュール管理を簡単にするために、1日の移動距離の分散を小さくしたいと考えています。

ここで、都市の位置、都市間の移動距離、移動距離の分散は次で定義されます。

番号 i の都市の座標は (x_{i},\ y_{i}) で表される。複数の都市が同一の座標に存在することもありうる。
都市間の移動距離はユークリッド距離で定義される。
分散 \(\mathit{variance}\) は、j 日目の移動距離を d_{j} 、移動距離の平均を \(\mathit{average}\) とすると、 \[ \mathit{variance} = \frac{1}{N} \sum_{j=1}^{N}(d_j - \mathit{average})^2 \] で定義される。

各都市の観光情報を収集するのに忙しいXの代わりに、移動距離の分散ができるだけ小さくなるような都市の訪問順を考えてあげてください。

各テストケースの得点および、この問題の得点は、次のように計算されます。

1つのテストケースの得点は、\(10^6\div(1+\mathit{variance})\) で計算された値の小数点以下を切り上げたものになります。
テストケースは全部で 50 個あります。各テストケースの得点の合計が、この問題の得点になります。

入力

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

N
x_{0} y_{0}
\(\vdots\)
x_{i} y_{i}
\(\vdots\)
x_{N-1} y_{N-1}

N は訪れる予定の都市の数を表す整数で、N=200 を満たします。
x_{i},\ y_{i} は番号 i の都市の座標を表す整数の組で、 0≤x_{i},\ y_{i}≤500 を満たします。

出力

i 行目に、 i 日目に訪れる都市の番号 c_{i} を出力してください。（c_{0} はスタートの都市です。）
c_{N}=c_{0} になるため、 c_{N} は出力しません。

c_{0}
\(\vdots\)
c_{i}
\(\vdots\)
c_{N-1}

テストケースの生成について

各都市の座標は一様ランダムに生成されています。

入力例1

注意: この入力はテストケースとしての制約を満たしていません。

出力例1

移動距離は順番に \(292.13\cdots, 370.91\cdots, 333.86\cdots, 380.82\cdots\)、
平均移動距離は \(344.43\cdots\)、分散は \(1218.01\cdots\) になり、スコアは \(821\) になります。

移動パスをビジュアライズした結果を以下に図示します。
短い移動距離のところを赤く、長い移動距離のところを青く、平均値に近い移動距離のところは緑に表示しています。

ジェネレータとテスターとサンプル入力データ

テストケースジェネレータ・テスター・サンプル入力データを次のリンクから提供しています。

ジェネレータ・テスター・サンプル入力データ

ビジュアライザ

入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。

このビジュアライザはデスクトップ版の Google Chrome および Mozilla Firefox の最新バージョン上で動作確認を行っています。全てのブラウザ環境で動作することを保証していません。特に、Internet Explorer 上では動作しないことが確認されています。
このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。

ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。

ビジュアライザ

input file

output file

average

variance

score

save as image

B - ファーマーXの収穫計画

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

家庭菜園を始めたXは、野菜の手入れと収穫の計画を立てています。

Xの庭は N 行 N 列の区画からなり、区画のi 行 j 列目には品質が A_{i,j} の野菜があります。各区画からはそれぞれ一度だけ野菜を収穫することができます。

Xは以下のどちらかの操作を最大で M 回実行することができます。各操作は、野菜がまだ収穫されていない区画をひとつ指定して実行します。野菜が既に収穫された区画を指定した場合、何もしません。

（1）手入れ：選んだ区画にある野菜の品質を 1 増やします。
（2）収穫：選んだ区画とその周辺の区画から野菜を収穫します。収穫するためには次の条件を満たす必要があります。
- 選んだ区画にある野菜の品質を Kとします。
- 選んだ区画から「まだ収穫されていない品質Kの野菜がある区画」だけを辿って上下左右に連結している区画の集合を S とします。（ S には選んだ区画自身を含みます。）
- S に含まれる区画が K 個以上の場合、S に含まれる全ての区画にある野菜を収穫します。
- S に含まれる区画が K 個未満の場合、何もしません。

Xが収穫する野菜の品質の合計値がなるべく大きくなるような計画を立ててください。

各テストケースの得点およびこの問題の得点は、次のように計算されます。

1つのテストケースでは、Xが収穫する野菜の品質の合計がそのまま得点になります。
テストケースは全部で 50 個あります。各テストケースの得点の合計が、この問題の得点になります。

入力

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

\(\begin{array}{lll}
    N ~ M & & \\
    A_{ 0,0 } & \ldots & A_{ 0,N-1 } \\
    \vdots & \ddots & \vdots \\
    A_{ N-1,0 } & \ldots & A_{ N-1,N-1 }
  \end{array}\)

N は庭の大きさを表す整数で、N = 50 を満たします。
M は許容される操作回数の最大値を表す整数で、M = 2500 を満たします。
A_{i,j} は i 行 j 列目の区画にある野菜の品質を表す整数で、1 ≤ A_{i,j} ≤ 9 を満たします。

出力

1行につき操作をひとつ、最大 M 行出力してください。

\(\begin{array}{lll}
    \mathit{op}_0 & r_0 & c_0 \\
    \mathit{op}_1 & r_1 & c_1 \\
    \vdots & & \\
  \end{array}\)

\(\mathit{op}_i\)は 手入れをする場合は1を、収穫する場合は2を出力し、その後に操作対象の区画（r_i 行 c_i 列目）をスペース区切りで出力してください。

テストケースの生成について

各ケースはテストケースジェネレータによって生成されています。
テストケースジェネレータは\(A_{i,j}\) を \([1, 9]\) の範囲の整数から一様ランダムに生成します。
テストケースジェネレータはページ下部のリンクより提供しています。

入力例1

出力例1

庭	説明	スコア
	入力された庭の様子です。このサンプルは制約 `N=50, M=2500` を満たしていません。	0
	最初の操作（`2 0 0`）では、 `(0,0)` から見た `S` に含まれる区画は `(0,0), (0,1), (0,2), (1,1)` の `4`つなので、収穫できる条件を満たしていません。`(1,1)` と斜め方向で隣接している区画 `(2,0)` は `S` に含まれない点に注意してください。	0
	次の4回の操作（`1 1 0`を4回繰り返し）で `(1,0)` にある野菜の品質を `1` から `5` に変更します。	0
	次の操作（`2 0 0`）では、 `(0,0)` から見た `S` に含まれる区画は `(0,0), (0,1), (0,2), (1,0), (1,1), (2,0)` の `6` つなので、収穫できる条件を満たしています。 `S` に含まれる `6` つの区画のそれぞれから、品質 `5` の野菜を収穫します。	30
	次の操作（`2 2 2`）では、 `(2,2)` にある野菜を収穫します。品質が `1` の野菜は単体で収穫することもできます。	31
	最後の操作（`1 2 1`）では、 `(2,1)` にある野菜の品質を `9` から `10` に変更します。 `A_{i,j}` は `1` 以上 `9` 以下の整数ですが、野菜の品質は手入れをすることで `10` 以上の整数になることもあります。	31

ジェネレータとテスターとサンプル入力データ

テストケースジェネレータ・テスター・サンプル入力データを次のリンクから提供しています。

ジェネレータ・テスター・サンプル入力データ

ビジュアライザ

入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。

このビジュアライザはデスクトップ版の Google Chrome および Mozilla Firefox の最新バージョン上で動作確認を行っています。全てのブラウザ環境で動作することを保証していません。特に、Internet Explorer 上では動作しないことが確認されています。
このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。

ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。

ビジュアライザ

input file

output file

fps

score delta

score

操作

収穫済みの区画を表示する

save as image