TopCoder SRM 649 Div1 o-- 1322->1283

442th, 95.3pts, +0/-0 challenge
Volatility: 347->324

• SRM 649 - Togetterまとめ

250: Decipherability

文字列\(s\)と数値\(K\)が与えられる(\(1 \le K \le 50\)、文字列の長さは\(K\)以下)
\(s\)からちょうど\(K\)文字削除した文字列を考える
その文字列に含まれる文字を見て元の文字列での位置がわからなくなるような削除の仕方があるかどうかを答える

一番近い同じ文字の距離が\(K\)以上かどうかを答えればよいらしい

以下は本番で混乱しながらゆっくり書いた、何故か最長共通部分列を計算している汚いコード
制約が緩かったのでなんとか通ったorz

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

Z = [[0] * (60) for j in xrange(60)]
def lcs(s1, s2):
    table = Z[::]
    m = -1
    for i in xrange(len(s1)):
        for j in xrange(len(s2)):
            if s1[i] == s2[j]:
                table[i + 1][j + 1] = table[i][j] + 1
                if table[i + 1][j + 1] > m:
                    m = table[i + 1][j + 1]
            else:
                if table[i + 1][j] >= table[i][j + 1]:
                    table[i + 1][j + 1] = table[i + 1][j]
                else:
                    table[i + 1][j + 1] = table[i][j + 1]
    return m


class Decipherability:
    def check(self, s, K):
        L = len(s)
        print
        for i in xrange(0, L):
            for j in xrange(i + 1, L):
                for k in xrange(j + 1, L + 1):
                    head = s[i:j]
                    tail = s[j:k]
                    ll = lcs(head, tail)
                    if k - i - ll == K and ll > 0:
                        break
                else:
                    continue
                break
            else:
                continue
            break
        else:
            return "Certain"
        return "Uncertain"