問題一覧 > スコア問題

No.5006 Hidden Maze

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 46
作問者 : 👑 platinumplatinum / テスター : butsurizukibutsurizuki
6 ProblemId : 8096 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-06-11 22:58:16

ストーリー

あなたはロボットを遠隔操作してとある建物の内部構造を調査しようとしています。建物の内部にはいくつかの壁があって通行できません。
壁がある方向にロボットが進もうとした場合、ロボットはそこに壁があることをあなたに伝えて入口まで引き返します。
あなたの目的は、建物の入口から出口までの経路を発見することです。
ただしこのロボットには不具合があり、一定の確率で進行方向に壁がない場合でも壁があると判定してしまうことがわかっています。

問題文

縦$\ 20\ $マス、横$\ 20\ $マスのグリッドが与えられます。グリッドの外周は壁であり、隣接するマスとマスの間にも壁が存在することがあります。
一番左上のマスの座標を$(0, 0)$とし、そこから下に$\ i\ $マス、右に$\ j\ $マス進んだ先のマスの座標を$(i, j)$とします。この建物の入口はマス$(0, 0)$、出口はマス$(19, 19)$に位置します。
途中で壁を通行しないかつ最終到達地点が出口である経路を「目的の経路」と呼ぶことにします。
目的の経路を発見するまで、以下の試行を繰り返してください。各試行においてロボットは入口から移動を開始します。

  • 上下左右の移動をそれぞれ U, D, L, R とし、移動経路を長さ$\ 400\ $以下の文字列として出力してください。
  • 出力された移動経路が目的の経路であった場合、ジャッジは$\ -1\ $を返します。その場合は直ちにプログラムを終了してください。
  • そうでない場合は、ロボットが移動できた回数が返されます。ただし、各移動において一定の確率$\ p\ $で移動方向に壁がない場合でも移動に失敗して試行を終了します。
  • $1001\ $回目の試行においてジャッジは$\ -1\ $を返すのでプログラムを直ちに終了してください。
目的の経路が出力された場合ジャッジは常に$\ -1\ $を返すことに注意してください。

得点

$t\ $回目の試行において目的の経路を出力した場合、$1001-t\ $の得点が得られます。ただし、試行回数が$\ 1001\ $以上となった場合はそのテストケースにおける得点は$\ 0\ $となります。
出力された文字列が U, D, L, R 以外の文字を含む場合は WA と判定されます。
テストケースは全部で$\ 100\ $個あり、各テストケースの得点の合計が提出の得点となります。
コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われません。
コンテストの順位は上の「スコア順」タブよりご覧ください。

入力

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

$H\ W\ p$

$H\ $はグリッドの行数、$W\ $はグリッドの列数であり、全てのテストケースにおいて$\ H=W=20\ $を満たします。
ロボットが移動に失敗する確率$\ p\ $は百分率で与えられます。$p\ $は$\ 6\ $以上$\ 15\ $以下の整数です。
全てのマスは入口から到達可能であることが保証されます。
また、各試行において文字列を出力後、一つの整数が標準入力から与えられます。
ジャッジの入力を必ず最後まで全て受け取ってください。行わなかった場合 WA となる可能性があります。

出力

各試行において、長さ$\ 400\ $以下の文字列を一つ出力してください。出力された文字列の長さが$\ 400\ $を超える場合、$401\ $文字目以降は無視されます。
各出力の後に標準出力をflushしてください。そうしない場合 TLE となる可能性があります。
なお、ジャッジが$\ -1\ $を返す前に提出プログラムが終了した場合およびジャッジが$\ -1\ $を返した後に出力を行った場合の挙動は未定義です。

サンプル

サンプル1
入力
5 5 10

このサンプルは説明のためにグリッドが小さくなっており、実際のテストケースには含まれません。
本ケースでは、ロボットは各移動において進行方向に壁がない場合でも$\ 0.1\ $の確率で移動に失敗します。
本ケースにおけるグリッドは以下の図の通りであるとします(入力では与えられません)。

例えば、以下のような試行が考えられます。

出力1
DDDDRRRR
入力1
2
出力2
RRRRDDDD
入力2
3
出力3
RRRDDDDR
入力3
-1

$1\ $回目の試行では、$3\ $回目の移動において進行方向に壁が存在するため移動に失敗し$\ 2\ $が返されました。
$2\ $回目の試行では、$4\ $回目の移動で進行方向に壁が存在しないもののロボットの不具合で移動に失敗し$\ 3\ $が返されました。
$3\ $回目の試行では、目的の経路を出力したため$\ -1\ $が返されました。このテストケースでは$\ 998\ $点を得ます。

入力生成方法

$L\ $以上$\ U\ $以下の整数値を一様ランダムに生成する関数を$\ rand(L,U)\ $で表す。
$i\ $番目のテストケースにおけるロボットが移動に失敗する確率を$\ p=6+(i-1) \% 10\ $とする。
また、入力としては与えられないが、壁の位置は以下の手順で決定される。
初めに外周を除く壁の総数$\ M=rand(100,200)\ $とし、以下の操作を$\ M\ $回繰り返す。
ただし壁を設置した際に到達不可能なマスが発生する場合または既に壁が設置してある位置を選択した場合は設置せずに操作をやり直す。

  • 壁の方向を決める乱数$\ D=rand(0,1)\ $を生成する。
  • $D=0\ $の場合、$i=rand(0,19),j=rand(1,19)\ $とし、マス$\ (i,j-1)\ $とマス$\ (i,j)\ $の間に壁を設置する。
  • $D=1\ $の場合、$i=rand(1,19),j=rand(0,19)\ $とし、マス$\ (i-1,j)\ $とマス$\ (i,j)\ $の間に壁を設置する。
各テストケースについて、確率$\ p\ $に基づいて各試行における最大移動可能回数があらかじめ定められている。
以下の操作を$\ 1000\ $回繰り返し、移動可能回数$\ t\ $を決定する。$\ i\ $回目の操作は以下の通りである。
  1. $1\ $以上$\ 100\ $以下の整数$\ c\ $を一様ランダムに生成する。
  2. $c\ $を生成した回数が$\ 400 \ $を超えた場合、$t_i=400\ $として操作を終了する。
  3. $c \leq p\ $であれば操作を終了し、$t_i = (cを生成した回数) - 1\ $とする。そうでなければ 1. に戻る。
$i\ $回目の試行では、進行方向に壁が存在するか、$\ t_i+1\ $回目の移動を試みた場合に移動に失敗する。

テストケース生成プログラムやジャッジプログラムは GitHub から入手できます。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。