ABC315Dを解いた【defaultdictの罠】

筆者はレート800前後の茶～緑コーダ

ABC315のD問題を解いていく

実装コード

行or列ごとにクッキーが何種類あるか管理して除去できる行or列を探索する

• 添字を数値に変換するのサボってdefaultdictで管理したらTLE出ました
• 除去の処理もijの組み合わせをproductとかまとめてるけど普通に2重for文2回の方が速かったっていう

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

def main():
    H, W = rLI()
    a = ord("a")
    grid = [[ord(c) - ord("a") for c in rS()] for _ in range(H)]
    
    rn = H
    sr = set(range(H))
    cn = W
    sc = set(range(W))
    
    cr = [[0]*30 for _ in range(H)]
    cc = [[0]*30 for _ in range(W)]
    dr = [0] * H
    dc = [0] * W
    
    for i in range(H):
        for j in range(W):
            c = grid[i][j]
            if cr[i][c] == 0:
                dr[i] += 1
            cr[i][c] += 1
            if cc[j][c] == 0:
                dc[j] += 1
            cc[j][c] += 1

    while True:
        
        mr = [i for i in sr if dr[i] == 1 and cn >= 2]
        mc = [j for j in sc if dc[j] == 1 and rn >= 2]
        er = len(mr)
        ec = len(mc)
        
        for i in mr:
            sr.remove(i)
        for j in mc:
            sc.remove(j)
        
        # err(rn,mr)
        # err(cn,mc)
        if er + ec == 0:
            break
        
        ijs = [product(mr,range(W)),product(range(H),mc)]
        
        for ij in ijs:
            for i, j in ij:
                if (c := grid[i][j]) == ".": continue
                # err(i,j,c)
                cr[i][c] -= 1
                if cr[i][c] == 0:
                    dr[i] -= 1
                cc[j][c] -= 1            
                if cc[j][c] == 0:
                    dc[j] -= 1
                grid[i][j] = "."
        rn -= er
        cn -= ec
    ans = rn*cn
    print(ans)
    
if __name__ == '__main__':
    main()

感想

最大個数が限定される配列はリストで管理したほうがいいってわかった。