提出 #27453026

---

ソースコード 拡げる

import sys,random,bisect
from collections import deque,defaultdict
from heapq import heapify,heappop,heappush
from itertools import cycle, permutations
from math import log,gcd

input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

H,W = mi()
A = [input() for i in range(H)]

dp_c = [[[k-1 for k in range(W)] for j in range(H)] for i in range(H)]
dp_r = [[[i-1 for i in range(H)] for l in range(W)] for k in range(W)]



"""
init
"""
for i in range(H):
    ok = [A[i][j] for j in range(W)]
    for k in range(W)[::-1]:
        if k!=W-1 and ok[k]==ok[k+1]:
            dp_c[i][i][k] = dp_c[i][i][k+1]
        else:
            dp_c[i][i][k] = k
    for j in range(i+1,H):
        for k in range(W):
            if ok[k]!=A[j][k]:
                ok[k] = ""
        for k in range(W)[::-1]:
            if ok[k]:
                if k!=W-1 and ok[k]==ok[k+1]:
                    dp_c[i][j][k] = dp_c[i][j][k+1]
                else:
                    dp_c[i][j][k] = k

for k in range(W):
    ok = [A[i][k] for i in range(H)]
    for i in range(H)[::-1]:
        if i!=H-1 and ok[i]==ok[i+1]:
            dp_r[k][k][i] = dp_r[k][k][i+1]
        else:
            dp_r[k][k][i] = i
    for l in range(k+1,W):
        for i in range(H):
            if ok[i]!=A[i][l]:
                ok[i] = ""
        for i in range(H)[::-1]:
            if ok[i]:
                if i!=H-1 and ok[i]==ok[i+1]:
                    dp_r[k][l][i] = dp_r[k][l][i+1]
                else:
                    dp_r[k][l][i] = i

"""
update
"""

for ans in range(17):
    if dp_c[0][H-1][0]==W-1:
        exit(print(ans))
    
    """
    dp_c:たての切断の分を更新
    dp_r:よこの切断の分を更新
    どちらもダブリングの要領で
    """

    for i in range(H):
        for j in range(i,H):
            tmp = dp_c[i][j]
            for k in range(W):
                next_c = tmp[k] + 1
                if next_c < W:
                    tmp[k] = tmp[next_c]
    
    for k in range(W):
        for l in range(k,W):
            tmp = dp_r[k][l]
            for i in range(H):
                next_r = tmp[i] + 1
                if next_r < H:
                    tmp[i] = tmp[next_r]
    
    """
    dp_c:よこの切断の分を更新
    l <= dp_c[i][j][k] iff j <= dp_r[k][l][i]
    jについて単調性があるのでjごとに尺取り
    """

    for i in range(H):
        for k in range(W):
            l = k-1
            for j in range(i,H)[::-1]:
                while l!=W-1 and j <= dp_r[k][l+1][i]:
                    l += 1
                if l > dp_c[i][j][k]:
                    dp_c[i][j][k] = l
    
    """
    dp_r:たての切断の分を更新
    j <= dp_r[k][l][i] iff l <= dp_c[i][j][k]
    lについて単調線があるのでlについて尺取り
    """

    for k in range(W):
        for i in range(H):
            j = i-1
            for l in range(k,W)[::-1]:
                while j!=H-1 and l <= dp_c[i][j+1][k]:
                    j += 1
                if j > dp_r[k][l][i]:
                    dp_r[k][l][i] = j
    
    #dp_c = n_dp_c
    




            

提出情報

ジャッジ結果