問題一覧 > スコア問題

No.5022 XOR Printer

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 57
作問者 : prussian_coder / テスター : butsurizuki
ProblemId : 12462 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-07-25 21:00:42

問題文

$N \times N$ のグリッドが与えられ、上から $i$ 番目、左から $j$ 番目のマス $(i,j)$ には$0 \le A_{i,j} < 2^{20}$を満たす整数 $A_{i,j}$ が書かれています。

また、あなたは数字$s=0$ を持っており、はじめは $(1,1)$ にいます。

下記の操作を最大 $T$ 回まで行い、操作が終了した際の最終的な$A_{i,j}$の総和 $S = \sum_{i=1}^{N}\sum_{j=1}^{N} A_{i,j}$ をできるだけ大きくしてください。

  1. 移動 : 上下左右に 1 マス移動する(ただし、盤面の外に出ることはできない)
    • U : $(i,j)$ から $(i-1,j)$ に移動(上に移動)
    • D : $(i,j)$ から $(i+1,j)$ に移動(下に移動)
    • L : $(i,j)$ から $(i,j-1)$ に移動(左に移動)
    • R : $(i,j)$ から $(i,j+1)$ に移動(右に移動)
  2. 書き込み : W ― 現在いるマス $(i,j)$ としたとき、 $A_{i,j}$を$A_{i,j}$ XOR $s$に書き換える
  3. コピー : C ― 現在いるマス $(i,j)$ としたとき、 $s$ を$s$ XOR $A_{i,j}$に書き換える
ビット単位 XOR とは 非負整数 $A$, $B$ のビット単位 XOR 、$A \oplus B$ は、以下のように定義されます。
  • $A \oplus B$ を二進表記した際の $2^k$ ($k \geq 0$) の位の数は、$A, B$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $1$、そうでなければ $0$ である。
例えば、$3 \oplus 5 = 6$ となります (二進表記すると: $011 \oplus 101 = 110$)。

得点

操作が終了した時点での$S = \sum_{i=1}^{N}\sum_{j=1}^{N} A_{i,j}$が得点となります。

合計で 50 個のテストケースがあり,各テストケースの合計が提出の得点となります。

ただし,1 つ以上のテストケースで不正な出力や実行時間制限超過となった場合,提出全体の判定が WATLE となります。

各参加者のスコアは,問題の「スコア順」タブから閲覧することができます。

入力

$N$ $T$
$A_{1,1}$ $A_{1,2}$ ⋯ $A_{1,N}$
$A_{2,1}$ $A_{2,2}$ ⋯ $A_{2,N}$
⋮
$A_{N,1}$ $A_{N,2}$ ⋯ $A_{N,N}$

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

  • $N=10$
  • $T=1000$
  • $0 \le A_{i,j} < 2^{20}$ ($1 \le i, j \le N$)
  • $A_{i,j}$は整数

出力

操作回数を$M ( \le T)$とした時、下記の形式で出力してください

$op_1$
$op_2$
⋮
$op_M$
  • 各 $op_k$ は U D L R W C のいずれかである

  • 下記のような出力を行った場合はWAと判定されます

    • 盤面外への移動を行った場合($(i,j)$ で $i < 1$ または $i > N$ または $j < 1$ または $j > N$ になる移動)
    • 操作回数が $T$ を超えた場合
    • 無効な操作文字を出力した場合

サンプル

サンプル1
入力
10 1000
264226 49169 452706 349656 591257 939313 965593 85397 632720 206018
566467 227769 615110 36900 345036 944860 703330 25814 842273 504621
820650 600306 657703 890023 445115 285847 371164 351616 509743 394296
81048 469097 173897 292799 386172 959727 149443 413245 589783 630430
916789 148189 268015 64518 295892 1046550 120834 270207 633559 440055
14749 933562 780924 54922 973454 480092 573280 261141 875995 51989
102482 891735 665329 563073 111119 714504 173520 502300 1015148 932589
434745 808253 755323 1034601 1032220 817896 683830 91987 707464 75264
12567 780789 971178 299603 190120 21290 1046392 559226 979416 364764
1023915 637535 261266 55386 617350 609300 1009204 1048372 583444 40394
出力
R
W
C
D
L
W
U

上記は出力形式を示す例であり、最適解を意味しません。

入力生成方法

  • $A_{i,j}$は$0$以上$2^{20}$未満の整数の中から一様ランダムに選ばれます。

ツール(入力ジェネレータ・ビジュアライザ)

  • Web版: ローカル版より高性能でアニメーション表示が可能です。
  • ローカル版: サンプル入力,入力生成コード,ローカルテスタ (C++)などが格納されています。詳細な使い方については、README.mdを参照してください。

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