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 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(sys.stdin.buffer.readline().decode().rstrip()) for _ in range(H)]

C = np.array(C, dtype='U1')


# @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)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import os
import sys

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 = [sys.stdin.buffer.readline().decode().rstrip() for _ in range(H)]


# @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]


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

Submission status: Time Limit Exceeded

Solution code:
def main():
    h,W = map(int,input().split())
    c = [tuple(input()) for _ in range(h)]
    c = tuple(c)
    ans = 0
    w = [0 for _ in range((h+1)**2)]
    dp = [0 for _ in range((h+1)**2)]
    for j in range(W-1):
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 or y == 0:
                    w[x*(h+1)+y] = 0
                    for z in range(h-max(x,y)):
                        if c[y+z][j] == c[x+z][j+1]:
                            w[x*(h+1)+y] += 1
                    if x == y:
                        dp[x*h+y] = 0
                    elif x == 0:
                        dp[x*(h+1)+y] = dp[x*(h+1)+y-1]+w[x*(h+1)+y-1]
                    else:
                        dp[x*(h+1)+y] = dp[(x-1)*(h+1)+y]+w[(x-1)*(h+1)+y]
                    continue
                w[x*(h+1)+y] = w[(x-1)*(h+1)+y-1]
                if c[h-x][j] == c[h-y][j+1]:
                    w[x*(h+1)+y] -= 1
                dp[x*(h+1)+y] = min(dp[x*(h+1)+y-1]+w[x*(h+1)+y-1],dp[(x-1)*(h+1)+y]+w[(x-1)*(h+1)+y])
        ans += dp[(h+1)**2-1]
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    h,W = map(int,input().split())
    c = [tuple(input()) for _ in range(h)]
    c = tuple(c)
    ans = 0
    w = [[0 for _ in range(h+1)] for _ in range(h+1)]
    dp = [0 for _ in range((h+1)**2)]
    for j in range(W-1):
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 or y == 0:
                    w[x][y] = 0
                    for z in range(h-max(x,y)):
                        if c[y+z][j] == c[x+z][j+1]:
                            w[x][y] += 1
                    if x == y:
                        dp[x*h+y] = 0
                    elif x == 0:
                        dp[x*(h+1)+y] = dp[x*(h+1)+y-1]+w[x][y-1]
                    else:
                        dp[x*(h+1)+y] = dp[(x-1)*(h+1)+y]+w[x-1][y]
                    continue
                w[x][y] = w[x-1][y-1]
                if c[h-x][j] == c[h-y][j+1]:
                    w[x][y] -= 1
                dp[x*(h+1)+y] = min(dp[x*(h+1)+y-1]+w[x][y-1],dp[(x-1)*(h+1)+y]+w[x-1][y])
        ans += dp[(h+1)**2-1]
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    h,W = map(int,input().split())
    c = [tuple(input()) for _ in range(h)]
    c = tuple(c)
    ans = 0
    w = [[0 for _ in range(h+1)] for _ in range(h+1)]
    dp = [[0 for _ in range(h+1)] for _ in range(h+1)]
    for j in range(W-1):
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 or y == 0:
                    w[x][y] = 0
                    for z in range(h-max(x,y)):
                        if c[y+z][j] == c[x+z][j+1]:
                            w[x][y] += 1
                    if x == y:
                        dp[x][y] = 0
                    elif x == 0:
                        dp[x][y] = dp[x][y-1]+w[x][y-1]
                    else:
                        dp[x][y] = dp[x-1][y]+w[x-1][y]
                    continue
                w[x][y] = w[x-1][y-1]
                if c[h-x][j] == c[h-y][j+1]:
                    w[x][y] -= 1
                dp[x][y] = min(dp[x][y-1]+w[x][y-1],dp[x-1][y]+w[x-1][y])
        ans += dp[h][h]
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    h,W = map(int,input().split())
    c = [tuple(input()) for _ in range(h)]
    c = tuple(c)
    ans = 0
    w = [[0 for _ in range(h+1)] for _ in range(h+1)]
    dp = [[0 for _ in range(h+1)] for _ in range(h+1)]
    for j in range(W-1):
        for x in range(h+1):
            for y in range(h+1):
                w[x][y] = 0
                if x == 0 and y == 0:
                    for z in range(h):
                        if c[z][j] == c[z][j+1]:
                            w[x][y] += 1
                    dp[x][y] = 0
                    continue
                if x == 0:
                    for z in range(h-y):
                        if c[y+z][j] == c[z][j+1]:
                            w[x][y] += 1
                    dp[x][y] = dp[x][y-1]+w[x][y-1]
                    continue
                if y == 0:
                    for z in range(h-x):
                        if c[z][j] == c[x+z][j+1]:
                            w[x][y] += 1
                    dp[x][y] = dp[x-1][y]+w[x-1][y]
                    continue
                w[x][y] = w[x-1][y-1]
                if c[h-x][j] == c[h-y][j+1]:
                    w[x][y] -= 1
                dp[x][y] = min(dp[x][y-1]+w[x][y-1],dp[x-1][y]+w[x-1][y])
        ans += dp[h][h]
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    h,W = map(int,input().split())
    c = [tuple(input()) for _ in range(h)]
    c = tuple(c)
    ans = 0
    w = [[0 for _ in range(h+1)] for _ in range(h+1)]
    dp = [[0 for _ in range(h+1)] for _ in range(h+1)]
    for j in range(W-1):
        for x in range(h+1):
            w[0][x] = 0
            for z in range(h-x):
                if c[x+z][j] == c[z][j+1]:
                    w[0][x] += 1
        for x in range(1,h+1):
            w[x][0] = 0
            for z in range(h-x):
                if c[z][j] == c[x+z][j+1]:
                    w[x][0] += 1
        for x in range(1,h+1):
            for y in range(1,h+1):
                w[x][y] = w[x-1][y-1]
                if c[h-x][j] == c[h-y][j+1]:
                    w[x][y] -= 1
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 and y == 0:
                    dp[x][y] = 0
                    continue
                if x == 0:
                    dp[x][y] = dp[x][y-1]+w[x][y-1]
                elif y == 0:
                    dp[x][y] = dp[x-1][y]+w[x-1][y]
                else:
                    dp[x][y] = min(dp[x][y-1]+w[x][y-1],dp[x-1][y]+w[x-1][y])
        ans += dp[h][h]
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    h,w = map(int,input().split())
    c = [tuple(input()) for _ in range(h)]
    c = tuple(c)
    ans = 0
    for j in range(w-1):
        w = [[0 for _ in range(h+1)] for _ in range(h+1)]
        for x in range(h+1):
            for z in range(h-x):
                if c[x+z][j] == c[z][j+1]:
                    w[0][x] += 1
        for x in range(1,h+1):
            for z in range(h-x):
                if c[z][j] == c[x+z][j+1]:
                    w[x][0] += 1
        for x in range(1,h+1):
            for y in range(1,h+1):
                w[x][y] = w[x-1][y-1]
                if c[h-x][j] == c[h-y][j+1]:
                    w[x][y] -= 1
        dp = [[0 for _ in range(h+1)] for _ in range(h+1)]
        dp[0][0] = 0
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 and y == 0:
                    continue
                if x == 0:
                    dp[x][y] = dp[x][y-1]+w[x][y-1]
                elif y == 0:
                    dp[x][y] = dp[x-1][y]+w[x-1][y]
                else:
                    dp[x][y] = min(dp[x][y-1]+w[x][y-1],dp[x-1][y]+w[x-1][y])
        ans += dp[h][h]
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    h,w = map(int,input().split())
    c = [tuple(input()) for _ in range(h)]
    ans = 0
    for j in range(w-1):
        w = [[0 for _ in range(h+1)] for _ in range(h+1)]
        
        for x in range(h+1):
            for z in range(h-x):
                if c[x+z][j] == c[z][j+1]:
                    w[0][x] += 1
        for x in range(1,h+1):
            for z in range(h-x):
                if c[z][j] == c[x+z][j+1]:
                    w[x][0] += 1
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 or y == 0:
                    continue
                else:
                    if c[h-x][j] == c[h-y][j+1]:
                        w[x][y] = w[x-1][y-1]-1
                    else:
                        w[x][y] = w[x-1][y-1]
        dp = [[0 for _ in range(h+1)] for _ in range(h+1)]
        dp[0][0] = 0
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 and y == 0:
                    continue
                if x == 0:
                    dp[x][y] = dp[x][y-1]+w[x][y-1]
                elif y == 0:
                    dp[x][y] = dp[x-1][y]+w[x-1][y]
                else:
                    dp[x][y] = min(dp[x][y-1]+w[x][y-1],dp[x-1][y]+w[x-1][y])
        ans += dp[h][h]
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    h,w = inpm()
    c = [tuple(input()) for _ in range(h)]
    ans = 0
    for j in range(w-1):
        w = [[0 for _ in range(h+1)] for _ in range(h+1)]
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 or y == 0:
                    for z in range(h-max(x,y)):
                        if c[x+z][j] == c[y+z][j+1]:
                            w[y][x] += 1
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 or y == 0:
                    continue
                else:
                    if c[h-x][j] == c[h-y][j+1]:
                        w[x][y] = w[x-1][y-1]-1
                    else:
                        w[x][y] = w[x-1][y-1]
        dp = [[10**10 for _ in range(h+1)] for _ in range(h+1)]
        dp[0][0] = 0
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 and y == 0:
                    continue
                if x == 0:
                    dp[x][y] = dp[x][y-1]+w[x][y-1]
                elif y == 0:
                    dp[x][y] = dp[x-1][y]+w[x-1][y]
                else:
                    dp[x][y] = min(dp[x][y-1]+w[x][y-1],dp[x-1][y]+w[x-1][y])
        ans += dp[h][h]
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    h,w = inpm()
    c = [list(input()) for _ in range(h)]
    ans = 0
    for j in range(w-1):
        w = [[0 for _ in range(h+1)] for _ in range(h+1)]
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 or y == 0:
                    for z in range(h-max(x,y)):
                        if c[x+z][j] == c[y+z][j+1]:
                            w[y][x] += 1
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 or y == 0:
                    continue
                else:
                    if c[h-x][j] == c[h-y][j+1]:
                        w[x][y] = w[x-1][y-1]-1
                    else:
                        w[x][y] = w[x-1][y-1]
        dp = [[10**10 for _ in range(h+1)] for _ in range(h+1)]
        dp[0][0] = 0
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 and y == 0:
                    continue
                if x == 0:
                    dp[x][y] = dp[x][y-1]+w[x][y-1]
                elif y == 0:
                    dp[x][y] = dp[x-1][y]+w[x-1][y]
                else:
                    dp[x][y] = min(dp[x][y-1]+w[x][y-1],dp[x-1][y]+w[x-1][y])
        ans += dp[h][h]
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate_reverse(S1, S2):
    res = [0]
    c = 0
    for i in range(min(len(S1), len(S2))):
        if S1[i] == S2[i]:
            c += 1
        res.append(c)
    return res[::-1]

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    Z1.append(accumulate_reverse(C1, C2))
    for j in range(1, H+1):
        Z1.append(accumulate_reverse(C1, C2[j:]))
        Z2.append(accumulate_reverse(C1[j:], C2))
    Z1 += Z2[::-1]
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + Z1[j-k][min(j, k)]
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate_reverse(S1, S2):
    res = [0]
    c = 0
    for i in range(min(len(S1), len(S2))):
        if S1[i] == S2[i]:
            c += 1
        res.append(c)
    res.reverse()
    return res

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    Z1.append(accumulate_reverse(C1, C2))
    for j in range(1, H+1):
        Z1.append(accumulate_reverse(C1, C2[j:]))
        Z2.append(accumulate_reverse(C1[j:], C2))
    Z1 += Z2[::-1]
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + Z1[j-k][min(j, k)]
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate_reverse(S1, S2):
    res = [0]
    c = 0
    for i in range(min(len(S1), len(S2))):
        if S1[i] == S2[i]:
            c += 1
        res.append(c)
    res.reverse()
    return res

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    z1 = accumulate_reverse(C1, C2);  Z1.append(z1)
    for j in range(1, H+1):
        z1 = accumulate_reverse(C1, C2[j:]);  Z1.append(z1)
        z2 = accumulate_reverse(C1[j:], C2);  Z2.append(z2)
    Z1 += Z2[::-1]
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + Z1[j-k][min(j, k)]
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate(S1, S2):
    res = [0]
    c = 0
    for i in range(min(len(S1), len(S2))):
        if S1[i] == S2[i]:
            c += 1
        res.append(c)
    return res

import sys
input = sys.stdin.readline
inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))[:-1]
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    z1 = accumulate(C1, C2);  z1.reverse()
    Z1.append(z1)
    for j in range(1, H+1):
        z1 = accumulate(C1, C2[j:]);  z1.reverse();  Z1.append(z1)
        z2 = accumulate(C1[j:], C2);  z2.reverse();  Z2.append(z2)
    Z1 += Z2[::-1]
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + Z1[j-k][min(j, k)]
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate(S1, S2):
    res = [0]
    c = 0
    for i in range(min(len(S1), len(S2))):
        if S1[i] == S2[i]:
            c += 1
        res.append(c)
    return res

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    z1 = accumulate(C1, C2);  z1.reverse()
    Z1.append(z1)
    #Z2.append([])
    for j in range(1, H+1):
        z1 = accumulate(C1, C2[j:]);  z1.reverse();  Z1.append(z1)
        z2 = accumulate(C1[j:], C2);  z2.reverse();  Z2.append(z2)
    Z1 += Z2[::-1]
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + (Z1[j-k][min(j, k)])# if j>=k else Z2[k-j][j])
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate(S1, S2):
    res = [0]
    c = 0
    for i in range(min(len(S1), len(S2))):
        if S1[i] == S2[i]:
            c += 1
        res.append(c)
    return res

from itertools import product
inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    z1 = accumulate(C1, C2);  z1.reverse()
    Z1.append(z1)
    Z2.append([])
    for j in range(1, H+1):
        z1 = accumulate(C1, C2[j:]);  z1.reverse();  Z1.append(z1)
        z2 = accumulate(C1[j:], C2);  z2.reverse();  Z2.append(z2)
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j, k in product(range(H+1), repeat=2):
        cost = dp[j][k] + (Z1[j-k][k] if j>=k else Z2[k-j][j])
        dp[j+1][k] = min(dp[j+1][k], cost)
        dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate(S1, S2):
    res = [0]
    c = 0
    for i in range(min(len(S1), len(S2))):
        if S1[i] == S2[i]:
            c += 1
        res.append(c)
    return res

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    z1 = accumulate(C1, C2);  z1.reverse()
    Z1.append(z1)
    Z2.append([])
    for j in range(1, H+1):
        z1 = accumulate(C1, C2[j:]);  z1.reverse();  Z1.append(z1)
        z2 = accumulate(C1[j:], C2);  z2.reverse();  Z2.append(z2)
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + (Z1[j-k][k] if j>=k else Z2[k-j][j])
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

# TLE が厳しすぎる

def accumulate(S1, S2):
    res = [0]
    c = 0
    for i in range(min(len(S1), len(S2))):
        if S1[i] == S2[i]:
            c += 1
        res.append(c)
    return res

inf = 2 * 10**9
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    z1 = accumulate(C1, C2);  z1.reverse()
    Z1.append(z1)
    Z2.append([])
    for j in range(1, H+1):
        #z1 = accumulate(C1, C2[j:]);  z1.reverse();  Z1.append(z1)
        res1, res2 = [0], [0]
        c1 = c2 = 0
        for i in range(H-j):
            ij = i+j
            if C1[i] == C2[ij]:
                c1 += 1
            res1.append(c1)
            if C1[ij] == C2[i]:
                c2 += 1
            res2.append(c2)
        res1.reverse();  Z1.append(res1)
        res2.reverse();  Z2.append(res2)

    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + (Z1[j-k][k] if j>=k else Z2[k-j][j])
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)