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

Solution (Python):
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
c = [input().rstrip() for _ in range(H)]
ans = 0
for w in range(W-1):
    cum1 = [[0] * (H + 1) for _ in range(H + 1)]
    for d in range(H):
        for i in range(H - d):
            cum1[d][i+1] = cum1[d][i] + (c[i][w] == c[d+i][w+1])
    cum2 = [[0] * (H + 1) for _ in range(H + 1)]
    for d in range(H):
        for i in range(H - d):
            cum2[d][i+1] = cum2[d][i] + (c[d+i][w] == c[i][w+1])
    dp = [[0] * (H + 1) for _ in range(H + 1)]
    for i in range(1, H+1):
        for j in range(1, H+1):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1])
            if i >= j:
                dp[i][j] += cum1[i-j][j]
            else:
                dp[i][j] += cum2[j-i][i]
    ans += dp[H][H]
print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = list(map(int, input().split()))
c = [None]*h
for i in range(h):
    c[i] = input()


























        




ans = 0
for i in range(w-1):
    c0 = [c[j][i] for j in range(h)]
    c1 = [c[j][i+1] for j in range(h)]
    dp = [[None]*(h+1) for _ in range(h+1)]
    for i in range(h+1):
        dp[i][0] = 0
        dp[0][i] = 0
    val = [None]*(2*h+1) 
    for i in range(h):
        
        l = []
        v = 0
        for j in range(i):
            if c1[h-i+j]==c0[j]:
                v += 1
            l.append(v)
        val[i] = l
    for i in range(h, -1, -1):
        
        l = []
        v = 0
        for j in range(i):
            if c0[h-i+j]==c1[j]:
                v += 1
            l.append(v)
        val[h+(h-i)] = l
        
    for i in range(1, h+1):
        for j in range(1, h+1):
            cost = val[(i)-j+h][min(i,j)-1]
            dp[i][j] = min(dp[i-1][j]+cost, dp[i][j-1]+cost)
    ans += dp[h][h]



print(ans)

Solution (Python):
h,w = map(int,input().split())
c = [input() for _ in range(h)]

ans = 0
for i in range(w-1):
    cost = [[0] * (h+1) for _ in range(h+1)]
    for ci in range(1,h+1):
        for cj in range(ci,h+1):
            cost[ci][cj] = cost[ci-1][cj-1] + (c[ci-1][i] == c[cj-1][i+1])

    for cj in range(1,h+1):
        for ci in range(cj+1,h+1):
            cost[ci][cj] = cost[ci-1][cj-1] + (c[ci-1][i] == c[cj-1][i+1])

    dp = [[0] * (h+1) for _ in range(h+1)]
    for ci in range(1,h+1):
        for cj in range(1,h+1):
            dp[ci][cj] = min(dp[ci-1][cj], dp[ci][cj-1]) + cost[ci][cj]

    ans += dp[-1][-1]

print(ans)

Solution (Python):
H,W=map(int,input().split())
c=[input() for i in range(H)]
res=0
for i in range(W-1):
    dp=[[0 for j in range(H+1)] for k in range(H+1)]
    table=[[0 for j in range(H+1)] for k in range(H+1)]
    for j in range(1,H+1):
        for k in range(1,H+1):
            table[j][k]=table[j-1][k-1]+(c[j-1][i]==c[k-1][i+1])

    for j in range(1,H+1):
        for k in range(1,H+1):
            cost=table[j][k]
            dp[j][k]=cost+min(dp[j-1][k],dp[j][k-1])
    res+=dp[H][H]

print(res)

Solution (Python):
import sys
input = sys.stdin.readline
INF = 10**10
h, w = map(int, input().split())
C = [input().rstrip() for _ in range(h)]
def solve(b):
  cost = [[0]*(h+1) for _ in range(h+1)]
  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 and j:
        cost[i][j] = cost[i-1][j-1] - (C[h-i][b] == C[h-j][b+1])
      else:
        for r in range(min(h-i, h-j)):
          cost[i][j] += C[j+r][b] == C[i+r][b+1]
      if i:
        dp[i][j] = min(dp[i][j], dp[i-1][j]+cost[i-1][j])
      if j:
        dp[i][j] = min(dp[i][j], dp[i][j-1]+cost[i][j-1])
  return dp[h][h]
ans = 0
for b in range(w-1):
  ans += solve(b)
print(ans)

Solution (Python):
n,m = map(int,input().split())
a = [input().rstrip() for i in range(n)]
b = list(zip(*a))
for i in range(m):
  b[i] = "".join(b[i])
ans = 0
ct1 = [[0 for k in range(n-j+1)] for j in range(n+1)]
ct2 = [[0 for k in range(n-j+1)] for j in range(n+1)]
dp = [[10**5 for i in range(n+1)] for j in range(n+1)]
for i in range(m-1):
  b1 = b[i]
  b2 = b[i+1]
  for j in range(n+1):
    ct1[j][0] = 0
    ct2[j][0] = 0
    for k in range(n-j):
      ct1[j][k+1] = ct1[j][k]
      ct2[j][k+1] = ct2[j][k]
      if b1[k+j] == b2[k]:
        ct1[j][k+1] += 1
      if b2[k+j] == b1[k]:
        ct2[j][k+1] += 1
  dp[0][0] = 0
  for i in range(n+1):
    if i < n:
      dp[i+1][0] = 10**6
    for j in range(n+1):
      if i == 0 and j < n:
        dp[i][j+1] = 10**6
      if i <= j:
        cost = ct2[j-i][n-j]
      else:
        cost = ct1[i-j][n-i]
      if j < n:
        dp[i][j+1] = min(dp[i][j+1],dp[i][j]+cost)
      if i < n:
        dp[i+1][j] = dp[i][j]+cost
  ans += dp[-1][-1]
print(ans)

Solution (Python):
def main():
    h, w = map(int, input().split())
    grid = [list(input()) for _ in [0]*h]
    grid = [[grid[j][i] for j in range(h)] for i in range(w)]
    ans = 0
    for i in range(w-1):
        same = [[0]*(h+1) for _ in [0]*(h+1)]
        for j in range(h-1, -1, -1):
            for k in range(h-1, -1, -1):
                same[j][k] += same[j+1][k+1]+(grid[i][-j-1] == grid[i+1][-k-1])
        dp = [[10**10]*(h+1) for _ in [0]*(h+1)]
        dp[0][0] = same[0][0]
        for j in range(h+1):
            for k in range(h+1):
                if j != 0:
                    dp[j][k] = min(dp[j][k], dp[j-1][k]+same[j][k])
                if k != 0:
                    dp[j][k] = min(dp[j][k], dp[j][k-1]+same[j][k])
        ans += dp[h][h]
    print(ans)


main()

Solution (Python):
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
h2 = (h + 1) * (h + 1)

ans = 0
dq = [0] * h2
for wi in range(w - 1):
    for diff in range(h + 1):
        cnt1 = 0
        cnt2 = 0
        for i in range(h - diff):
            cnt1 += (c[i * w + wi] == c[(i + diff) * w + wi + 1])
            cnt2 += (c[(i + diff) * w + wi] == c[i * w + wi + 1])
        dq[diff * (h + 1)] = cnt1
        dq[diff] = cnt2
        for i in range(h - diff - 1):
            cnt1 -= (c[(h - i - 1 - diff) * w + wi] == c[(h - i - 1) * w + wi + 1])
            dq[(i + 1 + diff) * (h + 1) + i + 1] = cnt1
            cnt2 -= (c[(h - i - 1 - diff) * w + wi + 1] == c[(h - i - 1) * w + wi])
            dq[(i + 1) * (h + 1) + i + 1 + diff] = cnt2
            
    dp = [INF] * h2
    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)

Solution (Python):
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])

    dq = [[INF] * (h + 1) for i in range(h + 1)]
    dq[0][0] = 0
    for i in range(h):
        dq[i + 1][0] = dq[i][0] + dp[h - i][h]
        dq[0][i + 1] = dq[0][i] + dp[h][h - i]  
    for i in range(h):
        for j in range(h):
            dq[i + 1][j + 1] = min(dq[i + 1][j] + dp[h - (i + 1)][h - j],
                                   dq[i][j + 1] + dp[h - i][h - (j + 1)])

    return dq[h][h]


h, w = map(int, input().split())
s = [input() for i in range(h)]
INF = 10 ** 5
OFFSET = 500

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

Solution (Python):
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)**2)]
    dp = [0 for _ in range((h+1)**2)]
    for j in range(W-1):
        for x in range(h,0,-1):
            for y in range(h,0,-1):
                w[(x-1)*(h+1)+y-1] = w[x*(h+1)+y]
                if c[h-x][j] == c[h-y][j+1]:
                    w[(x-1)*(h+1)+y-1] += 1
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 or y == 0:
                    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
                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[-1]
    print(ans)
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline

h,w = map(int,input().split())

c = []
for i in range(w):
    c.append(chr(150+i))

for i in range(h):
    inp = input()
    for j in range(w):
        c.append(inp[j])
h += 1
h2 = h**2
res = 0

for j in range(1,w):
    
    
    d = [0]*(h2)

    for x in range(1,h):
        for y in range(1,h):
            if c[x*w+j] == c[y*w+j-1]:
                d[x*h+y] = d[x*h+y-h-1] + 1
            else:
                d[x*h+y] = d[x*h+y-h-1]
    
    
    dp = [10**10]*h2

    for i in range(h):
        dp[i] = dp[i*h] = 0

    for x in range(1,h):
        for y in range(1,h):
            if dp[x*h+y-1] < dp[x*h-h+y]:
                dp[x*h+y] = dp[x*h+y-1] + d[x*h+y]
            else:
                dp[x*h+y] = dp[x*h-h+y] + d[x*h+y]
    res += dp[-1]

print(res)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        grid.append(input().rstrip('\n'))

    le = [''] * H
    for i in range(H):
        le[i] = grid[i][0]

    ans = 0
    for w in range(1, W):
        ri = [''] * H
        for i in range(H):
            ri[i] = grid[i][w]
        cost = [[0] * (H+1) for _ in range(H+1)]
        for i in range(1, H+1):
            for j in range(1, H+1):
                cost[i][j] = cost[i-1][j-1] + int(le[i-1] == ri[j-1])

        inf = 1000000007
        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:
                    if dp[i][j] + cost[i+1][j] < dp[i+1][j]:
                        dp[i+1][j] = dp[i][j] + cost[i+1][j]
                if j+1 <= H:
                    if dp[i][j] + cost[i][j+1] < dp[i][j+1]:
                        dp[i][j+1] = dp[i][j] + cost[i][j+1]
        ans += dp[-1][-1]
        le = ri[:]
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
readline = sys.stdin.readline

inf = 10**9+7
def calc(W1, W2):
    H = len(W1)
    cost = [[0]*(1+H) for _ in range(1+H)]
    for i in range(H):
        for j in range(H):
            cost[i+1][j+1] = cost[i][j] + (1 if W1[i] == W2[j] else 0)
    dp = [[inf]*(1+H) for _ in range(1+H)]
    dp[H][H] = 0
    for s in range(2*H, 0, -1):
        for i1 in range(max(0, s-H), 1+min(s, H)):
            i2 = s - i1
            c = dp[i1][i2] + cost[i1][i2]
            if i1:
                dp[i1-1][i2] = min(dp[i1-1][i2], c)
            if i2:
                dp[i1][i2-1] = min(dp[i1][i2-1], c)
    return dp[0][0]

H, W = map(int, readline().split())

G = [list(map(lambda x:ord(x)-97, readline().strip())) for _ in range(H)]
G = list(map(list, zip(*G)))        
ans = 0
for i in range(W-1):
    ans += calc(G[i], G[i+1])
print(ans)

Solution (Python):





def accumulate_reverse(S1, S2):
    n = min(len(S1), len(S2))
    res = [0] * (n+1)
    c = 0
    for i in range(n):
        if S1[i] == S2[i]:
            c += 1
        res[n-i-1] = 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:]):
    
    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 = [[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)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+1),dtype=np.int64)
for r in range(H):
    dp_1[:,r+2:r+H+2,r+1] = (C[:-1] == C[1:,r][:,None])

INF = 10**18

dp = np.full((W-1,H+1),INF,dtype=np.int64)
dp[:,0] = 0
for n in range(1,H+H+1):
    if n >= 2:
        dp_1[:,n,1:] += dp_1[:,n-2,:-1]
    
    prev = dp
    dp = np.full((W-1,H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:] = np.minimum(dp[:,:],prev[:,:])
    dp += dp_1[:,n,:]
answer = dp[:,H].sum()
print(answer)

Solution (Python):
R=range
N,M,*S=open(0).read().split()
N=int(N)+1
M=int(M)-1
l=lambda:[[0]*N for _ in R(N)]
C=l()
D=l()
r=0
for t in R(M):
	for i in R(1,N):
		for j in R(1,N):u=C[i][j]=C[i-1][j-1]+(S[i-1][t]==S[j-1][t+1]);v=D[i][j]=min(D[i-1][j],D[i][j-1])+u
	r+=v
print(r)

Solution (Python):
R=range
N,M,*S=open(0).read().split()
N=int(N)+1
M=int(M)-1
l=lambda:[[0]*N for _ in R(N)]
C=l()
D=l()
r=0
for t in R(M):
	for i in R(1,N):
		for j in R(1,N):u=C[i][j]=C[i-1][j-1]+(S[i-1][t]==S[j-1][t+1]);D[i][j]=min(D[i-1][j],D[i][j-1])+u
	r+=D[N-1][N-1]
print(r)

Solution (Python):
R=range
N,M,*S=open(0).read().split()
N=int(N)+1
M=int(M)-1
l=lambda:[[0]*N for _ in R(N)]
C=l()
D=l()
r=0
for t in R(M):
	for i in R(1,N):
		for j in R(1,N):C[i][j]=C[i-1][j-1]+(S[i-1][t]==S[j-1][t+1]);D[i][j]=min(D[i-1][j],D[i][j-1])+C[i][j]
	r+=D[N-1][N-1]
print(r)

Solution (Python):
N,M=map(int,input().split());C=[[0]*-~N for _ in range(N+1)];D=list(map(list,C));S=[input()for _ in range(N)];r=0
for t in range(M-1):
	for i in range(1,N+1):
		for j in range(1,N+1):C[i][j]=C[i-1][j-1]+int(S[i-1][t]==S[j-1][t+1]);D[i][j]=min(D[i-1][j],D[i][j-1])+C[i][j]
	r+=D[N][N]
print(r)

Solution (Python):
N,M=map(int,raw_input().split());C=[[0]*-~N for _ in range(N+1)];D=map(list,C);S=[raw_input()for _ in range(N)];r=0
for t in range(M-1):
	for i in range(1,N+1):
		for j in range(1,N+1):C[i][j]=C[i-1][j-1]+int(S[i-1][t]==S[j-1][t+1]);D[i][j]=min(D[i-1][j],D[i][j-1])+C[i][j]
	r+=D[N][N]
print r

Solution (Python):
N,M=map(int,input().split());C=[[0]*-~N for _ in range(N+1)];D=list(map(list,C));S=[input()for _ in range(N)];r=0
for t in range(M-1):
	for i in range(1,N+1):
		for j in range(1,N+1):C[i][j]=C[i-1][j-1]+int(S[i-1][t]==S[j-1][t+1]);D[i][j]=min(D[i-1][j],D[i][j-1])+C[i][j]
	r+=D[N][N]
print(r)

Solution (Python):
H, W = map(int, raw_input().split())
a = [raw_input().strip() for _ in xrange(H)]
a = map(''.join, zip(*a))
ans = 0
def solve(a, c):
    shift = [[0] * (H+1) for _ in xrange(H+1)]
    for i in reversed(xrange(H)):
        for j in reversed(xrange(H)):
            shift[i][j] = shift[i+1][j+1] + int(a[H-1-i] == c[H-1-j])
    dp = [[float('inf')] * (H+1) for _ in xrange(H+1)]
    for i in xrange(H+1):
        for j in xrange(H+1):
            b = 2147483647
            if i == j == 0:
                b = 0
            if i > 0:
                b = min(b, dp[i-1][j] + shift[i-1][j])
            if j > 0:
                b = min(b, dp[i][j-1] + shift[i][j-1])
            dp[i][j] = b
    
    return dp[H][H]
for i in xrange(W-1):
    i1 = i
    i2 = i+1
    ans += solve(a[i1], a[i2])
print ans