結果

問題 No.5002 stick xor
ユーザー ra5anchor
提出日時 2025-04-26 09:22:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 925 ms / 1,000 ms
コード長 5,565 bytes
コンパイル時間 504 ms
コンパイル使用メモリ 82,580 KB
実行使用メモリ 87,532 KB
スコア 30,007
最終ジャッジ日時 2025-04-26 09:23:18
合計ジャッジ時間 32,855 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

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.A = A
        self.A0 = [[0]*N for _ in range(N)]
        for i in range(N):
            self.A0[i] = A[i][:]


    def initialize(self):
        self.A = [[0]*self.N for _ in range(self.N)]
        for i in range(self.N):
            self.A[i] = self.A0[i][:]


    def update(self, a, b, c, d):
        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):
        A_ = [[0]*self.N for _ in range(self.N)]
        for i in range(self.N):
            A_[i] = self.A0[i][:]
        for k in range(self.K):
            a, b, c, d = ans[k]
            for i in range(a, c+1):
                for j in range(b, d+1):
                    A_[i][j] = 1 - A_[i][j]
        ansW = 0
        for i in range(self.N):
            for j in range(self.N):
                ansW += (1 - A_[i][j])
        return ansW - self.W

    def solve(self, tk):

        # 初期解（ランダム配置）
        self.initialize()
        ans = []
        for k in range(self.K):
            Lk = self.L[k]
            if k%2 == 0:
                a = random.randint(0, self.N-1)
                b = random.randint(0, self.N-Lk)
                c = a
                d = b + Lk - 1
            else:
                a = random.randint(0, self.N-Lk)
                b = random.randint(0, self.N-1)
                c = a + Lk - 1
                d = b
            self.update(a, b, c, d)
            ans.append((a, b, c, d))

        sc = self.calscore(ans)

        best_sc = sc

        # 山登り
        # 長方形の位置をずらす
        while True:
            if tk.is_time_over(0.8):
                break

            # Aの値を減らしていく
            n = random.randrange(self.K)
            a0, b0, c0, d0 = ans[n]
            if a0 == c0: # 横長
                if d0 != self.N-1 and random.randrange(2) == 0: # 右にずらす
                    if self.A[a0][b0] + self.A[c0][d0+1] >= 1:
                        # print("bef", self.A[a0][b0] + self.A[c0][d0+1], file=sys.stderr)
                        self.A[a0][b0] = 1 - self.A[a0][b0]
                        self.A[c0][d0+1] = 1 - self.A[c0][d0+1]
                        ans[n] = (a0, b0+1, c0, d0+1)
                        # print("after", self.A[a0][b0] + self.A[c0][d0+1], file=sys.stderr)
                elif b0 != 0 and random.randrange(2) == 1: # 左にずらす
                    if self.A[a0][b0-1] + self.A[c0][d0] >= 1:
                        # print("bef", self.A[a0][b0-1] + self.A[c0][d0], file=sys.stderr)
                        self.A[a0][b0-1] = 1 - self.A[a0][b0-1]
                        self.A[c0][d0] = 1 - self.A[c0][d0]
                        ans[n] = (a0, b0-1, c0, d0-1)
                        # print("after", self.A[a0][b0-1] + self.A[c0][d0], file=sys.stderr)
            elif b0 == d0: # 縦長
                if c0 != self.N-1 and random.randrange(2) == 0: # 下にずらす
                    if self.A[a0][b0] + self.A[c0+1][d0] >= 1:
                        # print("bef", self.A[a0][b0] + self.A[c0+1][d0], file=sys.stderr)
                        self.A[a0][b0] = 1 - self.A[a0][b0]
                        self.A[c0+1][d0] = 1 - self.A[c0+1][d0]
                        ans[n] = (a0+1, b0, c0+1, d0)
                        # print("after", self.A[a0][b0] + self.A[c0+1][d0], file=sys.stderr)
                elif a0 != 0 and random.randrange(2) == 1: # 上にずらす
                    if self.A[a0-1][b0] + self.A[c0][d0] >= 1:
                        # print("bef", self.A[a0-1][b0] + self.A[c0][d0], file=sys.stderr)
                        self.A[a0-1][b0] = 1 - self.A[a0-1][b0]
                        self.A[c0][d0] = 1 - self.A[c0][d0]
                        ans[n] = (a0-1, b0, c0-1, d0)
                        # print("after", self.A[a0-1][b0] + self.A[c0][d0], file=sys.stderr)
                
        # print(ans, file=sys.stderr)
        sc = self.calscore(ans)
        return ans, 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)

    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)
0