問題一覧 > 通常問題

No.1315 渦巻洞穴

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 26
作問者 : 👑 りあんりあん / テスター : tempura_pptempura_pp
3 ProblemId : 5541 / 出題時の順位表
問題文最終更新日: 2020-12-13 08:54:50

問題文

以下の図で示されるような無限に広がる二次元グリッドを考えます。各セルには、セル $1$ を中心に反時計回りに渦を巻くように番号が振られています。

あなたはセル $S$ からスタートして、上下左右に隣接するセルのいずれかに移動する、ということを繰り返しセル $T$ まで移動します。
このとき、通ったセル($S, T$ を含む)の番号のビットごとの排他的論理和(排他的論理和 - Wikipedia)がペナルティとして計算されます(同じセルに複数回訪れた場合は訪れた回数分計上する)。
より正確には、通ったセルの番号が順番に $C_0 (= S), C_1, C_2, \ \ldots \ , C_{K-1}, C_K (= T)$ だった場合、ペナルティは $C_0 \oplus C_1 \oplus C_2 \oplus \cdots \oplus C_{K-1} \oplus C_K$ で計算されます。


セル $S$ からセル $T$ まで移動する方法のうち、以下の 2 つの条件の両方を満たすものを一つ求めてください。

  • セル $S$ からセル $T$ まで移動する方法のうち、ペナルティが最小である
  • ステップ数(上下左右の隣接するセルに移動する回数)が $2 \times 10^5$ 以下である

条件を満たすものが複数ある場合は、そのうちのいずれを出力しても構いません(ステップ数を最小化する必要はないことに注意してください)。
なお、本問題の制約下で 2 つの条件の両方を満たすものが必ず存在する(ペナルティが最小であるような任意の移動のうち、ステップ数が $2 \times 10^5$ 以下であるものが必ず存在する)ことが証明できます。

入力

$S$ $T$

1 行にスタートのセルの番号を表す整数 $S$ とゴールのセルの番号を表す整数 $T$ が半角スペース区切りで与えられます。

入力は以下の制約を満たします。

  • 入力は全て整数
  • $1 \le S, T \le 10^9$
  • $S \neq T$

出力

$X$
$K$
$D_1 D_2 \ldots D_K$

期待される出力は 3 行からなります。

1 行目に、ペナルティの最小値 $X$ を整数で出力してください。

2 行目に、ステップ数(上下左右の隣接するセルに移動する回数)$K$ を整数で出力してください。なお、$1 \le K \le 2 \times 10^5$ を満たす必要があります。

3 行目に、移動方法を表す文字列 $D$ を出力してください。文字列 $D$ は以下の条件を全て満たす必要があります。

  • $D$ は長さ $K$ の文字列
  • $D$ はL, R, U, D のみからなる
  • 隣接するセルへの移動を $i \ (0 \le i \le K)$ 回繰り返した後にいるセルの番号を $C_i$ としたとき、以下の条件を全て満たす
    • $C_0 = S$
    • $C_K = T$
    • $1 \le i \le K$ を満たす全て整数の $i$ に対し、
      • $D_i =$ L ならば、$C_i$ は $C_{i-1}$ の左に隣接するセルである
      • $D_i =$ R ならば、$C_i$ は $C_{i-1}$ の右に隣接するセルである
      • $D_i =$ U ならば、$C_i$ は $C_{i-1}$ の上に隣接するセルである
      • $D_i =$ D ならば、$C_i$ は $C_{i-1}$ の下に隣接するセルである
    • $C_0 \oplus C_1 \oplus \cdots \oplus C_K = X$

解が複数ある場合、そのうちのいずれを出力しても構いません。

サンプル

サンプル1
入力
3 13
出力
0
2
UR

セル $3$ から上に隣接するセル $14$ を経由してセル $13$ に行くことで、ペナルティは $ \ 3 \oplus 14 \oplus 13 = 0 \ $ となります。

サンプル2
入力
23 16
出力
0
7
LLUURUU

サンプル3
入力
4 8
出力
0
8
DDLDDRUU

途中で $T$ を経由したり同じセルを 2 回以上経由することも可能です。

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