CodeForces Beta Round #18 E. Flag 2

Flag 2

条件から旗は２列ごとの繰り返しになるので、偶数列と奇数列の色を用いて動的計画法。色数をcとして、O(nc²(m+c²))。C++ならば充分だけど、Pythonでは間に合わない。 id:pes_magic さんにオーダーを下げる方法を教えてもらいPythonでも通った。
Pythonを練習してCodeforcesはPythonで戦おうと思ったけど、この遅さは致命的かもしれない。TopCoderのSRMでPythonが使えないのも速度が理由なんじゃなかろうか。時間制限を厳しくするとPythonが通らないし、Pythonにあわせると他の言語では遅い解法が間に合ってしまう、とか。

import itertools

n,m = map(int,raw_input().split())
flag = [raw_input() for i in range(n)]

alpha = "abcdefghijklmnopqrstuvwxyz"
col = [x[0]+x[1] for x in itertools.permutations(alpha,2)]
cn = len(col)

paint = [[0]*cn for i in range(n+1)]
prev = [[0]*cn for i in range(n+1)]

for y in range(n):

    tmp = sorted([(paint[y][c],c) for c in range(cn)])

    pe = [(m+1)/2]*256
    po = [m/2]*256
    for x in range(m):
        if x%2 == 0:
            pe[ord(flag[y][x])] -= 1
        else:
            po[ord(flag[y][x])] -= 1

    for c in range(cn):
    
        p = pe[ord(col[c][0])]+po[ord(col[c][1])]
        
        for tp,tc in tmp:
            if col[c][0] != col[tc][0] and col[c][1] != col[tc][1]:
                paint[y+1][c] = tp+p
                prev[y+1][c] = tc
                break
        
mc = 0
for c in xrange(cn):
    if paint[n][c] < paint[n][mc]:
        mc = c

print paint[n][mc]

f = []
for y in range(n,0,-1):
    f += [col[mc]]
    mc = prev[y][mc]
f.reverse()

for y in range(n):
    print (f[y]*(m/2+1))[:m]