Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
N \times N のマス目で表される洞窟がある。 一番左上のマスの座標を (0,0) とし、そこから下方向に i マス、右方向に j マス進んだ先のマスの座標を (i,j) とする。 洞窟の周囲は壁で囲まれており、外に出ることはできない。
洞窟内には岩と M 種類の鉱石が散らばっている。 また、洞窟内の異なる M 個のマスには穴があり、i 種類目の鉱石を全て i 番目の穴に落としたい。 岩については、どの穴に落としてもよく、また洞窟内に放置してもよい。 あなたは以下の操作を 最大で 10000 回 行うことができる。
- 上下左右に隣接するマスへ移動する。移動先に穴・岩・鉱石があっても移動できる。
- 現在位置にある岩・鉱石を上下左右に隣接するマスへ運ぶ。運ぶ先にすでに別の岩・鉱石があってはならない。運ぶ先は穴でもよい。 運んだ先が穴であった場合、岩・鉱石は穴に落ちて取り除かれる。あなたの現在位置は運んだ先のマスになる。
- 現在位置にある岩・鉱石を、上下左右のいずれかの方向に転がす。転がした岩・鉱石は、岩・鉱石・壁にぶつかって止まるか、穴に落ちるまで一直線に転がる。あなたの現在位置は変化しない。
転がす操作は、より詳細には以下の繰り返しによって処理される。
- 転がっている方向に隣接するマスが穴である場合、岩・鉱石は穴に落ちて取り除かれる。
- 転がっている方向に隣接するマスに岩・鉱石がある、または N \times N の外に出る場合、現在のマスで停止する。
- 上記のどちらにも該当しない場合、隣接するマスへ移動し、処理を繰り返す。
転がる速度は非常に速いため、あなたの次の行動の前に必ず停止するか、穴に落ちて取り除かれる。
できるだけ少ない行動回数ですべての鉱石を対応する穴に落としてほしい。
得点
出力した行動列の長さを T (\leq 10000)、初期盤面における鉱石の総数を K、正しい穴に落とすことができた鉱石の総数を A としたとき、以下の得点が得られる。
- A=K の場合、\mathrm{round}(10^6\times(1+\log_2{\frac{10000}{T}}))
- A<K の場合、\mathrm{round}(10^6\times\frac{A}{K})
入力生成方法の違いにより、問題は A・B・C の 3 問 に分かれている。 それぞれの問題には 150 個のテストケース があり、各テストケースの得点の合計がその問題に対する提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 各問題に対して獲得した最高得点の総和で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数のチームが得た場合、提出時刻に関わらず同じ順位となる。
入力
入力は以下の形式で標準入力から与えられる。
N M
C_0
\vdots
C_{N-1}
- 盤面の大きさ N は、すべてのテストケースにおいて N = 20 で固定されている。
- 鉱石の種類数 M は、問題ごとに固定されている。詳しくは 「入力生成方法」 の項目を参照せよ。
- 各 i = 0, 1, \dots, N-1 に対し、C_i は長さ N の文字列であり、その j 文字目は以下のようにマス (i, j) の初期状態を表す。
@: 岩が存在する。a-z: 鉱石が存在する。A-Z: 穴が存在する。.: 何も存在しない。
鉱石と穴はアルファベットの大文字・小文字が対応している。
たとえば、文字 a で表される鉱石を落とすべき穴は、文字 A で表される。
最初の M 個のアルファベットが使用され、同じ種類の鉱石は複数存在する可能性があるが、同じ種類の穴は必ず 1 つだけである。
あなたは初期状態で穴 A のマスにいる。
出力
t 手目の操作は、行動の種類番号 a_t \in \{1,2,3\} (1:移動、2:運ぶ、3:転がす) と上下左右の方向を表す文字 d_t \in \{U,D,L,R\} のペア (a_t, d_t) で表される。 例えば、(3, R) は現在位置にある岩・鉱石を右方向に転がす操作である。
このとき、以下の形式で標準出力に出力せよ。
a_0 d_0
\vdots
a_{T-1} d_{T-1}
サンプルプログラム
N, M = map(int, input().split())
grid = [list(input()) for _ in range(N)]
# 現在位置の取得
pi = 0
pj = 0
for i in range(N):
for j in range(N):
if grid[i][j] == 'A':
pi = i
pj = j
# 右方向に移動して岩・鉱石を見つけたら穴に運ぶ
for j in range(pj + 1, N):
if grid[pi][j] == '@' or 'a' <= grid[pi][j] and grid[pi][j] <= 'z':
print('1 R\n' * (j - pj), end='')
print('2 L\n' * (j - pj), end='')
elif 'A' <= grid[pi][j] and grid[pi][j] <= 'Z':
break
# 下方向に移動して岩・鉱石を見つけたら穴に転がす
for i in range(pi + 1, N):
if grid[i][pj] == '@' or 'a' <= grid[i][pj] and grid[i][pj] <= 'z':
print('1 D\n' * (i - pi), end='')
print('3 U\n', end='')
pi = i
elif 'A' <= grid[i][pj] and grid[i][pj] <= 'Z':
break
入力生成方法
入力生成方法は問題ごとに異なる。 大まかには、以下の表のような入力が生成される。
| 問題 | M | 岩 |
|---|---|---|
| A | 1 | 少ない |
| B | 3 | 存在しない |
| C | 1 | 大量 |
A 問題
M = 1 で固定されている。
- 穴
Aの配置: N^2 マスの中からランダムに 1 マス選択する。 - 鉱石
aの配置: 残りの N^2 - 1 マスの中からランダムに 2N マス選択する。 - 岩
@の配置: 残りの N^2 - 1 - 2N マスの中からランダムに 2N マス選択する。
B 問題
M = 3 で固定されている。
- 穴
A、B、Cの配置: N^2 マスの中から異なる 3 マスをランダムに選択する。 - 鉱石
aの配置: 残りの N^2 - 3 マスの中からランダムに N マス選択する。 - 鉱石
bの配置: 残りの N^2 - 3 - N マスの中からランダムに N マス選択する。 - 鉱石
cの配置: 残りの N^2 - 3 - 2N マスの中からランダムに N マス選択する。
最後に、各穴から空きマスまたは対応する鉱石が存在するマスのみを通って、すべての対応する鉱石に到達可能であることを確認する。 到達不可能な鉱石がある場合、生成をやり直す。
C 問題
M = 1 で固定されている。
- 岩
@の配置: 各マス (i, j) に対し、h_{i,j} = \mathrm{noise}(i/10, j/10) を生成する。ここで、\mathrm{noise}(y, x) は二次元のPerlin noiseを生成する関数である。h_{i,j} の値が大きい順に上位 N^2/2 マスに岩を配置する。 - 穴
Aの配置: 残りの N^2/2 マスの中からランダムに 1 マス選択する。 - 鉱石
aの配置: 残りの N^2/2 - 1 マスの中からランダムに 2N マス選択する。
ツール(入力ジェネレータ・スコア計算)
- ローカル版: 使用するにはRust言語のコンパイル環境をご用意下さい。
- Windows用のコンパイル済みバイナリ: Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。
コンテスト期間中に、チーム外とのビジュアライズ結果の共有や解法・考察に関する言及は禁止されています。ご注意下さい。
入力例 1
20 1 ..a.@....a.....a.... ..@........@..a.@a@. ..aa...a..@.....a... .............a.....@ .....@.a.....a@@.... ..a..a@..a......@... .@a.@aa...........a@ ...............@.a.. .a......@@@.a....... ........@.@..a.....a .a.A..a....@....a..@ ......@..@@......... ..@@....a..@@.a..... ......a.....@..a.... ...................a @@.....@....a.a.a... .....@.......a...@.. ...@......@...a....a ............a..@.... .......a.@..........
出力例 1
1 R 1 R 1 R 2 L 2 L 2 L 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 1 D 1 D 3 U 1 D 1 D 1 D 1 D 1 D 3 U
Problem Statement
There is a cave represented by an N \times N grid. Let (0,0) be the coordinates of the top-left square, and (i,j) be the coordinates of the square located i squares down and j squares to the right from there. The cave is surrounded by walls, and it is not possible to move outside.
Inside the cave, there are rocks and M types of ores scattered across the grid. Additionally, there are M distinct squares that contain holes, and you need to drop all ores of type i into the i-th hole. Rocks may be dropped into any hole or left inside the cave. You can perform the following operations at most 10000 times.
- Move to an adjacent square in any of the four directions (up, down, left, or right). You can move even if the destination square contains a hole, rock, or ore.
- Carry a rock or ore at your current position to an adjacent square in any of the four directions. The destination must not already contain another rock or ore. The destination may be a hole. If the destination is a hole, the rock or ore falls into it and is removed. Your position moves to the destination square.
- Roll the rock or ore at your current position in one of the four directions. The rolled rock or ore continues moving in a straight line until it either collides with a rock, ore, or wall, or falls into a hole. Your position does not change.
The rolling operation is processed in more detail through the following repeated steps:
- If the adjacent square in the rolling direction is a hole, the rock or ore falls into it and is removed.
- If the adjacent square in the rolling direction contains a rock or ore, or if it is outside the N \times N grid, the rock or ore stops in the current square.
- Otherwise, it moves to the adjacent square and repeats the process.
The rolling speed is very fast, so the rock or ore will always stop or fall into a hole before your next action.
Your goal is to drop all ores into their corresponding holes using as few actions as possible.
Scoring
Let T (\leq 10000) be the length of the output action sequence, K be the total number of ores in the initial grid, and A be the total number of ores successfully dropped into the correct holes. The score is calculated as follows:
- If A = K, then the score is \mathrm{round}(10^6 \times (1+\log_2{\frac{10000}{T}})).
- If A < K, then the score is \mathrm{round}(10^6 \times \frac{A}{K}).
The problem is divided into three subproblems: A, B, and C, based on different input generation methods. Each subproblem contains 150 test cases, and the total score for a submission to that subproblem is the sum of the scores from all test cases in it. 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 final ranking is determined by the sum of the highest scores obtained for each subproblem, and there will be no system test after the contest. If more than one team gets the same score, they will be ranked in the same place regardless of the submission time.
Input
Input is given from Standard Input in the following format:
N M
C_0
\vdots
C_{N-1}
- The grid size N is fixed at N = 20 for all test cases.
- The number of ore types M is fixed for each subproblem. See the "Input Generation" section for details.
- For each i = 0, 1, \dots, N-1, C_i is a string of length N, where the j-th character represents the initial state of square (i, j) as follows:
@: A rock is present.a-z: An ore is present.A-Z: A hole is present..: The square is empty.
Ores and holes correspond based on uppercase and lowercase letters.
For example, an ore represented by the character a corresponds to the hole represented by the character A.
The first M letters of the alphabet are used. There may be multiple ores of the same type, but there is exactly one hole for each type.
You start at the square containing hole A in the initial state.
Output
The operation at step t is represented by a pair (a_t, d_t), where a_t \in \{1,2,3\} denotes the action type (1:Move, 2:Carry, 3:Roll), and d_t \in \{U,D,L,R\} represents the direction (Up, Down, Left, Right).
For example, (3, R) denotes the action of rolling the rock or ore at the current position to the right.
Then, output to Standard Output in the following format.
a_0 d_0
\vdots
a_{T-1} d_{T-1}
Sample Solution
N, M = map(int, input().split())
grid = [list(input()) for _ in range(N)]
# Retrieve the current position
pi = 0
pj = 0
for i in range(N):
for j in range(N):
if grid[i][j] == 'A':
pi = i
pj = j
# Move to the right and carry any rock or ore found into the hole
for j in range(pj + 1, N):
if grid[pi][j] == '@' or 'a' <= grid[pi][j] and grid[pi][j] <= 'z':
print('1 R\n' * (j - pj), end='')
print('2 L\n' * (j - pj), end='')
elif 'A' <= grid[pi][j] and grid[pi][j] <= 'Z':
break
# Move downward and roll any rock or ore found into the hole
for i in range(pi + 1, N):
if grid[i][pj] == '@' or 'a' <= grid[i][pj] and grid[i][pj] <= 'z':
print('1 D\n' * (i - pi), end='')
print('3 U\n', end='')
pi = i
elif 'A' <= grid[i][pj] and grid[i][pj] <= 'Z':
break
Input Generation
The input generation method differs for each subproblem. The inputs are roughly generated as shown in the table below.
| Subproblem | M | Rocks |
|---|---|---|
| A | 1 | Few |
| B | 3 | None |
| C | 1 | Many |
Subproblem A
M = 1 is fixed.
- Placement of hole
A: Randomly select one square from the N^2 squares. - Placement of ore
a: Randomly select 2N squares from the remaining N^2 - 1 squares. - Placement of rocks
@: Randomly select 2N squares from the remaining N^2 - 1 - 2N squares.
Subproblem B
M = 3 is fixed.
- Placement of holes
A,B, andC: Randomly select three distinct squares from the N^2 squares. - Placement of ore
a: Randomly select N squares from the remaining N^2 - 3 squares. - Placement of ore
b: Randomly select N squares from the remaining N^2 - 3 - N squares. - Placement of ore
c: Randomly select N squares from the remaining N^2 - 3 - 2N squares.
Finally, ensure that from each hole, it is possible to reach all corresponding ores by passing only through empty squares or squares containing that ore. If there exists an ore that is unreachable, the generation process is repeated.
Subproblem C
M = 1 is fixed.
-
Placement of rocks
@: For each square (i, j), generate h_{i,j} = \mathrm{noise}(i/10, j/10). Here, \mathrm{noise}(y, x) is a function that generates two-dimensional Perlin noise. The top N^2/2 squares with the highest h_{i,j} values are assigned rocks. -
Placement of hole
A: Randomly select one square from the remaining N^2/2 squares. - Placement of ore
a: Randomly select 2N squares from the remaining N^2/2 - 1 squares.
Tools (Input generator and score calculation)
- 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 outside of the team during the contest is prohibited.
Sample Input 1
20 1 ..a.@....a.....a.... ..@........@..a.@a@. ..aa...a..@.....a... .............a.....@ .....@.a.....a@@.... ..a..a@..a......@... .@a.@aa...........a@ ...............@.a.. .a......@@@.a....... ........@.@..a.....a .a.A..a....@....a..@ ......@..@@......... ..@@....a..@@.a..... ......a.....@..a.... ...................a @@.....@....a.a.a... .....@.......a...@.. ...@......@...a....a ............a..@.... .......a.@..........
Sample Output 1
1 R 1 R 1 R 2 L 2 L 2 L 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 1 R 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 2 L 1 D 1 D 3 U 1 D 1 D 1 D 1 D 1 D 3 U
Time Limit: 2 sec / Memory Limit: 1024 MiB
Time Limit: 2 sec / Memory Limit: 1024 MiB