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:
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), 100, 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(i, idx)
        # print(dp)
    return dp[H][H]


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

Submission status: Wrong Answer

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

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

if w != 3:
    exit()


c = ['A','B','C']
for i in range(h):
    inp = input()
    c.append(inp[0])
    c.append(inp[1])
    c.append(inp[2])

h += 1

dp = [10**6]*(h**3)

dp[0] = 0
h2 = h**2

ab = [0]*(h2)
bc = [0]*(h2)


for i in range(1,h):
    for j in range(1,h):
        if c[i*3] == c[j*3+1]:
            ab[i*h+j] = ab[(i-1)*h+j-1] + 1
        else:
            ab[i*h+j] = ab[(i-1)*h+j-1]
        if c[i*3+1] == c[j*2+2]:
            bc[i*h+j] = bc[(i-1)*h+j-1] + 1
        else:
            bc[i*h+j] = bc[(i-1)*h+j-1]

for i in range(h):
    for j in range(h):
        for k in range(h):
            if i != 0 and dp[i*h2+j*h+k] > dp[(i-1)*h2+j*h+k] + ab[i*h+j]:
                dp[i*h2+j*h+k] = dp[(i-1)*h2+j*h+k] + ab[i*h+j]
            if j != 0 and dp[i*h2+j*h+k] > dp[i*h2+(j-1)*h+k] + ab[i*h+j] + bc[j*h+k]:
                dp[i*h2+j*h+k] = dp[i*h2+(j-1)*h+k] + ab[i*h+j] + bc[j*h+k]
            if k != 0 and dp[i*h2+j*h+k] > dp[i*h2+j*h+k-1] + bc[j*h+k]:
                dp[i*h2+j*h+k] = dp[i*h2+j*h+k-1] + bc[j*h+k]

print(dp[-1])

Submission status: Wrong Answer

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[x][y] += 1
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 or y == 0:
                    continue
                else:
                    if c[x-1][j] == c[y-1][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: Wrong Answer

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

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

if w != 3:
    exit()

c = []

c.append(["A","B","C"])
for i in range(h):
    c.append(list(input())[:3])


h += 1

dp = [10**6]*(h**3)

dp[0] = 0
h2 = h**2

ab = [0]*(h2)
bc = [0]*(h2)

for i in range(h):
    if c[i][0] == c[0][1]:
        ab[i*h] = 1
    if c[i][1] == c[0][0]:
        ab[i] = 1
    if c[i][1] == c[0][2]:
        bc[i*h] = 1
    if c[i][2] == c[0][1]:
        bc[i] = 1

for i in range(1,h):
    for j in range(1,h):
        if c[i][0] == c[j][1]:
            ab[i*h+j] = ab[(i-1)*h+j-1] + 1
        else:
            ab[i*h+j] = ab[(i-1)*h+j-1]
        if c[i][1] == c[j][2]:
            bc[i*h+j] = bc[(i-1)*h+j-1] + 1
        else:
            bc[i*h+j] = bc[(i-1)*h+j-1]

for i in range(h):
    for j in range(h):
        for k in range(h):
            if i != 0 and dp[i*h2+j*h+k] > dp[(i-1)*h2+j*h+k] + ab[i*h+j]:
                dp[i*h2+j*h+k] = dp[(i-1)*h2+j*h+k] + ab[i*h+j]
            if j != 0 and dp[i*h2+j*h+k] > dp[i*h2+(j-1)*h+k] + ab[i*h+j] + bc[j*h+k]:
                dp[i*h2+j*h+k] = dp[i*h2+(j-1)*h+k] + ab[i*h+j] + bc[j*h+k]
            if k != 0 and dp[i*h2+j*h+k] > dp[i*h2+j*h+k-1] + bc[j*h+k]:
                dp[i*h2+j*h+k] = dp[i*h2+j*h+k-1] + bc[j*h+k]

print(dp[-1])

Submission status: Wrong Answer

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

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

if w != 3:
    exit()

c = []
for i in range(h):
    c.append(list(input())[:3])

c.append(["A","B","C"])
h += 1

dp = [10**6]*(h**3)

dp[0] = 0
h2 = h**2

ab = [0]*(h2)
bc = [0]*(h2)

for i in range(h):
    if c[i][0] == c[0][1]:
        ab[i*h] = 1
    if c[i][1] == c[0][0]:
        ab[i] = 1
    if c[i][1] == c[0][2]:
        bc[i*h] = 1
    if c[i][2] == c[0][1]:
        bc[i] = 1

for i in range(1,h):
    for j in range(1,h):
        if c[i][0] == c[j][1]:
            ab[i*h+j] = ab[(i-1)*h+j-1] + 1
        else:
            ab[i*h+j] = ab[(i-1)*h+j-1]
        if c[i][1] == c[j][2]:
            bc[i*h+j] = bc[(i-1)*h+j-1] + 1
        else:
            bc[i*h+j] = bc[(i-1)*h+j-1]

for i in range(h):
    for j in range(h):
        for k in range(h):
            if i != 0 and dp[i*h2+j*h+k] > dp[(i-1)*h2+j*h+k] + ab[i*h+j]:
                dp[i*h2+j*h+k] = dp[(i-1)*h2+j*h+k] + ab[i*h+j]
            if j != 0 and dp[i*h2+j*h+k] > dp[i*h2+(j-1)*h+k] + ab[i*h+j] + bc[j*h+k]:
                dp[i*h2+j*h+k] = dp[i*h2+(j-1)*h+k] + ab[i*h+j] + bc[j*h+k]
            if k != 0 and dp[i*h2+j*h+k] > dp[i*h2+j*h+k-1] + bc[j*h+k]:
                dp[i*h2+j*h+k] = dp[i*h2+j*h+k-1] + bc[j*h+k]

print(dp[-1])

Submission status: Wrong Answer

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

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

if w != 3:
    exit()

c = []
for i in range(h):
    c.append(list(input())[:3])

dp = [10**6]*(h**3)

dp[0] = 0
h2 = h**2

ab = [0]*(h2)
bc = [0]*(h2)

for i in range(h):
    if c[i][0] == c[0][1]:
        ab[i*h] = 1
    if c[i][1] == c[0][0]:
        ab[i] = 1
    if c[i][1] == c[0][2]:
        bc[i*h] = 1
    if c[i][2] == c[0][1]:
        bc[i] = 1

for i in range(1,h):
    for j in range(1,h):
        if c[i][0] == c[j][1]:
            ab[i*h+j] = ab[(i-1)*h+j-1] + 1
        else:
            ab[i*h+j] = ab[(i-1)*h+j-1]
        if c[i][1] == c[j][2]:
            bc[i*h+j] = bc[(i-1)*h+j-1] + 1
        else:
            bc[i*h+j] = bc[(i-1)*h+j-1]
"""
if c[0][0] == c[0][1]:
    dp[0] += 1
if c[0][1] == c[0][2]:
    dp[0] += 1
"""
for i in range(h):
    for j in range(h):
        for k in range(h):
            if i != 0 and dp[i*h2+j*h+k] > dp[(i-1)*h2+j*h+k] + ab[i*h+j]:
                dp[i*h2+j*h+k] = dp[(i-1)*h2+j*h+k] + ab[i*h+j]
            if j != 0 and dp[i*h2+j*h+k] > dp[i*h2+(j-1)*h+k] + ab[i*h+j] + bc[j*h+k]:
                dp[i*h2+j*h+k] = dp[i*h2+(j-1)*h+k] + ab[i*h+j] + bc[j*h+k]
            if k != 0 and dp[i*h2+j*h+k] > dp[i*h2+j*h+k-1] + bc[j*h+k]:
                dp[i*h2+j*h+k] = dp[i*h2+j*h+k-1] + bc[j*h+k]

print(dp[-1])

Submission status: Wrong Answer

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

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

if w != 3:
    exit()

c = []
for i in range(h):
    c.append(list(input()))

dp = [[[10**6]*h for _ in [0]*h] for j in range(h)]

dp[0][0][0] = 0

ab = [[0]*(h) for i in range(h)]
bc = [[0]*(h) for i in range(h)]

for i in range(h):
    if c[i][0] == c[0][1]:
        ab[i][0] = 1
    if c[i][1] == c[0][0]:
        ab[0][i] = 1
    if c[i][1] == c[0][2]:
        bc[i][0] = 1
    if c[i][2] == c[0][1]:
        bc[0][i] = 1

for i in range(1,h):
    for j in range(1,h):
        if c[i][0] == c[j][1]:
            ab[i][j] = ab[i-1][j-1] + 1
        else:
            ab[i][j] = ab[i-1][j-1]
        if c[i][1] == c[j][2]:
            bc[i][j] = bc[i-1][j-1] + 1
        else:
            bc[i][j] = bc[i-1][j-1]
for i in range(h):
    for j in range(h):
        for k in range(h):
            if i != 0 and dp[i][j][k] > dp[i-1][j][k] + ab[i][j]:
                dp[i][j][k] = dp[i-1][j][k] + ab[i][j]
            if j != 0 and dp[i][j][k] > dp[i][j-1][k] + ab[i][j] + bc[j][k]:
                dp[i][j][k] = dp[i][j-1][k] + ab[i][j] + bc[j][k]
            if k != 0 and dp[i][j][k] > dp[i][j][k-1] + bc[j][k]:
                dp[i][j][k] = dp[i][j][k-1] + bc[j][k]

print(dp[-1][-1][-1])

Submission status: Wrong Answer

Solution code:
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
C1 = C_T[0]
for C2 in 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)

Submission status: Wrong Answer

Solution code:
# 計測
def accumulate(idx1, idx2):
    res = [0]
    c = 0
    for i in range(H - max(idx1, idx2)):
        if C1[i+idx1] == C2[i+idx2]:
            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(0, 0);  z1.reverse()
    Z1.append(z1)
    Z2.append([])
    for j in range(1, H+1):
        z1 = accumulate(0, j);  z1.reverse();  Z1.append(z1)
        z2 = accumulate(j, 0);  z2.reverse();  Z2.append(z2)

Submission status: Wrong Answer

Solution code:
# 計測
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)
        z2 = accumulate(C1[j:], C2);  z2.reverse();  Z2.append(z2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# 計測
from itertools import accumulate
inf = 2 * 10**9
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = [[ord(c) for c in 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 = list(accumulate([int(c1==c2) for c1, c2 in zip(C1, C2)]))
    z1.reverse();  z1.append(0)
    Z1.append(z1)
    Z2.append([])
    for j in range(1, H+1):
        z1 = list(accumulate([int(c1==c2) for c1, c2 in zip(C1, C2[j:])]))
        z1.reverse();  z1.append(0);  Z1.append(z1)
        z2 = list(accumulate([int(c1==c2) for c1, c2 in zip(C1[j:], C2)]))
        z2.reverse();  z2.append(0);  Z2.append(z2)
    continue
    # 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: Wrong Answer

Solution code:
# 計測
from itertools import accumulate
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 = list(accumulate([int(c1==c2) for c1, c2 in zip(C1, C2)]))
    z1.reverse();  z1.append(0)
    Z1.append(z1)
    Z2.append([])
    for j in range(1, H+1):
        z1 = list(accumulate([int(c1==c2) for c1, c2 in zip(C1, C2[j:])]))
        z1.reverse();  z1.append(0);  Z1.append(z1)
        z2 = list(accumulate([int(c1==c2) for c1, c2 in zip(C1[j:], C2)]))
        z2.reverse();  z2.append(0);  Z2.append(z2)
    continue

Submission status: Wrong Answer

Solution code:
# 計測
from itertools import accumulate
inf = 2 * 10**9
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    z1 = list(accumulate([int(c1==c2) for c1, c2 in zip(C1, C2)]))
    z1.reverse();  z1.append(0)
    Z1.append(z1)
    Z2.append([])
    for j in range(1, H+1):
        z1 = list(accumulate([int(c1==c2) for c1, c2 in zip(C1, C2[j:])]))
        z1.reverse();  z1.append(0);  Z1.append(z1)
        z2 = list(accumulate([int(c1==c2) for c1, c2 in zip(C1[j:], C2)]))
        z2.reverse();  z2.append(0);  Z2.append(z2)
    continue
    # 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: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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):
    for l in range(H):
        dp_1[:,l+r+2,r+1] = (C[:-1][:,l] == C[1:][:,r])

Submission status: Wrong Answer

Solution code:
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+H+1),dtype=np.int64)
R = np.arange(1,H+1)[None,:] + np.zeros(H,dtype=np.int32)
L = np.arange(1,H+1)[:,None] + np.zeros(H,dtype=np.int32)
dp_1[:,R-L+H,R+L] = (C[:-1][:,:,None] == C[1:][:,None,:])
np.cumsum(dp_1,out=dp_1,axis=2)

Submission status: Wrong Answer

Solution code:
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+H+1),dtype=np.int64)
L = np.arange(1,H+1)
R = np.arange(1,H+1)
(C[:-1][:,:,None] == C[1:][:,None,:])

Submission status: Wrong Answer

Solution code:
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+H+1),dtype=np.int64)
L = np.arange(1,H+1)
R = np.arange(1,H+1)
dp_1[:,R[None,:]-L[:,None]+H,R[None,:]+L[:,None]] = (C[:-1][:,:,None] == C[1:][:,None,:])
np.cumsum(dp_1,out=dp_1,axis=2)

Submission status: Wrong Answer

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

equal = np.empty((W-1,H,H),dtype=np.bool)
for n in range(W-1):
    equal[n,:,:] = (C[n][:,None] == C[n+1][None,:])
dp_1 = np.zeros((W-1,H+H+1,H+H+1),dtype=np.int64)
L = np.arange(1,H+1)
R = np.arange(1,H+1)

Submission status: Wrong Answer

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

equal = np.empty((W-1,H,H),dtype=np.bool)
for n in range(W-1):
    equal[n,:,:] = (C[n][:,None] == C[n+1][None,:])
dp_1 = np.zeros((W-1,H+H+1,H+H+1),dtype=np.int64)
L = np.arange(1,H+1)
R = np.arange(1,H+1)
dp_1[:,R[None,:]-L[:,None]+H,R[None,:]+L[:,None]] = equal
np.cumsum(dp_1,out=dp_1,axis=2)

Submission status: Wrong Answer

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

equal = np.empty((W-1,H,H),dtype=np.bool)
for n in range(W-1):
    equal[n,:,:] = (C[:,n][:,None] == C[:,n+1][None,:])

Submission status: Wrong Answer

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

import numpy as np

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

H,W = map(int,input().split())
C = np.array([list(input().rstrip()) for _ in range(H)])

equal = np.empty((H,H,W-1),dtype=np.bool)
for n in range(W-1):
    equal[:,:,n] = (C[:,n][:,None] == C[:,n+1][None,:])

Submission status: Wrong Answer

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

import numpy as np

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

H,W = map(int,input().split())
C = np.array([list(input().rstrip()) for _ in range(H)])

equal = np.empty((H,H,W-1),dtype=np.bool)
for n in range(W-1):
    equal[:,:,n] = (C[:,n][:,None] == C[:,n+1][None,:])
dp_1 = np.zeros((H+H+1,H+H+1,W-1),dtype=np.int64)
L = np.arange(1,H+1)
R = np.arange(1,H+1)
dp_1[R[None,:]-L[:,None]+H,R[None,:]+L[:,None],:] = equal
np.cumsum(dp_1,out=dp_1,axis=1)

Submission status: Wrong Answer

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

import numpy as np

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

H,W = map(int,input().split())
C = np.array([list(input().rstrip()) for _ in range(H)])

def score_between(col1,col2):
    equal = (col1[:,None] == col2[None,:])
    dp_1 = np.zeros((H+H+1,H+H+1),dtype=np.int64)
    return 0
    L = np.arange(1,H+1)
    R = np.arange(1,H+1)
    dp_1[R[None,:]-L[:,None]+H,R[None,:]+L[:,None]] = equal
    np.cumsum(dp_1,out=dp_1,axis=1)
    INF = 10**18
    # R-L+H -> min cost
    dp = np.full(H+H+1,INF,dtype=np.int64)
    dp[H] = 0
    for n in range(1,H+H+1):
        # n個目を置く
        prev = dp
        dp = np.full(H+H+1,INF,dtype=np.int64)
        dp[1:] = np.minimum(dp[1:],prev[:-1])
        dp[:-1] = np.minimum(dp[:-1],prev[1:])
        dp += dp_1[:,n]
    return dp[H]

answer = sum(score_between(C[:,n],C[:,n+1]) for n in range(W-1))
print(answer)

Submission status: Wrong Answer

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

import numpy as np

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

H,W = map(int,input().split())
C = np.array([list(input().rstrip()) for _ in range(H)])

def score_between(col1,col2):
    equal = (col1[:,None] == col2[None,:])
    dp_1 = np.zeros((H+H+1,H+H+1),dtype=np.int32)
    L = np.arange(1,H+1)
    R = np.arange(1,H+1)
    dp_1[R[None,:]-L[:,None]+H,R[None,:]+L[:,None]] = equal
    return 0

answer = sum(score_between(C[:,n],C[:,n+1]) for n in range(W-1))
print(answer)

Submission status: Wrong Answer

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

import numpy as np

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

H,W = map(int,input().split())
C = np.array([list(input().rstrip()) for _ in range(H)])

def score_between(col1,col2):
    equal = (col1[:,None] == col2[None,:])
    dp_1 = np.zeros((H+H+1,H+H+1),dtype=np.int64)
    L = np.arange(1,H+1)
    R = np.arange(1,H+1)
    dp_1[R[None,:]-L[:,None]+H,R[None,:]+L[:,None]] = equal
    return 0
    np.cumsum(dp_1,out=dp_1,axis=1)
    INF = 10**18
    # R-L+H -> min cost
    dp = np.full(H+H+1,INF,dtype=np.int64)
    dp[H] = 0
    for n in range(1,H+H+1):
        # n個目を置く
        prev = dp
        dp = np.full(H+H+1,INF,dtype=np.int64)
        dp[1:] = np.minimum(dp[1:],prev[:-1])
        dp[:-1] = np.minimum(dp[:-1],prev[1:])
        dp += dp_1[:,n]
    return dp[H]

answer = sum(score_between(C[:,n],C[:,n+1]) for n in range(W-1))
print(answer)

Submission status: Wrong Answer

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

import numpy as np

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

H,W = map(int,input().split())
C = np.array([list(input().rstrip()) for _ in range(H)])

def score_between(col1,col2):
    equal = (col1[:,None] == col2[None,:])
    dp_1 = np.zeros((H+H+1,H+H+1),dtype=np.int64)
    L = np.arange(1,H+1)
    R = np.arange(1,H+1)
    dp_1[R[None,:]-L[:,None]+H,R[None,:]+L[:,None]] = equal
    np.cumsum(dp_1,out=dp_1,axis=1)
    return 0
    INF = 10**18
    # R-L+H -> min cost
    dp = np.full(H+H+1,INF,dtype=np.int64)
    dp[H] = 0
    for n in range(1,H+H+1):
        # n個目を置く
        prev = dp
        dp = np.full(H+H+1,INF,dtype=np.int64)
        dp[1:] = np.minimum(dp[1:],prev[:-1])
        dp[:-1] = np.minimum(dp[:-1],prev[1:])
        dp += dp_1[:,n]
    return dp[H]

answer = sum(score_between(C[:,n],C[:,n+1]) for n in range(W-1))
print(answer)

Submission status: Wrong Answer

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

import numpy as np

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

H,W = map(int,input().split())
C = np.array([list(input().rstrip()) for _ in range(H)])

def score_between(col1,col2):
    col1 = np.concatenate([['*'],col1])
    col2 = np.concatenate([['#'],col2])
    equal = (col1[:,None] == col2[None,:])
    dp_1 = np.zeros((H+H+1,H+H+1),dtype=np.int64)
    L = np.arange(H+1)
    R = np.arange(H+1)
    dp_1[R[None,:]-L[:,None]+H,R[None,:]+L[:,None]] = equal
    np.cumsum(dp_1,out=dp_1,axis=1)
    return 0
    INF = 10**18
    # R-L+H -> min cost
    dp = np.full(H+H+1,INF,dtype=np.int64)
    dp[H] = 0
    for n in range(1,H+H+1):
        # n個目を置く
        prev = dp
        dp = np.full(H+H+1,INF,dtype=np.int64)
        dp[1:] = np.minimum(dp[1:],prev[:-1])
        dp[:-1] = np.minimum(dp[:-1],prev[1:])
        dp += dp_1[:,n]
    return dp[H]

answer = sum(score_between(C[:,n],C[:,n+1]) for n in range(W-1))
print(answer)

Submission status: Wrong Answer

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

import numpy as np

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

H,W = map(int,input().split())
C = np.array([list(input().rstrip()) for _ in range(H)])

def score_between(col1,col2):
    col1 = np.concatenate([['*'],col1])
    col2 = np.concatenate([['#'],col2])
    # まず、その瞬間のスコアを求める
    # L+R,R-L+H
    dp_1 = np.zeros((H+H+1,H+H+1),dtype=np.int64)
    for n in range(H+H+1):
        # R-L+H=n
        if n <= H:
            R0,L0 = 1,H-n+1
            R1,L1 = n,H
        else:
            L0,R0 = 1,n-H+1
            L1,R1 = H+H-n,H
        dp_1[n][L0+R0:L1+R1+2:2] = (col1[L0:L1+1] == col2[R0:R1+1])
    np.cumsum(dp_1,out=dp_1,axis=1)
    return 0
  
answer = sum(score_between(C[:,n],C[:,n+1]) for n in range(W-1))
print(answer)

Submission status: Wrong Answer

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

import numpy as np

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

H,W = map(int,input().split())
C = np.array([list(input().rstrip()) for _ in range(H)])

def score_between(col1,col2):
    col1 = np.concatenate([['*'],col1])
    col2 = np.concatenate([['#'],col2])
    # まず、その瞬間のスコアを求める
    # L+R,R-L+H
    dp_1 = np.zeros((H+H+1,H+H+1),dtype=np.int64)
    for n in range(H+H+1):
        # R-L+H=n
        if n <= H:
            R0,L0 = 1,H-n+1
            R1,L1 = n,H
        else:
            L0,R0 = 1,n-H+1
            L1,R1 = H+H-n,H
        dp_1[n][L0+R0:L1+R1+2:2] = (col1[L0:L1+1] == col2[R0:R1+1])
        np.cumsum(dp_1[n],out=dp_1[n])
    return 0
    INF = 10**18
    # R-L+H -> min cost
    dp = np.full(H+H+1,INF,dtype=np.int64)
    dp[H] = 0
    for n in range(1,H+H+1):
        # n個目を置く
        prev = dp
        dp = np.full(H+H+1,INF,dtype=np.int64)
        dp[1:] = np.minimum(dp[1:],prev[:-1])
        dp[:-1] = np.minimum(dp[:-1],prev[1:])
        dp += dp_1[:,n]
    return dp[H]

answer = sum(score_between(C[:,n],C[:,n+1]) for n in range(W-1))
print(answer)