結果
| 問題 |
No.5002 stick xor
|
| コンテスト | |
| ユーザー |
 ra5anchor
|
| 提出日時 | 2025-04-27 03:11:53 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 11,305 bytes |
| コンパイル時間 | 525 ms |
| コンパイル使用メモリ | 82,504 KB |
| 実行使用メモリ | 88,172 KB |
| スコア | 13,648 |
| 最終ジャッジ日時 | 2025-04-27 03:12:46 |
| 合計ジャッジ時間 | 35,901 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 10 TLE * 22 |
ソースコード
import copy
import random
from time import perf_counter
import argparse
import sys
import math
random.seed(0)
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)
class Solver:
def __init__(self, N, K, L, W, A):
self.N = N # グリッドサイズ
self.K = K # 操作回数
self.L = L # 長方形サイズリスト
self.W = W # 初期の白(0)の数
self.A0 = [row[:] for row in A]
def initialize(self):
# Aをリセット
self.A = [row[:] for row in self.A0]
def place(self, pos):
a, b, c, d = pos
for i in range(a, c+1):
for j in range(b, d+1):
self.A[i][j] = 1 - self.A[i][j]
def calscore(self, ans):
# ansでひっくり返した後の白(0)数を計算
A_ = [row[:] for row in self.A0]
for a, b, c, d in ans:
for i in range(a, c+1):
for j in range(b, d+1):
A_[i][j] = 1 - A_[i][j]
return sum((1 - A_[i][j]) for i in range(self.N) for j in range(self.N)) - self.W
def _greedy_initial(self, order):
# order は操作インデックスのリスト
self.initialize()
ans = [None] * self.K
B1 = 2
B2 = 5
for idx in order:
D = self.L[idx]
best_pos = (0, 0, 0, D-1)
mxcnt = -1
# 横向きスキャン
for i in range(self.N):
now = sum(self.A[i][j] for j in range(D))
bonus = B1 + (B1 if self.A[i][1] == 0 else 0) + (B2 if self.A[i][0] == 1 else 0) + (B2 if self.A[i][D-1] == 1 else 0)
if now + bonus > mxcnt:
mxcnt = now + bonus
best_pos = (i, 0, i, D-1)
for j in range(self.N - D):
now += self.A[i][j+D] - self.A[i][j]
bonus = (B1 if self.A[i][j] == 0 else 0) + (B1 if (j+D+1 >= self.N or self.A[i][j+D+1] == 0) else 0)
bonus += (B2 if self.A[i][j+1] == 1 else 0) + (B2 if self.A[i][j+D] == 1 else 0)
if now + bonus > mxcnt:
mxcnt = now + bonus
best_pos = (i, j+1, i, j+D)
# 縦向きスキャン
for j in range(self.N):
now = sum(self.A[i][j] for i in range(D))
bonus = B1 + (B1 if self.A[1][j] == 0 else 0) + (B2 if self.A[0][j] == 1 else 0) + (B2 if self.A[D-1][j] == 1 else 0)
if now + bonus > mxcnt:
mxcnt = now + bonus
best_pos = (0, j, D-1, j)
for i in range(self.N - D):
now += self.A[i+D][j] - self.A[i][j]
bonus = (B1 if self.A[i][j] == 0 else 0) + (B1 if (i+D+1 >= self.N or self.A[i+D+1][j] == 0) else 0)
bonus += (B2 if self.A[i+1][j] == 1 else 0) + (B2 if self.A[i+D][j] == 1 else 0)
if now + bonus > mxcnt:
mxcnt = now + bonus
best_pos = (i+1, j, i+D, j)
# 選んだbest_posを配置
self.place(best_pos)
ans[idx] = best_pos
return ans
def solve(self, tk, LIMIT):
# 初期解を複数パターンで生成
patterns = []
# サイズ大きい順
patterns.append(sorted(range(self.K), key=lambda k: self.L[k], reverse=True))
# ランダム順 (異なるシードで)
for seed in range(2):
rnd = random.Random(seed)
order = list(range(self.K))
rnd.shuffle(order)
patterns.append(order)
best_ans = None
best_sc = -float('inf')
# 各パターンでグリーディ生成
for order in patterns:
ans0 = self._greedy_initial(order)
sc0 = self.calscore(ans0)
if sc0 > best_sc:
best_sc = sc0
best_ans = ans0
# best_ans を現在の解としてセット
ans = best_ans[:]
curr_sc = best_sc
best_overall = ans[:]
best_overall_sc = best_sc
# self.A を best_ans 適用後の状態にリセット
self.initialize()
for pos in ans:
self.place(pos)
# 焼きなまし法パラメータ
T0, T1 = 0.5, 0.01
loop = 0
# 焼きなまし繰り返し
# 長方形の位置をずらす
loop = 0
while True:
if tk.is_time_over(LIMIT):
break
loop += 1
# 温度
t = tk.time_now()
progress = t / LIMIT
temp = T0 + (T1 - T0) * progress
# Aの値を減らしていく
rnd = random.randrange(100)
if rnd < 99:
n = random.randrange(self.K)
a0, b0, c0, d0 = ans[n]
kouho = []
if a0 == c0: # 横長
if d0 != self.N-1 and random.randrange(2) == 0: # 右にずらす
dsc = (self.A[a0][b0] + self.A[c0][d0+1] - 1) * 2
kouho.append((dsc, "R"))
elif b0 != 0 and random.randrange(2) == 1: # 左にずらす
dsc = (self.A[a0][b0-1] + self.A[c0][d0] - 1) * 2
kouho.append((dsc, "L"))
elif b0 == d0: # 縦長
if c0 != self.N-1 and random.randrange(2) == 0: # 下にずらす
dsc = (self.A[a0][b0] + self.A[c0+1][d0] - 1) * 2
kouho.append((dsc, "D"))
elif a0 != 0 and random.randrange(2) == 1: # 上にずらす
dsc = (self.A[a0-1][b0] + self.A[c0][d0] - 1) * 2
kouho.append((dsc, "U"))
if len(kouho) == 0:
continue
dsc, direction = kouho[0]
if dsc >= 0:
# if dsc >= 0 or random.random() < math.exp(dsc / temp): # 採用
curr_sc += dsc
if direction == "R":
self.place((a0, b0, c0, d0))
self.place((a0, b0+1, c0, d0+1))
ans[n] = (a0, b0+1, c0, d0+1)
elif direction == "L":
self.place((a0, b0, c0, d0))
self.place((a0, b0-1, c0, d0-1))
ans[n] = (a0, b0-1, c0, d0-1)
elif direction == "D":
self.place((a0, b0, c0, d0))
self.place((a0+1, b0, c0+1, d0))
ans[n] = (a0+1, b0, c0+1, d0)
elif direction == "U":
self.place((a0, b0, c0, d0))
self.place((a0-1, b0, c0-1, d0))
ans[n] = (a0-1, b0, c0-1, d0)
if curr_sc > best_sc:
print(f"best {loop=}", file=sys.stderr)
best_sc = curr_sc
best_ans = ans[:]
else:
n = random.randrange(self.K)
a0, b0, c0, d0 = ans[n]
D = max(abs(a0 - c0), abs(b0 - d0))+1
ones0 = sum(self.A[i][j] for i in range(a0,c0+1) for j in range(b0,d0+1))
zeros0 = D - ones0
dsc0 = ones0 - zeros0
# 一旦消去
self.place((a0, b0, c0, d0))
mxcnt = -1
best_pos = (0, 0, 0, D-1)
B1 = 0
B2 = 0
# 横向きスキャン
for i in range(self.N):
now = sum(self.A[i][j] for j in range(D))
bonus = B1 + (B1 if self.A[i][1] == 0 else 0) + (B2 if self.A[i][0] == 1 else 0) + (B2 if self.A[i][D-1] == 1 else 0)
if now + bonus > mxcnt:
mxcnt = now + bonus
best_pos = (i, 0, i, D-1)
for j in range(self.N - D):
now += self.A[i][j+D] - self.A[i][j]
bonus = (B1 if self.A[i][j] == 0 else 0) + (B1 if (j+D+1 >= self.N or self.A[i][j+D+1] == 0) else 0)
bonus += (B2 if self.A[i][j+1] == 1 else 0) + (B2 if self.A[i][j+D] == 1 else 0)
if now + bonus > mxcnt:
mxcnt = now + bonus
best_pos = (i, j+1, i, j+D)
# 縦向きスキャン
for j in range(self.N):
now = sum(self.A[i][j] for i in range(D))
bonus = B1 + (B1 if self.A[1][j] == 0 else 0) + (B2 if self.A[0][j] == 1 else 0) + (B2 if self.A[D-1][j] == 1 else 0)
if now + bonus > mxcnt:
mxcnt = now + bonus
best_pos = (0, j, D-1, j)
for i in range(self.N - D):
now += self.A[i+D][j] - self.A[i][j]
bonus = (B1 if self.A[i][j] == 0 else 0) + (B1 if (i+D+1 >= self.N or self.A[i+D+1][j] == 0) else 0)
bonus += (B2 if self.A[i+1][j] == 1 else 0) + (B2 if self.A[i+D][j] == 1 else 0)
if now + bonus > mxcnt:
mxcnt = now + bonus
best_pos = (i+1, j, i+D, j)
# 選んだbest_posを配置
self.place(best_pos)
ans[n] = best_pos
ones1 = sum(self.A[i][j] for i in range(best_pos[0],best_pos[2]+1)
for j in range(best_pos[1],best_pos[3]+1))
zeros1 = D - ones1
dsc1 = ones1 - zeros1
curr_sc += dsc0 - dsc1
if curr_sc > best_sc:
print(f"best2 {loop=}", file=sys.stderr)
best_sc = curr_sc
best_ans = ans[:]
# print(ans, file=sys.stderr)
# sc = self.calscore(ans)
return best_ans, best_sc
###########################################
def main(DEBUG):
tk = TimeKeeper()
LIMIT = 0.8
N, K = map(int, input().split())
L = list(map(int, input().split()))
S = [list(input().rstrip()) for _ in range(N)]
W = 0
A = [[0]*N for _ in range(N)]
for i in range(N):
for j in range(N):
A[i][j] = int(S[i][j])
W += (1 - A[i][j])
# N = 60 グリッドサイズ
# K = 500 操作回数
# 1 <= Li <= 25 長方形サイズ
# W 初期Aの白(0)の総数
solver = Solver(N, K, L, W, A)
ans, sc = solver.solve(tk, LIMIT)
for i in range(K):
ANS = [x+1 for x in ans[i]]
print(*ANS)
print("SC", sc, file=sys.stderr)
return
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)