結果

問題 No.5025 Forest Fire
コンテスト
ユーザー Koi
提出日時 2026-10-24 16:23:03
言語 PyPy3
(8.0.0 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,950 ms / 2,000 ms
+ 335µs
コード長 2,566 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 80 ms
コンパイル使用メモリ 64,664 KB
実行使用メモリ 95,276 KB
スコア 159,974,291
最終ジャッジ日時 2026-10-24 16:26:38
合計ジャッジ時間 155,345 ms
ジャッジサーバーID
（参考情報） 		judge6_0 / <nil>
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from atcoder import dsu
N, K = map(int, input().split())
D = []
for i in range(N):
    S = input()
    L = []
    for j in range(N):
        L.append(int(S[j]))
    D.append(L)
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def merge(i, j):
    return i * N + j
def sep(ij):
    return ij //N, ij % N
def calc_score(L):
    S = set(L)
    DS = dsu.DSU(N * N)
    for i in range(N):
        for j in range(N):
            if((i, j) in S or D[i][j] < 5):
                continue
            ij = merge(i, j)
            for k in range(4):
                x2 = i + dx[k]
                y2 = j + dy[k]
                if(0 <= x2 < N and 0 <= y2 < N):
                    if((x2, y2) not in S and D[x2][y2] >= 5):
                        xy2 = merge(x2, y2)
                        DS.merge(ij, xy2)
    s = 0
    # print(DS.groups())
    for l in DS.groups():
        s += len(l) ** 2
    return s
                    
                

Subs = []
for i in range(1, N - 1):
    L = set()
    for x in range(N):
        if(D[x][i + x % 2] >= 5):
            L.add((x, i + x % 2))
        else:
            if(len(L) > 5):
                Subs.append(L)
            L = set()
    if(len(L) != 0):
        if(len(L) > 5):
            Subs.append(L)
for i in range(1, N - 1):
    L = set()
    for x in range(N):
        if(D[i + x % 2][x] >= 5):
            L.add((i + x % 2, x))
        else:
            if(len(L) > 5):
                Subs.append(L)
            # Subs.append(L)
            L = set()
    if(len(L) != 0):
        if(len(L) > 5):
            Subs.append(L)
Chooses = []
total_n = 0

import time
t0 = time.time()
import random,sys
random.seed(51)
best_ans = []
best_score = calc_score([])
current_score = best_score
P = list(range(len(Subs)))
while time.time() - t0 < 1.9:
    old_chooses = Chooses[:]
    while total_n > 70:
        ind = random.randint(0, len(Chooses) - 1)
        total_n -= len(Subs[Chooses[ind]])
        Chooses.remove(Chooses[ind])
    random.shuffle(P)
    for i in P:
        if(total_n + len(Subs[i]) < K):
            Chooses.append(i)
            total_n += len(Subs[i])
    L = []
    for i in Chooses:
        for x, y in Subs[i]:
            L.append((x, y))
    new_score = calc_score(L)
    if(new_score < best_score):
        best_score = new_score
        best_ans = L
    
        
# print(len(Subs))
# for l in Subs:
#     print()
#     print(len(l))
#     for (x, y) in l:
#         print(x, y)
final_ans = set()
for (i, j) in best_ans:
    final_ans.add((i, j))
print(len(final_ans))
for x, y in final_ans:
    print(x, y)
0