yukicoder long contest 1 stick xor

問題

考察

愚直にやって終わった感じでした。
愚直にやる以外は全然思いつかなかった。

1ターン毎に現在の盤面から最も多く漆黒→純白に反転できる操作を盤面に適用していく。
操作対象となるセル(x,y)のx,yはランダムに決定した。
・xは1～N-L,yはランダム(範囲1~N-L)
・yは1～N-L,xはランダム(範囲1~N-L)
あとは単純に漆黒→純白に反転できる数が最も多い操作を選んで盤面に適用して、次のターンで繰り返し...

ソースコード

最終サブミット
https://yukicoder.me/submissions/260603

# coding: utf-8
import random
from heapq import heappush,heappop

#操作opを盤面gridに適用する
def operation_grid(op, grid):
    rev_grid = grid
    #縦方向の操作
    if op[1] == op[3]:
        length = op[2] - op[0] + 1
        for i in range(length):
            rev_grid[op[0]-1+i][op[1]-1] = (grid[op[0]-1+i][op[1]-1]+1)&1
    #横方向の操作
    if op[0] == op[2]:
        length = op[3] - op[1] + 1
        for i in range(length):
            rev_grid[op[0]-1][op[1]-1+i] = (grid[op[0]-1][op[1]-1+i]+1)&1
    return rev_grid
#(x,y)=(base_x,base_y)
#(x,y)のセルから横方向に幅length高さ1の範囲の漆黒のセル数をカウント
def count_black_horizon(grid, base_x, base_y, length):
    return grid[base_y][base_x:base_x + length].count(1)
#(x,y)=(base_x,base_y)
#(x,y)のセルから縦方向に幅1高さlengthの範囲の漆黒のセル数をカウント
def count_black_vertical(grid, base_x, base_y, length):
    return [grid[i][base_x] for i in range(base_y,base_y + length)].count(1)

N,K = map(int,input().split())
L = list(map(int,input().split()))
A = [list(map(int,list(input()))) for i in range(N)]

#出力する操作
operation = []
#適当な値
P = 3
for k in range(K):
    #(-漆黒から純白への反転数, [出力する操作])
    hq = []
    #N-L[k]=盤面からはみ出ない最上、最左
    for x in range(N-L[k]):
        for i in range(P):
            #yはランダム値(0~N-L[k])
            y = random.randint(0, N-L[k])

            #(x,y)のセルから漆黒から純白に反転する数を求める
            horizon_cnt = count_black_horizon(A, x, y, L[k])
            vertical_cnt = count_black_vertical(A, x, y, L[k])
            if horizon_cnt < vertical_cnt:
                heappush(hq, (-vertical_cnt, [y+1, x+1, y+L[k], x+1]))
            else:
                heappush(hq, (-horizon_cnt, [y+1, x+1, y+1, x+L[k]]))
    for y in range(N-L[k]):
        for i in range(P):
            #xはランダム値(0~N-L[k])
            x = random.randint(0, N-L[k])

            #(x,y)のセルから漆黒から純白に反転する数を求める
            horizon_cnt = count_black_horizon(A, x, y, L[k])
            vertical_cnt = count_black_vertical(A, x, y, L[k])
            if horizon_cnt < vertical_cnt:
                heappush(hq, (-vertical_cnt, [y+1, x+1, y+L[k], x+1]))
            else:
                heappush(hq, (-horizon_cnt, [y+1, x+1, y+1, x+L[k]]))
    #漆黒から純白へ最も多く反転できる操作を取り出す
    cnt, op = heappop(hq)
    #操作を盤面に適用
    A = operation_grid(op, A)
    operation.append(op)

print('\n'.join([' '.join(list(map(str,op))) for op in operation]))