結果
| 問題 |
No.5022 XOR Printer
|
| ユーザー |
 ra5anchor
|
| 提出日時 | 2025-07-31 20:56:03 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 562 ms / 2,000 ms |
| コード長 | 10,649 bytes |
| コンパイル時間 | 446 ms |
| コンパイル使用メモリ | 82,896 KB |
| 実行使用メモリ | 86,024 KB |
| スコア | 5,204,370,677 |
| 最終ジャッジ日時 | 2025-07-31 20:56:35 |
| 合計ジャッジ時間 | 28,751 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
import copy
import random
from time import perf_counter
import argparse
import sys
import math
MAX = 10**8
class TimeKeeper:
def __init__(self):
self.start_time = perf_counter()
def is_time_over(self, LIMIT):
return (perf_counter() - self.start_time) >= LIMIT
def time_now(self):
return (perf_counter() - self.start_time)
###########################################
def main(DEBUG):
tk = TimeKeeper()
if DEBUG == True:
LIMIT = 0.3
else:
LIMIT = 1.7
def cal_score(A):
N = 10
score = 0
for i in range(N):
for j in range(N):
score += A[i][j]
return score
def cal_score_sim(ANS):
N = 10
nowi = 0
nowj = 0
s = 0
B = [[0]*N for _ in range(N)]
for i in range(N):
for j in range(N):
B[i][j] = A[i][j]
if len(ANS) > 1000:
return -1
for c in ANS:
if c == "L":
nowj -= 1
elif c == "R":
nowj += 1
elif c == "U":
nowi -= 1
elif c == "D":
nowi += 1
elif c == "W":
B[nowi][nowj] ^= s
elif c == "C":
s ^= B[nowi][nowj]
if nowi < 0 or nowi >= N or nowj < 0 or nowj >= N:
print("outofrange", file=sys.stderr)
return -1
score = 0
for i in range(N):
for j in range(N):
score += B[i][j]
return score
def replay(ANS):
N = 10
nowi = 0
nowj = 0
s = 0
B = [[0]*N for _ in range(N)]
for i in range(N):
for j in range(N):
B[i][j] = A[i][j]
if len(ANS) > 1000:
return -1
for c in ANS:
if c == "L":
nowj -= 1
elif c == "R":
nowj += 1
elif c == "U":
nowi -= 1
elif c == "D":
nowi += 1
elif c == "W":
B[nowi][nowj] ^= s
elif c == "C":
s ^= B[nowi][nowj]
if nowi < 0 or nowi >= N or nowj < 0 or nowj >= N:
return -1
score = 0
minv = 10**18
for i in range(N):
for j in range(N):
score += B[i][j]
if B[i][j] < minv:
minv = B[i][j]
mini, minj = i, j
maxi, maxj = mini, minj
maxv = 0
for di in [-1,0,1]:
for dj in [-1,0,1]:
ii = mini + di
jj = minj + dj
if ii < 0 or ii >= N or jj < 0 or jj >= N:
continue
if B[ii][jj] > maxv:
maxv = B[ii][jj]
maxi = ii
maxj = jj
remain = 0
dist1 = abs(nowi-maxi) + abs(nowj-maxj)
dist2 = abs(maxi-mini) + abs(maxj-minj)
while dist1 + dist2 + 3 > remain:
c = ANS.pop()
remain += 1
if c == "L":
nowj += 1
elif c == "R":
nowj -= 1
elif c == "U":
nowi += 1
elif c == "D":
nowi -= 1
elif c == "W":
B[nowi][nowj] ^= s
elif c == "C":
s ^= B[nowi][nowj]
# コピー・印刷処理は省略
dist1 = abs(nowi-maxi) + abs(nowj-maxj)
dist2 = abs(maxi-mini) + abs(maxj-minj)
# 目的地へ向かう
if s < 2**19:
res = goto(nowi, nowj, maxi, maxj)
ANS.extend(res)
nowi = maxi
nowj = maxj
# Copy
ANS.append("C")
# 目的地へ向かう
res = goto(nowi, nowj, mini, minj)
ANS.extend(res)
nowi = mini
nowj = minj
# Copy
ANS.append("C")
# Print
ANS.append("W")
# return mini, minj, nowi, nowj, s
# return score
return ANS
def goto(nowi, nowj, toi, toj):
res = []
di = toi - nowi
dj = toj - nowj
if di > 0:
for _ in range(di):
res.append("D")
else:
for _ in range(abs(di)):
res.append("U")
if dj > 0:
for _ in range(dj):
res.append("R")
else:
for _ in range(abs(dj)):
res.append("L")
return res
def get_order(w_pos, nowi, nowj):
# greedy
w = []
while len(w_pos)>0:
w_pos.sort(key=lambda x: -abs(x[0]-nowi)-abs(x[1]-nowj))
(toi, toj) = w_pos.pop()
w.append((toi, toj))
nowi = toi
nowj = toj
return w
def get_order2(w_pos):
# zigzag
idx = dict()
cnt = 0
for i in range(N):
if i%2==0:
for j in range(N):
idx[(i,j)] = cnt
cnt += 1
else:
for j in reversed(range(N)):
idx[(i,j)] = cnt
cnt += 1
w_pos.sort(key=lambda x: idx[x[0],x[1]])
return w_pos
def solve(tk, LIMIT):
X = [[0]*N for _ in range(N)]
for i in range(N):
for j in range(N):
X[i][j] = A[i][j]
nowi = 0
nowj = 0
s = 0
actions = []
# for k in range(20): # k:keta
for k in range(10): # k:keta
if tk.is_time_over(LIMIT):
break
if len(actions) > 1000:
break
bestv = 0
minturn = 10000
nowi0, nowj0 = nowi, nowj
s0 = s
max_loop = 100
for loop in range(max_loop):
X1 = copy.deepcopy(X)
actions1 = []
nowi, nowj = nowi0, nowj0
s = s0
# sを設定する（色々試して
xnow = s >> 20-1-k & 1
kouho = []
for i in range(N):
for j in range(N):
# if (X[i][j] >> (20-1-k)) & 1 == 1:
if (X1[i][j] >> 20-1-k+1 == (1 << k) - 1) and (X1[i][j] >> 20-1-k & 1 == 1-xnow):
ti, tj = i, j
d = abs(nowi-i) + abs(nowj-j)
kouho.append((d, ti, tj))
kouho.sort()
if len(kouho)==0:
print(f"not found kouho {k=} -> break", file=sys.stderr)
break
# d, ti, tj = kouho[0]
d, ti, tj = kouho[random.randrange(len(kouho))]
# 目的地へ向かう
res = goto(nowi, nowj, ti, tj)
actions1.extend(res)
nowi = ti
nowj = tj
# Copyして完成
actions1.append("C")
s ^= X1[nowi][nowj]
# 書き込みする地点列挙
w_pos = []
for i in range(N):
for j in range(N):
if X1[i][j] ^ s > X1[i][j]:
# if (X[i][j] >> (20-1-k)) & 1 == 0:
# if (X[i][j] >> 20-1-k+1 == (1 << k) - 1) and (X[i][j] >> 20-1-k & 1 == 0):
w_pos.append((i, j))
if len(w_pos) == 0:
print(f"not found w_pos {k=} -> break", file=sys.stderr)
break
# 最大値の地点は使用せずに残す
mxv = 0
for (toi, toj) in w_pos:
v = X1[toi][toj]
if v > mxv:
mxv = v
mxi, mxj = toi, toj
w_pos.remove((mxi, mxj))
# 巡回する順番決め
w_pos_ordered = get_order(w_pos, nowi, nowj)
# w_pos_ordered = get_order2(w_pos)
# 一つ残して巡回
for (toi, toj) in w_pos_ordered:
res = goto(nowi, nowj, toi, toj)
actions1.extend(res)
nowi = toi
nowj = toj
# Print
actions1.append("W")
X1[nowi][nowj] ^= s
# 最後の一つはsに書き込む
toi, toj = mxi, mxj
res = goto(nowi, nowj, toi, toj)
actions1.extend(res)
nowi = toi
nowj = toj
# Copy
actions1.append("C")
s ^= X1[nowi][nowj]
# 暫定スコア
v = 0
for i in range(N):
for j in range(N):
v += X1[i][j]
turn = len(actions1)
if turn < minturn:
# if v > bestv:
print(f"best: {v=} {turn=} loop: {loop}", file=sys.stderr)
bestv = v
minturn = turn
best_actions = actions1[:]
best_X = copy.deepcopy(X1)
best_s = s
best_nowi, best_nowj = nowi, nowj
X = copy.deepcopy(best_X)
actions.extend(best_actions)
s = best_s
nowi, nowj = best_nowi, best_nowj
print(f"{k=} skip ({nowi} {nowj}) turn {len(actions)}", file=sys.stderr)
print(f"{k=} {s=} {bin(s)=}", file=sys.stderr)
print(X, file=sys.stderr)
return actions
N, T = map(int, input().split())
# N=10, T=1000
A = [list(map(int, input().split())) for _ in range(N)]
ANS = solve(tk, LIMIT)
sc0 = cal_score_sim(ANS[:T])
# 最小値のマスを修正
# T=1000時点での最小値(i,j)および(nowi,nowj)、s値を再計算
ANS = replay(ANS[:T])
# print(f"T: {len(ANS)}", file=sys.stderr)
# ANS = ANS[:T]
sc1 = cal_score_sim(ANS)
print(f"SC: {sc1} <- {sc0}", file=sys.stderr)
print(*ANS, sep='\n')
if __name__ == '__main__':
parser = argparse.ArgumentParser(description='Debug mode')
parser.add_argument('--debug', action='store_true', help='Enable debug mode')
args = parser.parse_args()
main(args.debug)