A、B問題は解けたけどC問題は解けず、52位(弱い
終了後にC問題の愚直な実装を試したら当然TLEでしたorz
A: C-Filter - DigitalArts プログラミングコンテスト2012 | AtCoder
文字列マッチ、ただし*の場合には任意の文字を許す。
- 例えば、a*cとabcはマッチする
正規表現を使って解いたけど、1文字ずつ見ていっても良かったかも。
import sys import re words = sys.stdin.readline().strip().split() N = int(sys.stdin.readline().strip()) filter = [] for line in sys.stdin: filter.append(line.strip()) r = [] for f in filter: r.append(re.compile(f.replace('*', '.'))) for w in words: for m in r: result = m.match(w) length = len(w) if result != None and result.end() == length: print '*' * length, break else: print w,
B: Password - DigitalArts プログラミングコンテスト2012 | AtCoder
入力文字列に含まれる英字を数値に変換した時に、総和が等しい文字列で入力と異なるものを返す。
すでに回答している人で間違えている人が多く、例外になる条件を尽くしきれているかよくわからなかった。
適当にハードコーディングしてぐちゃぐちゃ書いたら一発で通ったが、時間かけすぎ。
import sys import re pwd = sys.stdin.readline().strip() def toChar(n): if n == 0: return '' return chr(n - 1 + ord('a')) def toHash(n): return ord(n) - ord('a') + 1 length = len(pwd) if pwd != pwd[::-1]: print pwd[::-1] elif len(pwd) == 1: if pwd != 'a': print 'a' + toChar(toHash(pwd) - 1) else: print 'NO' elif len(pwd) == 20: if pwd == 'zzzzzzzzzzzzzzzzzzzz': print 'NO' elif pwd == 'aaaaaaaaaaaaaaaaaaaa': print 'aaaaaaaaaaaaaaaaaab' elif pwd != 'zzzzzzzzzzzzzzzzzzzz': for i in xrange(length): if pwd[i] != 'a': start = i for j in xrange(length): if i == j: continue if pwd[j] != 'z': end = j temp = list(pwd) temp[start] = toChar(toHash(pwd[start]) - 1) temp[end] = toChar(toHash(pwd[end]) + 1) print ''.join(temp) else: s = 0 for c in pwd: s += toHash(c) for i in xrange(length): start = i temp = list(pwd) temp[start] = toChar(toHash(pwd[start]) - 1) cand = ''.join(temp) suc = False for j in xrange(length): if j == start: continue in_temp = list(pwd) in_temp[start] = toChar(toHash(pwd[start]) - 1) if in_temp[j] != 'z': in_temp[j] = toChar(toHash(pwd[j]) + 1) if ''.join(in_temp) != pwd: suc = True print ''.join(in_temp) break if suc: break if cand + 'a' != pwd: print cand + 'a' break if (cand + 'a')[::-1] != pwd: print (cand + 'a')[::-1] break if 'a' + cand != pwd: print 'a' + cand break if ('a' + cand)[::-1] != pwd: print ('a' + cand)[::-1] break
愚直に実装したらTLE。
Twitterで見かけたコードを見るに、現在までのフォロー情報とかをいちいち覚えてなくてもフォローとアンフォローの時にまとめて計算すれば解けるみたいですね。
以下は素朴な実装(TLE)
import sys import re import collections N, M, K = map(int, sys.stdin.readline().strip().split()) count = collections.Counter() link = collections.defaultdict(set) for i in xrange(1, N + 1): link[i].add(i) for line in sys.stdin: l = line.strip() if l[0] == 't': a, b = l.split() b = int(b) for i in link[b]: count[i] += 1 # print 'add', i elif l[0] == 'f': a, b, c = l.split() b = int(b) c = int(c) link[b].add(c) link[c].add(b) # print 'follow', b, c elif l[0] == 'u': a, b, c = l.split() b = int(b) c = int(c) link[b].remove(c) link[c].remove(b) # print 'unfollow', b, c if len(count) < K: print 0 else: result = count.most_common() print result[K - 1][1]