Time Limit: 4 sec / Memory Limit: 1024 MB
問題文
人気ゲーム実況者として活動しているXは、新しい動画の制作に取り組んでいます。今回は、とあるパズルゲームを攻略することにしました。
このゲームの目的は、 H行W列のマスからなるマップの中で、プレイヤーを動かしてできるだけ多くのコインを集めることです。詳しいルールは以下の通りです。なお、マップの一番上の行を 0 行目、一番左の列を 0 列目とします。
- マップの各マスは、壁のマス・コインのマス・罠のマス・空のマスのいずれかである
- マップの外周（0行目・H-1行目・0列目・W-1列目）は壁のマスである
- 初期状態では空のマスが1つだけあり、そこにプレイヤーがいる
- 1回のコマンドで、プレイヤーを上下左右いずれかの隣接したマスへ移動させることができる
- 移動先が壁のマスだった場合、移動せず現在のマスにとどまる
- プレイヤーがコインのマスに入った場合、コインを得る。そのマスからコインはなくなり、空のマスになる
- プレイヤーが罠のマスに入った場合、それ以降プレイヤーは移動できなくなる
- コマンドは最大 T 回与えることができる
このゲーム内には N 個のマップが用意されています。ただ高得点を取るだけでは面白くないと考えたXは、次のチャレンジをすることにしました。
- N 個のマップの中から K 個のマップを選ぶ
- それら K 個のマップを、同一のコマンドで操作する
マップの選び方と実行するコマンドを決め、得られるコインの数の合計を最大化してください。
各テストケースの得点および、この問題の得点は、次のように計算されます。
- 1つのテストケースの得点は、選んだ K 個のマップで得られたコインの数の合計です。
- テストケースは全部で 30 個あります。各テストケースの得点の合計が、この問題の得点になります。
入力
入力は以下の形式で標準入力から与えられます。
N K H W T
row_{0,0}
row_{0,1}
:
row_{0,H-1}
row_{1,0}
:
row_{N-1,H-1}
- N はマップの数を表す整数で、N=100 を満たします。
- K は使用するマップの数を表す整数で、K=8 を満たします。
- H はマップの行数を表す整数で、H=50 を満たします。
- W はマップの列数を表す整数で、W=50 を満たします。
- T はコマンドの回数の最大値を表す整数で、T=2,500 を満たします。
- row_{i,j} は i 番目のマップの j 行目を表す W 文字の文字列です。各文字は、
#,o,x,@のいずれかです。#は壁のマスを表します。oはコインのマスを表します。xは罠のマスを表します。@はプレイヤーがいるマスを表します。- 各マップの外周は
#であることが保証されます。 - 各マップに
@はただ一つ存在することが保証されます。
出力
1行目に、選択したマップの番号（0始まり）を表す整数を K 個、スペース区切りで出力してください。
2行目に、実行するコマンド列を表す T 文字以下の文字列を出力してください。
M_0 M_1 … M_{K-1}
commands
- M_0, M_1, …, M_{K-1} は、互いに異なる 0 以上 N 未満の整数です。
- commands の i 文字目は、i 個目のコマンドを表します。
- 各コマンドは、以下の文字によって表されます。
U- 現在のマスより1行小さいマスに移動します。（上に移動します）
D- 現在のマスより1行大きいマスに移動します。（下に移動します）
L- 現在のマスより1列小さいマスに移動します。（左に移動します）
R- 現在のマスより1列大きいマスに移動します。（右に移動します）
テストケースの生成について
各マップは次の手順で生成されます。
- 外周を壁のマスにする
- 外周以外のマスを、それぞれ確率 0.77 でコインのマスに、確率 0.20 で壁のマスに、確率 0.03 で罠のマスにする
- 外周以外のマスを1つ選び、空のマス（初期状態でプレイヤーがいるマス）に置き換える
入力例1
4 2 8 8 3 ######## #o#oooo# #ooooo## ##ooooo# #oooo#x# ##o#ooo# ##@ooox# ######## ######## ##xoooo# #oo#oox# #oooooo# #oooxoo# ##o@o#o# #o#oo#o# ######## ######## #ooo##o# #oo##oo# #ooo@oo# ###oooo# #o#xo#o# #ooooo## ######## ######## #ooo#oo# ##oooo## ##ooo#@# #oooooo# #oo#ooo# #oooo#x# ########
注意: この入力はテストケースとしての制約を満たしていません。
マップを以下に図示します。
出力例1
1 2 URR
マップ1とマップ2を選びました。全てのコマンドを実行後のマップの様子は以下のようになります。
- 1つめのコマンドでは、マップ1のプレイヤーは上に移動してコインを得ます。マップ2のプレイヤーは、上が壁のマスのため移動しません。
- 2つめのコマンドでは、マップ1のプレイヤーは右に移動して罠のマスに入ります。マップ2のプレイヤーは、右に移動してコインを得ます。
- 3つめのコマンドでは、マップ1のプレイヤーは罠のマスに入っているため移動できません。マップ2のプレイヤーは、右に移動してコインを得ます。
- マップ1で1個、マップ2で2個のコインを得たため、このテストケースで得られるスコアは、3点です。
ジェネレータとテスター
テストケースジェネレータとテスターを次のリンクから提供しています。
ビジュアライザ
入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。
- このビジュアライザは主要なブラウザ上で動作確認を行っていますが、全ての環境で動作することを保証していません。特に、Internet Explorer 上では動作しないことが確認されています。
- このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
- このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。
ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。
Time Limit: 4 sec / Memory Limit: 1024 MB
問題文
人気ゲーム実況者として活動しているXは、撮りためた動画の整理に取り組んでいます。
動画の読み込みに時間がかかるので調べたところ、どうやらファイルの断片化が進んでいるようでした。
Xの撮りためた動画は特殊なファイルストレージに、次のような条件で保存されています。
- 1つの動画ファイルはストレージ上の縦 H 行、横 W 列に並んだセクタ上に保存されている。
- 一番左上のセクタを (0,\ 0)、一番右下のセクタを (H - 1,\ W - 1) と表す。
- ファイルは D 個のセクタに分かれて保存されており、それらのセクタの位置は (r_{0},\ c_{0}),…,\ (r_{D-1},\ c_{D-1}) である。
- 上記に現れないセクタは空いていて、何も保存されていない。
- ファイルを読み込む際には次のような制限がある。
- ファイルを読み込むにはそのファイルを構成するセクタに (r_{0},\ c_{0}),…,\ (r_{D-1},\ c_{D-1}) の順にアクセスする必要がある。
- セクタにアクセスするために位置 (a,\ b) から (c,\ d) に移動するには |c - a| + |d - b| のコストがかかる。
- ファイル読み込みコストはこの移動コストの和である。つまり
Xは swap を繰り返してファイルの断片化を解消（デフラグ）し、ファイル読み込みコストを減らすことにしました。
swap とは縦 H 行、横 W 列に並んだセクタのうち、任意の2つのセクタ（データの有無は問わない）の状態を入れ替える操作を指します。
ただし、デフラグはストレージの寿命を縮めると聞いたことがあるXは swap 操作の回数を最大 K 回までとしました。
ゲーム実況で忙しいXのかわりにデブラグを行って、ファイル読み込みコストを最小化してください。
各テストケースの得点およびこの問題の得点は、次のように計算されます。
- 1つのテストケースでは、 max(0,\ (初期状態のコスト - 最終状態のコスト)/100) の小数点以下を切り上げた整数が得点になります。
- テストケースは全部で 30 個あります。各テストケースの得点の合計が、この問題の得点になります。
入力
入力は以下の形式で標準入力から与えられます。
H W D K
r_{0} c_{0}
:
r_{D-1} c_{D-1}
- H はセクタの行数を表す整数で、H = 200 を満たします。
- W はセクタの列数を表す整数で、W = 200 を満たします。
- D はファイルデータのあるセクタ数を表す整数で、D = 16000 を満たします。
- K は swap 操作の最大回数を表す整数で、K = 4000 を満たします。
- r_{i}\ c_{i} は データの書かれているセクタの位置を表す座標で、以下の条件を満たします。
- 0 ≤ r_{i} < H
- 0 ≤ c_{i} < W
- (r_{i},\ c_{i}) はすべて異なる
出力
swap するセクタの位置の組を1行に1つ、最大 K 行まで出力してください。
セクタ (a,\ b) と (c,\ d) を入れ替える場合は、a\ b\ c\ d と出力してください。
a_{0} b_{0} c_{0} d_{0}
a_{1} b_{1} c_{1} d_{1}
:
- 同じセクタの swap も可能です。
- K行より多い出力や範囲外の swap があった場合は WA (Wrong Answer) になります。
テストケースの生成について
各ケースはテストケースジェネレータによって生成されています。
テストケースジェネレータは一様乱数にしたがってケースを生成しています。
テストケースジェネレータはページ下部のリンクより提供しています。
入力例1
5 5 5 4000 0 0 4 4 4 0 0 4 2 2
注意: この入力はテストケースとしての制約を満たしていません。
セクタの状態を以下に図示します。
ファイル読み込みコストは 8 + 4 + 8 + 4 = 24 です。
出力例1
2 2 0 4 1 2 4 4 3 1 4 0 3 3 2 2 4 3 0 4
出力された swap 実行後のセクタの状態は以下のようになります。
ファイル読み込みコストは 3 + 3 + 2 + 1 = 9 となります。
このケースでの得点は max(0, (24 - 9)/100) = 0.15 の小数点以下切り上げで 1 となります。
ジェネレータとテスター
テストケースジェネレータとテスターを次のリンクから提供しています。
ビジュアライザ
入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。
- このビジュアライザは主要なブラウザ上で動作確認を行っていますが、全ての環境で動作することを保証していません。特に、Internet Explorer 上では動作しないことが確認されています。
- このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
- このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。
ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。