Problem:


Score : 800 points

Problem Statement

Mr. Takahashi has in his room an art object with H rows and W columns, made up of H \times W blocks.
Each block has a color represented by a lowercase English letter (a-z).
The color of the block at the i-th row and j-th column is c_{i,j}.  

Mr. Takahashi would like to dismantle the object, finding it a bit kitschy for his tastes.
The dismantling is processed by repeating the following operation:  

Choose one of the W columns and push down that column one row.
The block at the bottom of that column disappears.

Each time the operation is performed, a cost is incurred.
Since blocks of the same color have a property to draw each other together, the cost of the operation is the number of the pairs of blocks (p, q) such that:

The block p is in the selected column.

The two blocks p and q are horizontally adjacent (before pushing down the column).

The two blocks p and q have the same color.

Mr. Takahashi dismantles the object by repeating the operation H \times W times to get rid of all the blocks.
Compute the minimum total cost to dismantle the object.

Constraints

1 ≤ H ≤ 300

2 ≤ W ≤ 300

All characters c_{i,j} are lowercase English letters (a-z).

Partial Score

In test cases worth 300 points, W = 3.

Input

The input is given from Standard Input in the following format:

H W
c_{1,1}c_{1,2}..c_{1,W}
c_{2,1}c_{2,2}..c_{2,W}
:
c_{H,1}c_{H,2}..c_{H,W}

Output

Print the minimum total cost to dismantle the object.

Sample Input 1

2 3
rrr
brg

Sample Output 1

2

For example, the total cost of 2 can be achieved by performing the operation as follows and this is the minimum value.

Sample Input 2

6 3
xya
xya
ayz
ayz
xaz
xaz

Sample Output 2

0

The total cost of 0 can be achieved by first pushing down all blocks of the middle column, then all of the left column, and all of the right column.

Sample Input 3

4 2
ay
xa
xy
ay

Sample Output 3

0

The total cost of 0 can be achieved by the following operations:

pushing down the right column one row;

pushing down the left column one row;

pushing down all of the right column;

and pushing down all of the left column.

Sample Input 4

5 5
aaaaa
abbba
ababa
abbba
aaaaa

Sample Output 4

24

Sample Input 5

7 10
xxxxxxxxxx
ccccxxffff
cxxcxxfxxx
cxxxxxffff
cxxcxxfxxx
ccccxxfxxx
xxxxxxxxxx

Sample Output 5

130



Sample input:
2 3
rrr
brg


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
h, w = map(int, input().split())
c = [input() for _ in range(h)]

cost = [[[0 for _ in range(h+1)] for _ in range(h+1)] for _ in range(w-1)]
for i in range(w-1):
	for d in range(-h, h+1):
		if d < 0:
			d = -d
			cost[i][h-d][h] = 0
			for j in range(h-d-1, -1, -1):
				cost[i][j][j+d] = cost[i][j+1][j+d+1] + (c[h-j-1][i] == c[h-j-d-1][i+1])
		else:
			cost[i][h][h-d] = 0
			for j in range(h-d-1, -1, -1):
				cost[i][j+d][j] = cost[i][j+d+1][j+1] + (c[h-j-d-1][i] == c[h-j-1][i+1])

dp = [[[10**6 for _ in range(h+1)] for _ in range(h+1)] for _ in range(w-1)]
for i in range(w-1):
	dp[i][0][0] = 0
	for j in range(h+1):
		for k in range(h+1):
			if j > 0:
				dp[i][j][k] = min(dp[i][j][k], dp[i][j-1][k] + cost[i][j-1][k])
			if k > 0:
				dp[i][j][k] = min(dp[i][j][k], dp[i][j][k-1] + cost[i][j][k-1])

ans = 0
for i in range(w-1):
	ans += dp[i][h][h]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools


h, w = map(int, input().split())
c = [list(map(ord, input())) for i in range(h)]
c = list(itertools.chain.from_iterable(c))
INF = 10 ** 9


ans = 0
dq = [0] * ((h + 1) ** 2)
for wi in range(w - 1):
    for diff in range(h + 1):
        cnt = 0
        for i in range(h - diff):
            cnt += (c[i * w + wi] == c[(i + diff) * w + wi + 1])
        dq[diff * (h + 1)] = cnt
        for i in range(h - diff - 1):
            cnt -= (c[(h - i - 1 - diff) * w + wi] == c[(h - i - 1) * w + wi + 1])
            dq[(i + 1 + diff) * (h + 1) + i + 1] = cnt

        cnt = 0
        for i in range(h - diff):
            cnt += (c[(i + diff) * w + wi] == c[i * w + wi + 1])
        dq[diff] = cnt
        for i in range(h - diff - 1):
            cnt -= (c[(h - i - 1 - diff) * w + wi + 1] == c[(h - i - 1) * w + wi])
            dq[(i + 1) * (h + 1) + i + 1 + diff] = cnt
            
    dp = [INF] * ((h + 1) ** 2)
    dp[0] = 0
    for i in range(h + 1):
        for j in range(h + 1):
            if i + 1 < h + 1:
                dp[(i + 1) * (h + 1) + j] = min(dp[i * (h + 1) + j] + dq[i * (h + 1) + j], dp[(i + 1) *(h + 1) + j])
            if j + 1 < h + 1:
                dp[i * (h + 1) + j + 1] = min(dp[i * (h + 1) + j] + dq[i * (h + 1) + j], dp[i * (h + 1) + j + 1])
    ans += dp[-1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools


h, w = map(int, input().split())
c = [list(map(ord, input())) for i in range(h)]
c = list(itertools.chain.from_iterable(c))
INF = 10 ** 9


ans = 0
dq = [0] * ((h + 1) ** 2)
for wi in range(w - 1):
    for diff in range(h + 1):
        cnt = 0
        for i in range(h):
            if i + diff >= h:
                break
            cnt += (c[i * w + wi] == c[(i + diff) * w + wi + 1])
        dq[(0 + diff) * (h + 1) + 0] = cnt
        for i in range(h):
            if i + 1 + diff >= h:
                break
            cnt -= (c[(h - i - 1 - diff) * w + wi] == c[(h - i - 1) * w + wi + 1])
            dq[(i + 1 + diff) * (h + 1) + i + 1] = cnt

        cnt = 0
        for i in range(h):
            if i + diff >= h:
                break
            cnt += (c[(i + diff) * w + wi] == c[i * w + wi + 1])
        dq[0 + diff] = cnt
        for i in range(h):
            if i + 1 + diff >= h:
                break
            cnt -= (c[(h - i - 1 - diff) * w + wi + 1] == c[(h - i - 1) * w + wi])
            dq[(i + 1) * (h + 1) + i + 1 + diff] = cnt
            
    dp = [INF] * ((h + 1) ** 2)
    dp[0] = 0
    for i in range(h + 1):
        for j in range(h + 1):
            if i + 1 < h + 1:
                dp[(i + 1) *(h + 1) + j] = min(dp[i * (h + 1) + j] + dq[i * (h + 1) + j], dp[(i + 1) *(h + 1) + j])
            if j + 1 < h + 1:
                dp[i * (h + 1) + j + 1] = min(dp[i * (h + 1) + j] + dq[i * (h + 1) + j], dp[i * (h + 1) + j + 1])
    ans += dp[-1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


h, w = map(int, input().split())
c = [list(map(ord, input())) for i in range(h)]
INF = 10 ** 9


ans = 0
dq = [0] * ((h + 1) ** 2)
for wi in range(w - 1):
    for diff in range(h + 1):
        cnt = 0
        for i in range(h):
            if i + diff >= h:
                break
            cnt += (c[i][wi] == c[i + diff][wi + 1])
        dq[(0 + diff) * (h + 1) + 0] = cnt
        for i in range(h):
            if i + 1 + diff >= h:
                break
            cnt -= (c[h - i - 1 - diff][wi] == c[h - i - 1][wi + 1])
            dq[(i + 1 + diff) * (h + 1) + i + 1] = cnt

        cnt = 0
        for i in range(h):
            if i + diff >= h:
                break
            cnt += (c[i + diff][wi] == c[i][wi + 1])
        dq[0 + diff] = cnt
        for i in range(h):
            if i + 1 + diff >= h:
                break
            cnt -= (c[h - i - 1 - diff][wi + 1] == c[h - i - 1][wi])
            dq[(i + 1) * (h + 1) + i + 1 + diff] = cnt
            
    dp = [INF] * ((h + 1) ** 2)
    dp[0] = 0
    for i in range(h + 1):
        for j in range(h + 1):
            if i + 1 < h + 1:
                dp[(i + 1) *(h + 1) + j] = min(dp[i * (h + 1) + j] + dq[i * (h + 1) + j], dp[(i + 1) *(h + 1) + j])
            if j + 1 < h + 1:
                dp[i * (h + 1) + j + 1] = min(dp[i * (h + 1) + j] + dq[i * (h + 1) + j], dp[i * (h + 1) + j + 1])
    ans += dp[-1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
c = [list(map(ord, input())) for i in range(h)]
INF = 10 ** 9


ans = 0
dq = [[0] * (h + 1) for i in range(h + 1)]
dp = [[INF] * (h + 1) for i in range(h + 1)]
for wi in range(w - 1):
    for diff in range(h + 1):
        cnt = 0
        for i in range(h):
            if i + diff >= h:
                break
            cnt += (c[i][wi] == c[i + diff][wi + 1])
        dq[0 + diff][0] = cnt
        for i in range(h):
            if i + 1 + diff >= h:
                break
            cnt -= (c[h - i - 1 - diff][wi] == c[h - i - 1][wi + 1])
            dq[i + 1 + diff][i + 1] = cnt

        cnt = 0
        for i in range(h):
            if i + diff >= h:
                break
            cnt += (c[i + diff][wi] == c[i][wi + 1])
        dq[0][0 + diff] = cnt
        for i in range(h):
            if i + 1 + diff >= h:
                break
            cnt -= (c[h - i - 1 - diff][wi + 1] == c[h - i - 1][wi])
            dq[i + 1][i + 1 + diff] = cnt
            
    for i in range(h + 1):
        for j in range(h + 1):
            dp[i][j] = INF
    dp[0][0] = 0
    for i in range(h + 1):
        for j in range(h + 1):
            if i + 1 < h + 1:
                dp[i + 1][j] = min(dp[i][j] + dq[i][j], dp[i + 1][j])
            if j + 1 < h + 1:
                dp[i][j + 1] = min(dp[i][j] + dq[i][j], dp[i][j + 1])
    ans += dp[-1][-1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
c = [input() for i in range(h)]
INF = 10 ** 9


ans = 0
dq = [[0] * (h + 1) for i in range(h + 1)]
dp = [[INF] * (h + 1) for i in range(h + 1)]
for wi in range(w - 1):
    for diff in range(h + 1):
        cnt = 0
        for i in range(h):
            if i + diff >= h:
                break
            cnt += (c[i][wi] == c[i + diff][wi + 1])
        dq[0 + diff][0] = cnt
        for i in range(h):
            if i + 1 + diff >= h:
                break
            dq[i + 1 + diff][i + 1] = dq[i + diff][i] - (c[h - i - 1 - diff][wi] == c[h - i - 1][wi + 1])
            
        cnt = 0
        for i in range(h):
            if i + diff >= h:
                break
            cnt += (c[i + diff][wi] == c[i][wi + 1])
        dq[0][0 + diff] = cnt
        for i in range(h):
            if i + 1 + diff >= h:
                break
            dq[i + 1][i + 1 + diff] = dq[i][i + diff] - (c[h - i - 1 - diff][wi + 1] == c[h - i - 1][wi])  
    for i in range(h + 1):
        for j in range(h + 1):
            dp[i][j] = INF
    dp[0][0] = 0
    for i in range(h + 1):
        for j in range(h + 1):
            if i + 1 < h + 1:
                dp[i + 1][j] = min(dp[i][j] + dq[i][j], dp[i + 1][j])
            if j + 1 < h + 1:
                dp[i][j + 1] = min(dp[i][j] + dq[i][j], dp[i][j + 1])
    ans += dp[-1][-1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
c = [input() for i in range(h)]
INF = 10 ** 9


ans = 0
for wi in range(w - 1):
    dq = [[0] * (h + 1) for i in range(h + 1)]
    for diff in range(h + 1):
        cnt = 0
        for i in range(h):
            if i + diff >= h:
                break
            if c[i][wi] == c[i + diff][wi + 1]:
                cnt += 1
        dq[0 + diff][0] = cnt
        for i in range(h):
            if i + 1 + diff >= h:
                break
            dq[i + 1 + diff][i + 1] = dq[i + diff][i] - (c[h - i - 1 - diff][wi] == c[h - i - 1][wi + 1])
            
        cnt = 0
        for i in range(h):
            if i + diff >= h:
                break
            if c[i + diff][wi] == c[i][wi + 1]:
                cnt += 1
        dq[0][0 + diff] = cnt
        for i in range(h):
            if i + 1 + diff >= h:
                break
            dq[i + 1][i + 1 + diff] = dq[i][i + diff] - (c[h - i - 1 - diff][wi + 1] == c[h - i - 1][wi])  
    
    dp = [[INF] * (h + 1) for i in range(h + 1)]
    dp[0][0] = 0
    for i in range(h + 1):
        for j in range(h + 1):
            if i + 1 < h + 1:
                dp[i + 1][j] = min(dp[i][j] + dq[i][j], dp[i + 1][j])
            if j + 1 < h + 1:
                dp[i][j + 1] = min(dp[i][j] + dq[i][j], dp[i][j + 1])
    ans += dp[-1][-1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(k):
    dp = [[0] * (h + 1) for i in range(h + 1)]
    for i in range(h):
        for diff in range(h - i):
            dp[i + 1][i + 1 + diff] = dp[i][i + diff] + (s[i + diff][k] == s[i][k + 1])
            dp[i + 1 + diff][i + 1] = dp[i + diff][i] + (s[i][k] == s[i + diff][k + 1])
    
    min_cost = {}
    def solve_cost(i, j):
        if i * offset + j in min_cost:
            return min_cost[i * offset + j]
        if i == 0 or j == 0:
            return 0
        min_cost[i * offset + j] = min(solve_cost(i, j - 1), solve_cost(i - 1, j)) + dp[i][j]
        return min_cost[i * offset + j]
    
    return solve_cost(h, h)


h, w = map(int, input().split())
s = [input() for i in range(h)]
offset = 500

ans = 0
for i in range(w - 1):
    ans += solve(i)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(k):
    dp = [[0] * (h + 1) for i in range(h + 1)]
    for i in range(h):
        for diff in range(h - i):
            dp[i + 1][i + 1 + diff] = dp[i][i + diff] + (s[i + diff][k] == s[i][k + 1])
            dp[i + 1 + diff][i + 1] = dp[i + diff][i] + (s[i][k] == s[i + diff][k + 1])
    
    min_cost = {}
    def solve_cost(i, j):
        if (i, j) in min_cost:
            return min_cost[i, j]
        if i == 0 or j == 0:
            return 0
        min_cost[i, j] = min(solve_cost(i, j - 1), solve_cost(i - 1, j)) + dp[i][j]
        return min_cost[i, j]
    
    return solve_cost(h, h)
  
h, w = map(int, input().split())
s = [input() for i in range(h)]

ans = 0
for i in range(w - 1):
    ans += solve(i)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, W = list(map(int, sys.stdin.buffer.readline().split()))
C = [list(map(ord, sys.stdin.buffer.readline().decode().rstrip())) for _ in range(H)]
C = np.array(C, dtype='int').T


# @debug
def solve(left_w):
    # 隣り合う2個の最小コストが分かれば、いい感じに沈めていけばそれらの和を全体のコストにできる
    # left_w と left_w + 1 の列の最小コストを求めます
    s1 = C[left_w]
    s2 = C[left_w + 1]

    cum1 = []  # cum1[i]: s1 が i 沈んでる
    cum2 = []  # cum2[i]: s2 が i 沈んでる
    for h in range(H + 1):
        cum = [0]
        s = 0
        for c1, c2 in zip(s1, s2[h:]):
            s += c1 == c2
            cum.append(s)
        cum1.append(cum)
        cum = [0]
        s = 0
        for c1, c2 in zip(s1[h:], s2):
            s += c1 == c2
            cum.append(s)
        cum2.append(cum)

    # cums[i]:  s1 が i 沈んでる
    # cums[-i]: s2 が i 沈んでる
    cums = cum1 + cum2[1:][::-1]

    # costs[i][j]: s1 を i 回、s2 を j 回沈めている状態の次のコスト
    costs = [[0] * (H + 1) for _ in range(H + 1)]
    for i, j in itertools.product(range(H + 1), range(H + 1)):
        cum = cums[i - j]
        costs[i][j] = cum[~min(i, j)]

    # dp[i][j]: s1をi回、s2をj回沈めたときのコストの最小値
    dp = [[INF] * (H + 1) for _ in range(H + 1)]
    dp[0][0] = 0
    for i, j in itertools.product(range(H + 1), range(H + 1)):
        if i + 1 <= H:
            # i を沈める
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + costs[i][j])
        if j + 1 <= H:
            # j を沈める
            dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + costs[i][j])
    return dp[H][H]


# cums[i]:  s1 が i 沈んでる
# cums[-i]: s2 が i 沈んでる
cums = np.zeros((W - 1, H * 2 + 1, H + 1), dtype=int)
cums[:, 0, 1:] = (C[:-1] == C[1:]).cumsum(axis=1)
for h in range(1, H):
    cums[:, h, h + 1:] = (C[:-1, :-h] == C[1:, h:]).cumsum(axis=1)
    cums[:, -h, h + 1:] = (C[:-1, h:] == C[1:, :-h]).cumsum(axis=1)

# costs[i][j]: s1 を i 回、s2 を j 回沈めている状態の次のコスト
hs = np.arange(H + 1, dtype=int)
costs = cums[:, np.subtract.outer(hs, hs), ~np.minimum.outer(hs, hs)]

# dp[i][j]: s1をi回、s2をj回沈めたときのコストの最小値
dp = np.full((H + 2, H + 2, W - 1), IINF, dtype=int)
dp[0, 0] = 0
for i in range(H * 2):
    idx = hs[max(0, i - H):i + 1]
    ridx = idx[::-1]
    dp[idx, ridx] += costs[:, idx, ridx].T
    dp[idx, ridx + 1] = np.minimum(dp[idx, ridx + 1], dp[idx, ridx])
    dp[idx + 1, ridx] = np.minimum(dp[idx + 1, ridx], dp[idx, ridx])

print(dp[H, H].sum())

Submission status: Time Limit Exceeded

Solution code:
import itertools
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, W = list(map(int, sys.stdin.buffer.readline().split()))
C = [list(map(ord, sys.stdin.buffer.readline().decode().rstrip())) for _ in range(H)]
C = np.array(C, dtype='int').T


# @debug
def solve(left_w):
    # 隣り合う2個の最小コストが分かれば、いい感じに沈めていけばそれらの和を全体のコストにできる
    # left_w と left_w + 1 の列の最小コストを求めます
    s1 = C[left_w]
    s2 = C[left_w + 1]

    cum1 = []  # cum1[i]: s1 が i 沈んでる
    cum2 = []  # cum2[i]: s2 が i 沈んでる
    for h in range(H + 1):
        cum = [0]
        s = 0
        for c1, c2 in zip(s1, s2[h:]):
            s += c1 == c2
            cum.append(s)
        cum1.append(cum)
        cum = [0]
        s = 0
        for c1, c2 in zip(s1[h:], s2):
            s += c1 == c2
            cum.append(s)
        cum2.append(cum)

    # cums[i]:  s1 が i 沈んでる
    # cums[-i]: s2 が i 沈んでる
    cums = cum1 + cum2[1:][::-1]

    # costs[i][j]: s1 を i 回、s2 を j 回沈めている状態の次のコスト
    costs = [[0] * (H + 1) for _ in range(H + 1)]
    for i, j in itertools.product(range(H + 1), range(H + 1)):
        cum = cums[i - j]
        costs[i][j] = cum[~min(i, j)]

    # dp[i][j]: s1をi回、s2をj回沈めたときのコストの最小値
    dp = [[INF] * (H + 1) for _ in range(H + 1)]
    dp[0][0] = 0
    for i, j in itertools.product(range(H + 1), range(H + 1)):
        if i + 1 <= H:
            # i を沈める
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + costs[i][j])
        if j + 1 <= H:
            # j を沈める
            dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + costs[i][j])
    return dp[H][H]


# cums[i]:  s1 が i 沈んでる
# cums[-i]: s2 が i 沈んでる
cums = np.zeros((W - 1, H * 2 + 1, H + 1), dtype=int)
cums[:, 0, 1:] = (C[:-1] == C[1:]).cumsum(axis=1)
for h in range(1, H):
    cums[:, h, h + 1:] = (C[:-1, :-h] == C[1:, h:]).cumsum(axis=1)
    cums[:, -h, h + 1:] = (C[:-1, h:] == C[1:, :-h]).cumsum(axis=1)

# costs[i][j]: s1 を i 回、s2 を j 回沈めている状態の次のコスト
hs = np.arange(H + 1, dtype=int)
costs = cums[:, np.subtract.outer(hs, hs), ~np.minimum.outer(hs, hs)]

# dp[i][j]: s1をi回、s2をj回沈めたときのコストの最小値
dp = np.full((W - 1, H + 2, H + 2), IINF, dtype=int)
dp[:, 0, 0] = 0
for i in range(H * 2):
    idx = hs[max(0, i - H):i + 1]
    ridx = idx[::-1]
    dp[:, idx, ridx] += costs[:, idx, ridx]
    dp[:, idx, ridx + 1] = np.minimum(dp[:, idx, ridx + 1], dp[:, idx, ridx])
    dp[:, idx + 1, ridx] = np.minimum(dp[:, idx + 1, ridx], dp[:, idx, ridx])

print(dp[:, H, H].sum())

Submission status: Time Limit Exceeded

Solution code:
import itertools
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, W = list(map(int, sys.stdin.buffer.readline().split()))
C = [list(map(ord, sys.stdin.buffer.readline().decode().rstrip())) for _ in range(H)]
C = np.array(C, dtype='int').T


# @debug
def solve(left_w):
    # 隣り合う2個の最小コストが分かれば、いい感じに沈めていけばそれらの和を全体のコストにできる
    # left_w と left_w + 1 の列の最小コストを求めます
    s1 = C[left_w]
    s2 = C[left_w + 1]

    cum1 = []  # cum1[i]: s1 が i 沈んでる
    cum2 = []  # cum2[i]: s2 が i 沈んでる
    for h in range(H + 1):
        cum = [0]
        s = 0
        for c1, c2 in zip(s1, s2[h:]):
            s += c1 == c2
            cum.append(s)
        cum1.append(cum)
        cum = [0]
        s = 0
        for c1, c2 in zip(s1[h:], s2):
            s += c1 == c2
            cum.append(s)
        cum2.append(cum)

    # cums[i]:  s1 が i 沈んでる
    # cums[-i]: s2 が i 沈んでる
    cums = cum1 + cum2[1:][::-1]

    # costs[i][j]: s1 を i 回、s2 を j 回沈めている状態の次のコスト
    costs = [[0] * (H + 1) for _ in range(H + 1)]
    for i, j in itertools.product(range(H + 1), range(H + 1)):
        cum = cums[i - j]
        costs[i][j] = cum[~min(i, j)]

    # dp[i][j]: s1をi回、s2をj回沈めたときのコストの最小値
    dp = [[INF] * (H + 1) for _ in range(H + 1)]
    dp[0][0] = 0
    for i, j in itertools.product(range(H + 1), range(H + 1)):
        if i + 1 <= H:
            # i を沈める
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + costs[i][j])
        if j + 1 <= H:
            # j を沈める
            dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + costs[i][j])
    return dp[H][H]


# cums[i]:  s1 が i 沈んでる
# cums[-i]: s2 が i 沈んでる
cums = np.zeros((W - 1, H * 2 + 1, H + 1), dtype=int)
cums[:, 0, 1:] = (C[:-1] == C[1:]).cumsum(axis=1)
for h in range(1, H):
    cums[:, h, h + 1:] = (C[:-1, :-h] == C[1:, h:]).cumsum(axis=1)
    cums[:, -h, h + 1:] = (C[:-1, h:] == C[1:, :-h]).cumsum(axis=1)

# costs[i][j]: s1 を i 回、s2 を j 回沈めている状態の次のコスト
hs = np.arange(H + 1, dtype=int)
costs = cums[:, np.subtract.outer(hs, hs), ~np.minimum.outer(hs, hs)]

# dp[i][j]: s1をi回、s2をj回沈めたときのコストの最小値
dp = np.full((W - 1, H + 2, H + 2), IINF, dtype=int)
dp[:, 0, 0] = 0
for i in range(H * 2):
    idx = hs[max(0, i - H):i + 1]
    dp[:, idx, idx[::-1] + 1] = np.minimum(
        dp[:, idx, idx[::-1] + 1],
        dp[:, idx, idx[::-1]] + costs[:, idx, idx[::-1]]
    )
    dp[:, idx + 1, idx[::-1]] = np.minimum(
        dp[:, idx + 1, idx[::-1]],
        dp[:, idx, idx[::-1]] + costs[:, idx, idx[::-1]]
    )

print(dp[:, H, H].sum())

Submission status: Time Limit Exceeded

Solution code:
import itertools
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, W = list(map(int, sys.stdin.buffer.readline().split()))
C = [list(map(ord, sys.stdin.buffer.readline().decode().rstrip())) for _ in range(H)]
C = np.array(C, dtype='int').T


# @debug
def solve(left_w):
    # 隣り合う2個の最小コストが分かれば、いい感じに沈めていけばそれらの和を全体のコストにできる
    # left_w と left_w + 1 の列の最小コストを求めます
    s1 = C[left_w]
    s2 = C[left_w + 1]

    cum1 = []  # cum1[i]: s1 が i 沈んでる
    cum2 = []  # cum2[i]: s2 が i 沈んでる
    for h in range(H + 1):
        cum = [0]
        s = 0
        for c1, c2 in zip(s1, s2[h:]):
            s += c1 == c2
            cum.append(s)
        cum1.append(cum)
        cum = [0]
        s = 0
        for c1, c2 in zip(s1[h:], s2):
            s += c1 == c2
            cum.append(s)
        cum2.append(cum)

    # cums[i]:  s1 が i 沈んでる
    # cums[-i]: s2 が i 沈んでる
    cums = cum1 + cum2[1:][::-1]

    # costs[i][j]: s1 を i 回、s2 を j 回沈めている状態の次のコスト
    costs = [[0] * (H + 1) for _ in range(H + 1)]
    for i, j in itertools.product(range(H + 1), range(H + 1)):
        cum = cums[i - j]
        costs[i][j] = cum[~min(i, j)]

    # dp[i][j]: s1をi回、s2をj回沈めたときのコストの最小値
    dp = [[INF] * (H + 1) for _ in range(H + 1)]
    dp[0][0] = 0
    for i, j in itertools.product(range(H + 1), range(H + 1)):
        if i + 1 <= H:
            # i を沈める
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + costs[i][j])
        if j + 1 <= H:
            # j を沈める
            dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + costs[i][j])
    return dp[H][H]


# cums[i]:  s1 が i 沈んでる
# cums[-i]: s2 が i 沈んでる
cums = np.zeros((W - 1, H * 2 + 1, H + 1), dtype=int)
cums[:, 0, 1:] = (C[:-1] == C[1:]).cumsum(axis=1)
for h in range(1, H):
    cums[:, h, h + 1:] = (C[:-1, :-h] == C[1:, h:]).cumsum(axis=1)
    cums[:, -h, h + 1:] = (C[:-1, h:] == C[1:, :-h]).cumsum(axis=1)

# costs[i][j]: s1 を i 回、s2 を j 回沈めている状態の次のコスト
hs = np.arange(H + 1, dtype=int)
costs = cums[:, np.subtract.outer(hs, hs), ~np.minimum.outer(hs, hs)]

# dp[i][j]: s1をi回、s2をj回沈めたときのコストの最小値
dp = np.full((W - 1, H + 1, H + 1), IINF, dtype=int)
dp[:, 0, 0] = 0
for i, j in itertools.product(range(H + 1), range(H + 1)):
    if i + 1 <= H:
        # i を沈める
        dp[:, i + 1, j] = np.minimum(dp[:, i + 1, j], dp[:, i, j] + costs[:, i, j])
    if j + 1 <= H:
        # j を沈める
        dp[:, i, j + 1] = np.minimum(dp[:, i, j + 1], dp[:, i, j] + costs[:, i, j])

print(dp[:, H, H].sum())

Submission status: Time Limit Exceeded

Solution code:
import itertools
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, W = list(map(int, sys.stdin.buffer.readline().split()))
C = [list(map(ord, sys.stdin.buffer.readline().decode().rstrip())) for _ in range(H)]
C = np.array(C, dtype='int').T


# @debug
def solve(left_w):
    # 隣り合う2個の最小コストが分かれば、いい感じに沈めていけばそれらの和を全体のコストにできる
    # left_w と left_w + 1 の列の最小コストを求めます
    s1 = C[left_w]
    s2 = C[left_w + 1]

    cum1 = []  # cum1[i]: s1 が i 沈んでる
    cum2 = []  # cum2[i]: s2 が i 沈んでる
    for h in range(H + 1):
        cum = [0]
        s = 0
        for c1, c2 in zip(s1, s2[h:]):
            s += c1 == c2
            cum.append(s)
        cum1.append(cum)
        cum = [0]
        s = 0
        for c1, c2 in zip(s1[h:], s2):
            s += c1 == c2
            cum.append(s)
        cum2.append(cum)

    # cums[i]:  s1 が i 沈んでる
    # cums[-i]: s2 が i 沈んでる
    cums = cum1 + cum2[1:][::-1]

    # costs[i][j]: s1 を i 回、s2 を j 回沈めている状態の次のコスト
    costs = [[0] * (H + 1) for _ in range(H + 1)]
    for i, j in itertools.product(range(H + 1), range(H + 1)):
        cum = cums[i - j]
        costs[i][j] = cum[~min(i, j)]

    # dp[i][j]: s1をi回、s2をj回沈めたときのコストの最小値
    dp = [[INF] * (H + 1) for _ in range(H + 1)]
    dp[0][0] = 0
    for i, j in itertools.product(range(H + 1), range(H + 1)):
        if i + 1 <= H:
            # i を沈める
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + costs[i][j])
        if j + 1 <= H:
            # j を沈める
            dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + costs[i][j])
    return dp[H][H]


hs = np.arange(H + 1, dtype=int)


def solve_np(left_w):
    s1 = C[left_w]
    s2 = C[left_w + 1]

    # cums[i]:  s1 が i 沈んでる
    # cums[-i]: s2 が i 沈んでる
    cums = np.zeros((H * 2 + 1, H + 1), dtype=int)
    cums[0, 1:] = (s1 == s2).cumsum()
    for h in range(1, H):
        cums[h][h + 1:] = (s1[:-h] == s2[h:]).cumsum()
        cums[-h][h + 1:] = (s1[h:] == s2[:-h]).cumsum()

    # costs[i][j]: s1 を i 回、s2 を j 回沈めている状態の次のコスト
    costs = cums[np.subtract.outer(hs, hs), ~np.minimum.outer(hs, hs)]

    # dp[i][j]: s1をi回、s2をj回沈めたときのコストの最小値
    dp = np.full((H + 2, H + 2), IINF, dtype=int)
    dp[0][0] = 0
    for i in range(H * 2):
        idx = hs[max(0, i - H):i + 1]
        dp[idx, idx[::-1] + 1] = np.minimum(
            dp[idx, idx[::-1] + 1],
            dp[idx, idx[::-1]] + costs[idx, idx[::-1]]
        )
        dp[idx + 1, idx[::-1]] = np.minimum(
            dp[idx + 1, idx[::-1]],
            dp[idx, idx[::-1]] + costs[idx, idx[::-1]]
        )
    return dp[H][H]


ans = 0
for w in range(W - 1):
    # ans += solve(w)
    ans += solve_np(w)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import os
import sys

# import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, W = list(map(int, sys.stdin.buffer.readline().split()))
C = [list(map(ord, sys.stdin.buffer.readline().decode().rstrip())) for _ in range(H)]

# C = np.array(C, dtype='int')


# @debug
def solve(left_w):
    # 隣り合う2個の最小コストが分かれば、いい感じに沈めていけばそれらの和を全体のコストにできる
    # left_w と left_w + 1 の列の最小コストを求めます
    s1 = [C[h][left_w] for h in range(H)]
    s2 = [C[h][left_w + 1] for h in range(H)]

    cum1 = []  # cum1[i]: s1 が i 沈んでる
    cum2 = []  # cum2[i]: s2 が i 沈んでる
    for h in range(H + 1):
        cum = [0]
        s = 0
        for c1, c2 in zip(s1, s2[h:]):
            s += c1 == c2
            cum.append(s)
        cum1.append(cum)
        cum = [0]
        s = 0
        for c1, c2 in zip(s1[h:], s2):
            s += c1 == c2
            cum.append(s)
        cum2.append(cum)

    # cums[i]:  s1 が i 沈んでる
    # cums[-i]: s2 が i 沈んでる
    cums = cum1 + cum2[1:][::-1]

    # costs[i][j]: s1 を i 回、s2 を j 回沈めている状態の次のコスト
    costs = [[0] * (H + 1) for _ in range(H + 1)]
    for i, j in itertools.product(range(H + 1), range(H + 1)):
        cum = cums[i - j]
        costs[i][j] = cum[~min(i, j)]

    # dp[i][j]: s1をi回、s2をj回沈めたときのコストの最小値
    dp = [[INF] * (H + 1) for _ in range(H + 1)]
    dp[0][0] = 0
    for i, j in itertools.product(range(H + 1), range(H + 1)):
        if i + 1 <= H:
            # i を沈める
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + costs[i][j])
        if j + 1 <= H:
            # j を沈める
            dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + costs[i][j])
    return dp[H][H]


def solve_np(left_w):
    s1 = C[:, left_w]
    s2 = C[:, left_w + 1]

    # cums[i]:  s1 が i 沈んでる
    # cums[-i]: s2 が i 沈んでる
    cums = np.zeros((H * 2 + 1, H + 1), dtype=int)
    cums[0, 1:] = (s1 == s2).cumsum()
    for h in range(1, H):
        cums[h][h + 1:] = (s1[:-h] == s2[h:]).cumsum()
        cums[-h][h + 1:] = (s1[h:] == s2[:-h]).cumsum()

    # costs[i][j]: s1 を i 回、s2 を j 回沈めている状態の次のコスト
    hs = np.arange(H + 1, dtype=int)
    costs = cums[np.subtract.outer(hs, hs), ~np.minimum.outer(hs, hs)].tolist()

    # dp[i][j]: s1をi回、s2をj回沈めたときのコストの最小値
    dp = [[INF] * (H + 1) for _ in range(H + 1)]
    dp[0][0] = 0
    for i in range(H + 1):
        for j in range(H + 1):
            if i + 1 <= H:
                # i を沈める
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + costs[i][j])
            if j + 1 <= H:
                # j を沈める
                dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + costs[i][j])
    return dp[H][H]


ans = 0
for w in range(W - 1):
    ans += solve(w)
    # ans += solve_np(w)
print(ans)