442th, 95.3pts, +0/-0 challenge
Volatility: 347->324
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"