唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

DigitalArts プログラミングコンテスト2012 に参加した

python atcoder

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]