最近全然TopCoderやって無いんですが、周りがcodejam, codejamと騒がしかったので参加してみました。で、結果は３問中1.5問。A:完答，B:パス, C:ラージが通らず。１問完答で通過らしいのでギリギリ通過ですか。
問題A. Alien Language
testcaseをパースする部分のコードが汚いです。(ab)cd(ef) => [‘ab’, ‘c’, ‘d’, ‘ef’]に変換するのに正規表現が使えると思うんですけど、上手く行かなかったので、愚直にパースしました。あとpythonってscanfが無いので問題文のパースがやや面倒ですね。
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import re
def match(word, test):
result = True
if len(word) != len(test):
result = False
for i in range(0, len(word)):
current = test[i]
if current.find(word[i]) < 0:
result = False
break
return result
nums = sys.stdin.readline().strip().split(' ')
L = int(nums[0])
D = int(nums[1])
N = int(nums[2])
dic = []
for i in range(0, D):
dic.append(sys.stdin.readline().strip())
tests = []
for i in range(0, N):
case = []
pattern = sys.stdin.readline().strip()
index = 0
while index < len(pattern):
c = pattern[index]
if c != '(':
case.append(c)
index += 1
else:
group = pattern[index + 1 : pattern.find(')', index + 1)]
case.append(group)
index += len(group) + 2
tests.append(case)
results = []
for test in tests:
count = 0
for word in dic:
if match(word, test):
count += 1
results.append(count)
for i in range(0, len(results)):
print "Case #%(index)d: %(count)d" % {'index':i+1, 'count':results[i]}
問題B Watersheds
面倒そうだったのでパスしました。
問題C Welcome to Code Jam
パスしようと思ったんですが、問題の導入が面白かったのでやってみました。最初に書いたのが以下です。ラージがタイムアウトしてしまいます。再帰を使ってるせいでループ数が爆発しました。
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import re
sys.stdout.flush()
def find_all(text, c):
indices = []
for i in range(0, len(text)):
if text[i] == c:
indices.append(i)
return indices
def get_combination(text, sub):
if len(sub) == 1:
return len(find_all(text, sub))
else:
total = 0
c = sub[0]
regex = re.compile("[^%(sub)s]" % {"sub" : sub})
trimed = regex.sub('', text)
indices = find_all(trimed, c)
for index in indices:
total += get_combination(trimed[index:], sub[1:])
return total
search = "welcome to code jam"
regex = re.compile('[^welcome to code jam]')
N = int(sys.stdin.readline().strip())
for i in range(0, N):
text = regex.sub('', sys.stdin.readline().strip())
count = get_combination(text, search)
print "Case #%(num)d: %(count)04d" % {"num":i+1, "count":count % 10000 }
考えているうちに寝てしまい、寝ているうちにラウンドが終了しまして、ラウンドの終了後に、他の人のコードをチラチラ見ながら、書き直したのが以下のコードです。再帰ではなく帰納を使ってるわけですが、昨日はこれが思いつきませんでした。
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
num = int(sys.stdin.readline().strip())
search = "welcome to code jam"
for t in range(1, num+1):
text = sys.stdin.readline().strip()
dp = [[0 for i in range(0, len(search))] for j in range(0, len(text))]
if text[0] == search[0]:
dp[0][0] = 1
for i in range(1, len(text)):
dp[i][0] += dp[i-1][0]
if text[i] == search[0]:
dp[i][0] += 1
for j in range(1, len(search)):
dp[i][j] += dp[i-1][j]
if search[j] == text[i]:
dp[i][j] += dp[i-1][j-1]
print "Case #%(index)d: %(count)04d" % {'index':t, 'count':dp[-1][-1] % 10000}
このコードを見ても中々全体のイメージがわかない訳ですが、これをさっと書ける人は頭の中でイメージが鮮明に湧いてるんだろうなと思います。もっと鍛錬を積まねばなりませんね。
Round1は9/12,13ですね。とりあえずここまでは通りたいですね。頑張りましょう。