問題一覧 > 通常問題

No.2228 Creeping Ghost

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 94
作問者 : AngrySadEightAngrySadEight / テスター : hari64hari64 akakimidoriakakimidori
6 ProblemId : 8809 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-01-31 18:51:49

問題文

以下のような,$5$ 行 $5$ 列のマス目があり,$i$ 行 $j$ 列目のマスをマス $(i,j)$ と表します.最初,あなたはマス $(1,1)$ にいます.

2023-01-31-185119

あなたは,これから,$T$ 回にわたって移動を行います.各移動では,上下左右に隣接したマスのいずれかに移動します(その場にとどまることはできません).また,マス目の外への移動もできません.

さて,このマス目には幽霊が出現します.幽霊は,あなたが $4k(k \geq 1)$ 回目の移動をするのと同時に,あなたの $4(k-1)$ 回目の移動先のマスに移動します.(ただし,「$0$ 回目の移動先のマス」とは,マス $(1,1)$ のことを指すこととします.また,$3$ 回目の移動までは幽霊は出現しません.)

幽霊は,自分のいるマスと同じ行または同じ列のマスすべてを監視します.そのため,$4k(k \geq 1)$ 回目から $4k+3$ 回目までの移動先に次のいずれかの条件を満たすようなマスを選んだ場合,幽霊に見つかってしまいます.

  • $4(k-1)$ 回目の移動先のマスと,同じ行のマス.
  • $4(k-1)$ 回目の移動先のマスと,同じ列のマス.

幽霊に見つかることなく $T$ 回の移動を行える方法をひとつ求めてください.なお,本問題の制約でそのような移動方法が存在することが示せます.

上下左右とは(クリックで展開)

隣接するマスの移動の向きは,それぞれ次のように定義されます.

  • 上のマスへの移動:マス $(i,j)$ から,マス $(i-1,j)$ への移動のこと.
  • 下のマスへの移動:マス $(i,j)$ から,マス $(i+1,j)$ への移動のこと.
  • 左のマスへの移動:マス $(i,j)$ から,マス $(i,j-1)$ への移動のこと.
  • 右のマスへの移動:マス $(i,j)$ から,マス $(i,j+1)$ への移動のこと.

制約

  • $T$ は整数である.
  • $1 \leq T \leq 10^6$

入力

入力は以下の形式で標準入力から与えられる.

$T$

出力

幽霊に見つかることなく $T$ 回の移動を行える方法を,L,R,U,D からなる長さ $T$ の文字列 $S$ として出力せよ.

ここで,$S$ の $i$ 文字目が L,R,U,D であることは,$i$ 回目の移動の向きがそれぞれ左,右,上,下であることを表す.

なお,条件を満たす移動方法が複数ある場合は,どれを出力しても正解となる.

サンプル

サンプル1
入力
9
出力
RDRDRURUL

移動の様子を以下に示します.ただし,赤丸はあなたの移動先のマスを,赤星は幽霊のいるマスを,青く塗りつぶされたマスは幽霊に見つかるマスの範囲を表します.

2022-11-21-185945

この移動方法を行うと最後まで幽霊に見つからずに移動できるため,この移動方法は正解の一つとなります.なお,$8$ 回目の移動後は,幽霊は $4$ 回目の移動後のマスであるマス $(3,3)$ に移動しているため,移動先のマス $(1,5)$ で幽霊に見つかることはありません.

一方,例えば RDRDRURDU という移動方法を行った場合,下図のように,$8$ 回目の移動後に幽霊に見つかってしまうため,この移動方法は不正解となります.

2022-11-21-190609
サンプル2
入力
3
出力
DRU

$3$ 回目の移動までは幽霊は出現しないため,マス目の外に行かない限りどのような移動をしても正解となります.

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