/ 
実行時間制限: 3 sec / メモリ制限: 1024 MiB
ストーリー
AtCoder 王国は N \times N のグリッド状の区画に区切られており、各区画にはそれぞれ異なる人数の国民が住んでいる。 国王の高橋君は、国民からの好感度を上げるため、縦・横・斜めに隣接する区画を辿りながら、すべての区画を一度ずつ訪問するツアーを計画している。 ツアーは日を追うごとに盛り上がっていくので、後の日に訪れた区画ほど、住人の高橋君への好感度が高くなる。 高橋君が得る好感度の総和がなるべく大きくなるようなツアーを計画してほしい。
問題文
N \times N の区画に区切られた王国がある。左上の区画を (0,0) とし、下方向に i 区画、右方向に j 区画進んだ区画を (i,j) とする。 区画 (i,j) には A_{i,j} 人の国民が住んでいる。
0 日目から N^2-1 日目までの N^2 日間で、すべての区画をちょうど一度ずつ訪問するツアーを考える。 k 日目に訪問する区画を (i_k, j_k) とする。
このとき、連続する 2 日に訪問する区画は、 縦・横・斜め に隣接していなければならない。 より厳密には、各 k=0,1,\dots,N^2-2 について
\[ \max\bigl(|i_k-i_{k+1}|,\ |j_k-j_{k+1}|\bigr)=1 \]
が成り立つ必要がある。 ツアーの開始区画と終了区画は任意に選んでよい。
ツアーの k 日目に訪問した区画では、住民 1 人あたり k の好感度が得られる。 このとき、高橋君が得る好感度の総和は
\[ \sum_{k=0}^{N^2-1} k\cdot A_{i_k, j_k} \]
である。
高橋君が得る好感度の総和がなるべく大きくなるような訪問順を求めよ。
得点
高橋君が得る好感度の総和を V としたとき、
\[ \mathrm{round}\left(\frac{V}{N^2}\right) \]
をそのテストケースにおける得点とする。
合計で 100 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。
入力
入力は以下の形式で標準入力から与えられる。
N
A_{0,0} \cdots A_{0,N-1}
\vdots
A_{N-1,0} \cdots A_{N-1,N-1}
- すべてのテストケースにおいて、N=200 で固定である。
- 区画 (i,j) の住民数 A_{i,j} は、1\leq A_{i,j}\leq N^2 を満たす整数である。
出力
ツアーの k 日目に訪問する区画を (i_k, j_k) とするとき、以下の形式で標準出力に出力せよ。
i_0 j_0
\vdots
i_{N^2-1} j_{N^2-1}
ただし、出力は以下の条件をすべて満たさなければならない。
- k=0,1,\cdots,N^2-1 について、i_k および j_k は 0 以上 N-1 以下の整数である。
- (i_k, j_k) (k=0,1,\cdots,N^2-1) は互いに異なる。
- k=0,1,\cdots,N^2-2 について、\max(|i_k-i_{k+1}|,\ |j_k-j_{k+1}|)=1 である。
入力生成方法
- すべてのテストケースにおいて N=200 である。
- 1 以上 N^2 以下の整数を一様ランダムに並び替え、それらを順に A_{0,0}, A_{0,1}, \cdots, A_{0,N-1}, A_{1,0}, \cdots, A_{N-1,N-1} とする。
ツール(入力ジェネレータ・ビジュアライザ)
- Web版: ローカル版より高性能でアニメーション表示が可能です。
- ローカル版: 使用するにはRust言語のコンパイル環境をご用意下さい。
- Windows用のコンパイル済みバイナリ: Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。
コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。
Story
The AtCoder Kingdom is divided into an N \times N grid of districts, and each district has a different number of citizens. To increase his popularity among the citizens, King Takahashi plans a tour that visits all districts exactly once by moving through districts adjacent vertically, horizontally, or diagonally. As the tour becomes more exciting day by day, districts visited on later days yield higher favor from their residents toward Takahashi. Please plan a tour so that the total favor Takahashi gains is as large as possible.
Problem Statement
There is a kingdom divided into an N \times N grid of districts. Let the top-left district be (0,0), and let the district reached by moving i districts downward and j districts to the right be (i,j). District (i,j) has A_{i,j} citizens.
Consider a tour that visits every district exactly once over N^2 days, from day 0 to day N^2-1. Let the district visited on day k be (i_k, j_k).
The districts visited on two consecutive days must be adjacent vertically, horizontally, or diagonally. More precisely, for each k=0,1,\dots,N^2-2,
\[ \max\bigl(|i_k-i_{k+1}|,\ |j_k-j_{k+1}|\bigr)=1 \]
must hold. The starting district and the ending district of the tour may be chosen arbitrarily.
For the district visited on day k of the tour, each resident contributes k favor. The total favor Takahashi gains is
\[ \sum_{k=0}^{N^2-1} k\cdot A_{i_k, j_k} \]
Find a visiting order that makes the total favor Takahashi gains as large as possible.
Scoring
Let V be the total favor Takahashi gains. Then the score for that test case is
\[ \mathrm{round}\left(\frac{V}{N^2}\right) \]
There are 100 test cases, and the score of a submission is the total score for each test case. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE , and the score of the submission will be zero. The highest score obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time.
Input
The input is given from Standard Input in the following format.
N
A_{0,0} \cdots A_{0,N-1}
\vdots
A_{N-1,0} \cdots A_{N-1,N-1}
- In all test cases, N=200.
- A_{i,j}, the number of citizens in district (i,j), is an integer satisfying 1\leq A_{i,j}\leq N^2.
Output
Let (i_k, j_k) be the district visited on day k of the tour. Output to Standard Output in the following format.
i_0 j_0
\vdots
i_{N^2-1} j_{N^2-1}
Your output must satisfy all of the following conditions.
- For k=0,1,\cdots,N^2-1, i_k and j_k are integers between 0 and N-1, inclusive.
- All (i_k, j_k) for k=0,1,\cdots,N^2-1 are distinct.
- For k=0,1,\cdots,N^2-2, \max(|i_k-i_{k+1}|,\ |j_k-j_{k+1}|)=1 holds.
Input Generation
- In all test cases, N=200.
- The integers from 1 to N^2 are shuffled uniformly at random, and assigned in order to A_{0,0}, A_{0,1}, \cdots, A_{0,N-1}, A_{1,0}, \cdots, A_{N-1,N-1}.
Tools (Input generator and visualizer)
- Web version: This is more powerful than the local version providing animations.
- Local version: You need a compilation environment of Rust language.
- Pre-compiled binary for Windows: If you are not familiar with the Rust language environment, please use this instead.
Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.