«
»

[codejam] Qualification Round 2009をやってみた 

はてなブックマーク - [codejam] Qualification Round 2009をやってみた
Bookmark this on Delicious

最近全然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ですね。とりあえずここまでは通りたいですね。頑張りましょう。

関連する記事

  • 関連する記事はありません

タグ:

この投稿は 2009年9月4日 金曜日 14:38:31 に programming, topcoder カテゴリーに公開されました。 この投稿へのコメントは RSS 2.0 フィードで購読することができます。 コメントを残すか、ご自分のサイトからトラックバックすることができます。

コメントをどうぞ