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: Wrong Answer

Solution code:
def inpl(): return list(map(int, input().split()))

H, W = inpl()
C = [[0]*H for _ in range(W)]
for h in range(H):
    S = input()
    for w in range(W):
        C[w][h] = ord(S[w]) - 97

def calc_cost(L, R):
    def count(l, r):
        tmp = 0
        for i in range(H-max(l, r)):
            tmp += L[l+i] == R[r+i]
        return tmp
    DP = [[100000]*(H+1) for _ in range(H+1)]
    DP[0][0] = 0
    
    for x in range(2*H+1):
        for y in range(max(0, x-H), min(x+1, H+1)):
            c = count(x-y, y)
            if x-y < H:
                DP[x-y+1][y] = min(DP[x-y+1][y], DP[x-y][y] + c)
            if y < H:
                DP[x-y][y+1] = min(DP[x-y][y+1], DP[x-y][y] + c)

    return DP[-1][-1]

ans = 0
for i in range(W-1):
    ans += calc_cost(C[i], C[i+1])
print(ans)

Submission status: Wrong Answer

Solution code:
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[i] == c[j])
    dp = [[float('inf')] * (H+1) for _ in xrange(H+1)]
    for i in xrange(H+1):
        for j in xrange(H+1):
            b = []
            if i == j == 0:
                b.append(0)
            if i > 0:
                b.append(dp[i-1][j] + shift[i-1][j])
            if j > 0:
                b.append(dp[i][j-1] + shift[i][j-1])
            dp[i][j] = min(b)
    #print a, c, shift
    return dp[H][H]
for i in xrange(W-1):
    i1 = i
    i2 = i+1
    ans += solve(a[i1], a[i2])
print ans

Submission status: Wrong Answer

Solution code:
H, W = list(map(int, input().split()))
X = [input() for _ in range(H)]
Y = list(map(list, zip(*X)))


def get(A, B):
    cost = {}
    return 1

    def calc(A, B, a_n, b_n):
        
        if a_n >= H or b_n >= H:
            return 0
        if (a_n, b_n) in cost:
            return cost[(a_n, b_n)]
        start = max(a_n, b_n)
        ans = 0
        for i in range(start, H):
            if A[i - a_n] == B[i - b_n]:
                ans += 1
            cost[(a_n + H - 1 - i, b_n + H - 1 - i)] = ans
        return cost[(a_n, b_n)]

    for i in range(H):
        calc(A,B,0,i)
        calc(A,B,i,0)

    dp = [[999999999999999 for _ in range(H + 2)] for _ in range(H + 2)]
    dp[0][0] = 0

    for i in range(H + 1):
        for j in range(H + 1):
            dp[i + 1][j] = min(dp[i][j] + calc(A, B, i, j), dp[i + 1][j])
            dp[i][j + 1] = min(dp[i][j] + calc(A, B, i, j), dp[i][j + 1])
    # print(dp)
    return dp[H][H]


ans = 0
for i in range(W - 1):
    tmp = get(Y[i], Y[i + 1])
    ans += tmp
    # print(tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = list(map(int, input().split()))
X = [input() for _ in range(H)]
Y = list(map(list, zip(*X)))


def get(A, B):
    cost = {}

    def calc(A, B, a_n, b_n):
        return 1
        if a_n >= H or b_n >= H:
            return 0
        if (a_n, b_n) in cost:
            return cost[(a_n, b_n)]
        start = max(a_n, b_n)
        ans = 0
        for i in range(start, H):
            if A[i - a_n] == B[i - b_n]:
                ans += 1
            cost[(a_n + H - 1 - i, b_n + H - 1 - i)] = ans
        return cost[(a_n, b_n)]

    for i in range(H):
        calc(A,B,0,i)
        calc(A,B,i,0)

    dp = [[999999999999999 for _ in range(H + 2)] for _ in range(H + 2)]
    dp[0][0] = 0

    for i in range(H + 1):
        for j in range(H + 1):
            dp[i + 1][j] = min(dp[i][j] + calc(A, B, i, j), dp[i + 1][j])
            dp[i][j + 1] = min(dp[i][j] + calc(A, B, i, j), dp[i][j + 1])
    # print(dp)
    return dp[H][H]


ans = 0
for i in range(W - 1):
    tmp = get(Y[i], Y[i + 1])
    ans += tmp
    # print(tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
h, w = list(map(int, input().split()))
c = [[0] * h for i in range(w)]
for i in range(h):
    line = list(input())
    for j in range(w):
        c[j][i] = line[j]

mp1 = [[0 for i in range(h)] for j in range(h)]
mp2 = [[0 for i in range(h)] for j in range(h)]
mp = [[[0 for i in range(h)] for j in range(h)] for k in range(h)]

for i in range(h):
    mp1[i][0] = 0
    mp1[0][i] = 0  
    mp2[i][0] = 0
    mp2[0][i] = 0
    for j in range(1, h+1-i):
        if c[0][h-i-j] == c[1][h-j]:
            mp1[i][0] += 1
        if c[0][h-j] == c[1][h-i-j]:
            mp1[0][i] += 1
        if c[1][h-i-j] == c[2][h-j]:
            mp2[i][0] += 1
        if c[1][h-j] == c[2][h-i-j]:
            mp2[0][i] += 1

for i in range(1, h):
    for j in range(1, h):
        if c[0][i-1] == c[1][j-1]:
            mp1[i][j] = mp1[i-1][j-1] - 1
        else:
            mp1[i][j] = mp1[i-1][j-1]

        if c[1][i-1] == c[2][j-1]:
            mp2[i][j] = mp2[i-1][j-1] - 1
        else:
            mp2[i][j] = mp2[i-1][j-1]        

for i in range(1, h):
    mp[i][0][0] = mp[i-1][0][0] + mp1[i-1][0]
    mp[0][i][0] = mp[0][i-1][0] + mp1[0][i-1] + mp2[i-1][0]
    mp[0][0][i] = mp[0][0][i-1] + mp2[0][i-1]


for i in range(1, h):
    for j in range(1, h):
        for k in range(1, h):
            mp[i][j][k] = min(mp[i-1][j][k]+mp1[i-1][j], mp[i][j-1][k]+mp1[i][j-1]+mp2[j-1][k], mp[i][j][k-1]+mp2[j][k-1])

print(mp1, mp2)
print(mp[-1][-1][-1])

Submission status: Wrong Answer

Solution code:
import sys

H, W = list(map(int, input().split()))
arr = []
count = 0

if W == 1:
    print(0)
    sys.exit()
if W == 2:
    for i in range(H):
        a,b = list(input())
        if a == b:
            count += 1
    print(count)
    sys.exit()
if W == 3:
    for i in range(H):
        a,b,c = list(input())
        if a == b:
            count += 1
        if b == c:
            count += 1
    print(count)
    sys.exit()

Submission status: Wrong Answer

Solution code:
def f(col1, col2):
    # print(col1, col2)
    h1 = len(col1)
    h2 = len(col2)
    cache = [[None] * h2 for _ in range(h1)]
    def g(r1, r2):
        if cache[r1][r2] is not None:
            return cache[r1][r2]
        if r1 == -1 or r2 == -1:
            return 0
        c = sum(c1 == c2 for c1, c2 in zip(col1[-r1-1:], col2[-r2-1:]))
        cache[r1][r2] = min(g(r1-1, r2) + c, g(r1, r2-1) + c)
        return cache[r1][r2]
    return g(h1-1, h2-1)

if __name__ == "__main__":
    H, W = [int(i) for i in input().split()]
    if W != 3:
        raise
    field = list(zip(*[list(map(ord, input())) for _ in range(H)]))
    print(sum(f(col1, col2) for col1, col2 in zip(field, field[1:])))

Submission status: Wrong Answer

Solution code:
H,W = list(map(int,input().split()))
X= [input() for _  in range(H)]
Y = list(map(list, zip(*X)))


def _get(A,B):
    a=0
    b=0
    cache={}
    cache[(0,0)]=0

    def f(A,B, a_n,b_n):
        if a_n<0 or b_n<0:
            return 999999999999999999999

        if (a_n,b_n) in cache:
            return cache[a_n,b_n]

        res= min(f(A,B,a_n-1,b_n)+calc(A,B,a_n-1,b_n),f(A,B,a_n,b_n-1)+calc(A,B,a_n,b_n-1))
        cache[(a_n,b_n)]= res
        return res
    return f(A,B,H-1,H-1)


def get(A, B):
    cost ={}
    def calc(A, B, a_n, b_n):
        if a_n < 0 or b_n < 0:
            raise
        if a_n >= H or b_n >= H:
            return 0
        if (a_n,b_n) in cost:
            return cost[(a_n,b_n)]
        start = max(a_n, b_n)
        ans = 0
        #print(a_n,b_n)
        for i in range(start, H):
            if A[i - a_n] == B[i - b_n]:
                ans += 1
            cost[(a_n+H-1-i,b_n+H-1-i)]=ans
        return cost[(a_n,b_n)]


    dp = [[999999999999999 for _ in range(H+1)] for _ in range(H+1)]
    dp[0][0]=0

    for i in range(H):
        for j in range(H):
            dp[i+1][j] = min(dp[i][j] + calc(A, B, i  , j), dp[i+1][j])
            dp[i][j+1] = min(dp[i][j] + calc(A, B, i  , j), dp[i][j+1])
            continue
    #print(dp)
    return dp[H-1][H-1]




ans=0
for i in range(W-1):
    ans += get(Y[i],Y[i+1])
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3


def main():
    h, w = (int(x) for x in input().split())
    assert w == 3
    stage = [list(input()) for _ in range(h)]
    cost = 0
    for _ in range(h):
        for r in range(h):
            cost += (stage[r][0] == stage[r][1]) + (stage[r][1] == stage[r][2])
        for r in range(h - 1):
            stage[r + 1][1] = stage[r][1]
            stage[r][1] = "-"
    print(cost)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N ,K = list(map(int, input().split()))
ls = [ input() for j in range(N)]
cost = 0
for j in range(N): 
    for i in range(K-1):
        if ls[j][i] == ls[j][i+1]:
            cost +=1
            
print(cost)

Submission status: Wrong Answer

Solution code:
H,W = list(map(int,input().split()))
X= [input() for _  in range(H)]
Y = list(map(list, zip(*X)))


def _get(A,B):
    a=0
    b=0
    cache={}
    cache[(0,0)]=0

    def f(A,B, a_n,b_n):
        if a_n<0 or b_n<0:
            return 999999999999999999999

        if (a_n,b_n) in cache:
            return cache[a_n,b_n]

        res= min(f(A,B,a_n-1,b_n)+calc(A,B,a_n-1,b_n),f(A,B,a_n,b_n-1)+calc(A,B,a_n,b_n-1))
        cache[(a_n,b_n)]= res
        return res
    return f(A,B,H-1,H-1)


def get(A, B):

    dp = [[999999999999999 for _ in range(H+1)] for _ in range(H+1)]
    dp[0][0]=0

    for i in range(H):
        for j in range(H):
            dp[i+1][j] = min(dp[i][j] + calc(A, B, i  , j), dp[i+1][j])
            dp[i][j+1] = min(dp[i][j] + calc(A, B, i  , j), dp[i][j+1])
            continue
    #print(dp)
    return dp[H-1][H-1]



def calc(A, B, a_n, b_n):
    if a_n<0 or b_n<0:
        raise
    if a_n>=H or b_n>=H:
        return 0
    start= max(a_n,b_n)
    ans =0
    for i in range(start,H):
        if A[i-a_n]==B[i-b_n]:
            ans +=1
    return ans

ans=0
for i in range(W-1):
    ans += get(Y[i],Y[i+1])
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    h, w = map(int, raw_input().split())
    t = [raw_input() for i in range(h)]
    tr = [[e[i] for e in t] for i in range(w)]
    res = 0
    while tr != [["0" for j in range(h)] for i in range(w)]:
        x, tr = cal(tr)
        res += x
    print res


def cal(tr):
    now = 9999999999
    ret = 9999999999
    p = -1
    for i, e in enumerate(tr):
        if set(e) == set(["0"]):
            continue
        tmp1 = 0
        tmp2 = 0
        if i == 0:
            for x, y in enumerate(e):
                if y == "0":
                    continue
                if y == tr[i+1][x]:
                    tmp1 += 1
                if x != len(e)-1:
                    if y == tr[i+1][x+1]:
                        tmp2 += 1
            if now > tmp1+tmp2:
                now = tmp1+tmp2
                ret = tmp1
                p = i
        elif i == len(tr)-1:
            for x, y in enumerate(e):
                if y == "0":
                    continue
                if y == tr[i-1][x]:
                    tmp1 += 1
                if x != len(e)-1:
                    if y == tr[i-1][x+1]:
                        tmp2 += 1
            if now > tmp1+tmp2:
                now = tmp1+tmp2
                ret = tmp1
                p = i
        else:
            for x, y in enumerate(e):
                if y == "0":
                    continue
                if y == tr[i-1][x]:
                    tmp1 += 1
                if y == tr[i+1][x]:
                    tmp1 += 1
                if x != len(e)-1:
                    if y == tr[i-1][x+1]:
                        tmp2 += 1
                    if y == tr[i+1][x+1]:
                        tmp2 += 1
            if now >= tmp1+tmp2:
                now = tmp1+tmp2
                ret = tmp1
                p = i
    tr[p] = ["0"] + tr[p][:-1]
    return ret, tr


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
H,W = map(int,raw_input().split(" "))
data = [[],[],[]]
for i in range(H):
    line = raw_input()
    for w in range(W):
        data[w].append(line[w])
    




if W == 3:
    ans = 0
    for i in range(H):
        for j in range(i,H):
            if data[1][j] == data[0][j]:
                ans += 1
            if data[1][j] == data[2][j]:
                ans += 1
    print ans




else:
    pass

Submission status: Wrong Answer

Solution code:
from collections import Counter

N ,K = list(map(int, input().split()))
ls = [ input() for j in range(N)]

cnt = [[0 for i in range(25)] for i in range(N)]
al = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','w','x','y','z']
cost = 0
for j in range(N): 
    for i in range(25):
        Cnt = Counter(ls[j])
        cnt[j][i] = Cnt[al[i]]

for j in range(N):
    for i in range(25):
        if cnt[j][i] != 0 and cnt[j][i] !=1:
            cost +=cnt[j][i]
print(cost-1)

Submission status: Wrong Answer

Solution code:
def f(col1, col2):
    # print(col1, col2)
    H = len(col1)
    cache = [[None] * H for _ in range(H)]
    def g(r1, r2):
        if cache[r1][r2] is not None:
            return cache[r1][r2]
        if r1 == -1 or r2 == -1:
            return 0        
        c = sum(c1 == c2 for c1, c2 in zip(col1[-r1-1:], col2[-r2-1:]))
        cache[r1][r2] = min(g(r1-1, r2) + c, g(r1, r2-1) + c)
        return cache[r1][r2]
    return g(H-1, H-1)

if __name__ == "__main__":
    H, W = [int(i) for i in input().split()]
    if W != 3:
        raise
    field = list(zip(*[input() for _ in range(H)]))    
    print(sum(f(col1, col2) for col1, col2 in zip(field, field[1:])))

Submission status: Wrong Answer

Solution code:

def f(col1, col2):
    # print(col1, col2)
    H = len(col1)
    cache = [[None] * H for _ in range(H)]
    def g(r1, r2):
        if cache[r1][r2] is not None:
            return cache[r1][r2]
        if r1 == 0 or r2 == 0:
            return 0
        c = sum(c1 == c2 for c1, c2 in zip(col1[-r1-1:], col2[-r2-1:]))
        cache[r1][r2] = min(g(r1-1, r2) + c, g(r1, r2-1) + c)
        return cache[r1][r2]
    return g(H-1, H-1)

if __name__ == "__main__":
    H, W = [int(i) for i in input().split()]
    if W == 3:
        field = list(zip(*[input() for _ in range(H)]))
        print(sum(f(col1, col2) for col1, col2 in zip(field, field[1:])))
    else:
        raise

Submission status: Wrong Answer

Solution code:
H,W = list(map(int,input().split()))
X= [input() for _  in range(H)]
Y = list(map(list, zip(*X)))


def get(A,B):
    a=0
    b=0
    cache={}
    cache[(0,0)]=0
    def f(A,B, a_n,b_n):
        if a_n<0 or b_n<0:
            return 999999999999999999999

        if (a_n,b_n) in cache:
            return cache[a_n,b_n]

        res= min(f(A,B,a_n-1,b_n)+calc(A,B,a_n-1,b_n),f(A,B,a_n,b_n-1)+calc(A,B,a_n,b_n-1))
        cache[(a_n,b_n)]= res
        return res

    return f(A,B,H-1,H-1)
def calc(A, B, a_n, b_n):
    if a_n<0 or b_n<0:
        return 999999999999
    start= max(a_n,b_n)
    ans =0
    for i in range(start,H):
        if A[i-a_n]==B[i-b_n]:
            ans +=1
    return ans

ans=0
for i in range(W-1):
    ans += get(Y[i],Y[i+1])

print(ans)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7


def f():
    h,w = list(map(int, input().split()))
    c = [input() for _ in range(h)]
    a = [[ord(c[j][i]) for j in range(h)] for i in range(w)]

    r = 0
    for i in range(1,w):
        b = a[i]
        t = a[i-1]
        m = {}
        def g(j,k):
            if j >= h or k >= h:
                return 0
            if (j,k) in m:
                return m[(j,k)]
            gr = 0
            if j < k:
                for l in range(h-k):
                    if b[j+l] == t[k+l]:
                        gr += 1
            else:
                for l in range(h-j):
                    if b[j+l] == t[k+l]:
                        gr += 1
            m[(j,k)] = gr + min(g(j+1,k), g(j,k+1))
            return m[(j,k)]
        r += g(0,0)

    return r


print(f())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7


def f():
    h,w = list(map(int, input().split()))
    c = [input() for _ in range(h)]
    a = [[ord(c[j][i]) for j in range(h)] for i in range(w)]
    print(a)

    r = 0
    for i in range(1,w):
        b = a[i]
        t = a[i-1]
        m = {}
        def g(j,k):
            if j >= h or k >= h:
                return 0
            if (j,k) in m:
                return m[(j,k)]
            gr = 0
            if j < k:
                for l in range(h-k):
                    if b[j+l] == t[k+l]:
                        gr += 1
            else:
                for l in range(h-j):
                    if b[j+l] == t[k+l]:
                        gr += 1
            m[(j,k)] = gr + min(g(j+1,k), g(j,k+1))
            return m[(j,k)]
        r += g(0,0)

    return r


print(f())

Submission status: Wrong Answer

Solution code:
import sys

H, W = map(int, raw_input().split())
blocks = [raw_input() for i in xrange(H)]

if W != 3:
    print 0
    sys.exit()

cnt = 0

ma = [[0 for i in xrange(H + 1)] for j in xrange(H + 1)]

for i in range(H):
    for j in range(H):
        ma[i + 1][j + 1] = ma[i][j]
        if blocks[i][0] == blocks[j][1]:
            ma[i + 1][j + 1] += 1

dp = [[0 for i in xrange(H + 1)] for j in xrange(H + 1)]

for i in range(H):
    for j in range(H):
        dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j]) + ma[i + 1][j + 1]

'''
for i in range(H + 1):
    print ' '.join(map(str, dp[i]))
'''

cnt += dp[-1][-1]

ma = [[0 for i in xrange(H + 1)] for j in xrange(H + 1)]

for i in range(H):
    for j in range(H):
        ma[i + 1][j + 1] = ma[i][j]
        if blocks[i][2] == blocks[j][1]:
            ma[i + 1][j + 1] += 1

dp = [[0 for i in xrange(H + 1)] for j in xrange(H + 1)]

for i in range(H):
    for j in range(H):
        dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j]) + ma[i + 1][j + 1]

'''
for i in range(H + 1):
    print ' '.join(map(str, dp[i]))
'''

cnt += dp[-1][-1]

print cnt

Submission status: Wrong Answer

Solution code:
import sys

H, W = map(int, raw_input().split())
blocks = [raw_input() for i in xrange(H)]

if W != 3:
    print 0
    sys.exit()

cnt = 0

dp = [[0 for i in xrange(H + 1)] for j in xrange(H + 1)]

for i in range(H):
    for j in range(H):
        dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j]) + dp[i][j]
        if blocks[i][0] == blocks[j][1]:
            dp[i + 1][j + 1] += 1

cnt += dp[-1][-1]

dp = [[0 for i in xrange(H + 1)] for j in xrange(H + 1)]

for i in range(H):
    for j in range(H):
        dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j]) + dp[i][j]
        if blocks[i][2] == blocks[j][1]:
            dp[i + 1][j + 1] += 1

cnt += dp[-1][-1]

print cnt

Submission status: Time Limit Exceeded

Solution code:

"""

https://atcoder.jp/contests/code-festival-2016-qualc/tasks/codefestival_2016_qualC_d

隣り合った2列のみが関係する
隣り合った2列は実質的に自由な順番で解体できる
→あとは部分点問題を解くだけ

O(H**2)までは行ける
dp[l][r] = 左をl個、右をr個まで減らしたときのコスト最小値
→O(H**2)

推移のコストを前計算で高速に？
cost[z][t] = 左の数-右の数がzの時、右のtopからt個目までに同じ文字がいくつあるか
→O(H**2)で計算可能

"""

from sys import stdin

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

c = []
for i in range(H):
    C = list(stdin.readline())
    c.append(C)

ans = 0
cost = [ [0]*(H+1) for i in range(H*2+2) ]
dp = [[float("inf")] * (H+1) for i in range(H+1)]
for ind in range(W-1):

    for i in range(H*2+2):
        for j in range(H+1):
            cost[i][j] = 0
    for i in range(H+1):
        for j in range(H+1):
            dp[i][j] = float("inf")
    
    for z in range(-1*H,H+1):
        now = 0
        for t in range(1,H+1):
            if 0<t+z<=H and c[t-1][ind+1] == c[t+z-1][ind]:
                now += 1
            cost[z][t] = now

    dp[H][H] = 0
    for l in range(H,-1,-1):
        for r in range(H,-1,-1):

            if l > 0:
                dp[l-1][r] = min(dp[l-1][r] , dp[l][r] + cost[l-r][r])
            if r > 0:
                dp[l][r-1] = min(dp[l][r-1] , dp[l][r] + cost[l-r][r])

    ans += dp[0][0]

print (ans)

Submission status: Time Limit Exceeded

Solution code:

"""

https://atcoder.jp/contests/code-festival-2016-qualc/tasks/codefestival_2016_qualC_d

隣り合った2列のみが関係する
隣り合った2列は実質的に自由な順番で解体できる
→あとは部分点問題を解くだけ

O(H**2)までは行ける
dp[l][r] = 左をl個、右をr個まで減らしたときのコスト最小値
→O(H**2)

推移のコストを前計算で高速に？
cost[z][t] = 左の数-右の数がzの時、右のtopからt個目までに同じ文字がいくつあるか
→O(H**2)で計算可能

"""

from sys import stdin

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

c = []
for i in range(H):
    C = list(stdin.readline())
    c.append(C)

ans = 0
for ind in range(W-1):

    cost = [ [0]*(H+1) for i in range(H*2+2) ]
    for z in range(-1*H,H+1):
        now = 0
        for t in range(1,H+1):
            if 0<t+z<=H and c[t-1][ind+1] == c[t+z-1][ind]:
                now += 1
            cost[z][t] = now

    dp = [[float("inf")] * (H+1) for i in range(H+1)]
    dp[H][H] = 0
    for l in range(H,-1,-1):
        for r in range(H,-1,-1):

            if l > 0:
                dp[l-1][r] = min(dp[l-1][r] , dp[l][r] + cost[l-r][r])
            if r > 0:
                dp[l][r-1] = min(dp[l][r-1] , dp[l][r] + cost[l-r][r])

    ans += dp[0][0]

print (ans)

Submission status: Time Limit Exceeded

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

for i in range(W-1):
    for j in range(1,H+1):
        for k in range(1,H+1):
            cost=sum(c[j-l-1][i]==c[k-l-1][i+1] for l in range(0,min(j,k)))
            dp[i][j][k]=cost+min(dp[i][j-1][k],dp[i][j][k-1])

res=sum(dp[i][H][H] for i in range(W-1))

print(res)

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
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)]
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 = [[10**6 for i in range(n+1)] for j in range(n+1)]
  dp[0][0] = 0
  for i in range(n+1):
    for j in range(n+1):
      if i <= j:
        cost = ct2[j-i][n-j]
      else:
        cost = ct1[i-j][n-i]
      if i < n:
        dp[i+1][j] = min(dp[i+1][j],dp[i][j]+cost)
      if j < n:
        dp[i][j+1] = min(dp[i][j+1],dp[i][j]+cost)
  ans += dp[-1][-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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
for i in range(m-1):
  b1 = b[i]
  b2 = b[i+1]
  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)]
  for j in range(n+1):
    for k in range(n-j):
      if b1[k+j] == b2[k]:
        ct1[j][k+1] += ct1[j][k]+1
      else:
        ct1[j][k+1] += ct1[j][k]
      if b2[k+j] == b1[k]:
        ct2[j][k+1] += ct2[j][k]+1
      else:
        ct2[j][k+1] += ct2[j][k]
  dp = [[10**6 for i in range(n+1)] for j in range(n+1)]
  dp[0][0] = 0
  for i in range(n+1):
    for j in range(n+1):
      if i <= j:
        cost = ct2[j-i][n-j]
      else:
        cost = ct1[i-j][n-i]
      if i < n:
        dp[i+1][j] = min(dp[i+1][j],dp[i][j]+cost)
      if j < n:
        dp[i][j+1] = min(dp[i][j+1],dp[i][j]+cost)
  ans += dp[-1][-1]
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

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

ans = 0

for i in range(w-1):
	cost = [[0 for _ in range(h+1)] for _ in range(h+1)]
	for d in range(-h, h+1):
		if d < 0:
			d = -d
			cost[h-d][h] = 0
			for j in range(h-d-1, -1, -1):
				cost[j][j+d] = cost[j+1][j+d+1] + (c[h-j-1][i] == c[h-j-d-1][i+1])
		else:
			cost[h][h-d] = 0
			for j in range(h-d-1, -1, -1):
				cost[j+d][j] = cost[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)]
	dp[0][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] + cost[j-1][k])
			if k > 0:
				dp[j][k] = min(dp[j][k], dp[j][k-1] + cost[j][k-1])

	ans += dp[h][h]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

h, w = map(int, input().split())
c = [list(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 sys
def input():
	return sys.stdin.readline()[:-1]

h, w = map(int, input().split())
c = [list(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)