Google Code Jam Japan 2011 Final C: ワイルドカード

GCJ

問題概要

文字列A,B(長さ<=(small ? 10 : 50))が与えられるので、AにマッチしてBにマッチしない最小の長さのパターンを返す問題。長さ最小のが複数あれば*の少なさ、それも一緒なら辞書順最小のものを返す。

考えたこと

  • (Bを提出した時点で結構順位が高くて、このsmallを出したら賞金圏内だったので必死になった)。
  • smallはどう見ても全探索。Aのどの文字を*に対応させるか2^10通り試してやればよい。隣合う*は一つにまとめる。
  • で、作ったパターンがBにマッチしてるかどうか確かめればよい。
  • …はて、どうやってマッチしてるか確かめればいいんだろうか。
  • 正規表現使えというアレですか。DかpythonかJavaかgrepか…。
  • 一番リファレンスが見つかりそうなpythonにしよう。
  • 入力ってraw_input()でよかったっけ、とかstringにcountメソッドあるといいなあ、とか手探りで実装。
  • 正規表現のコンパイルで怒られる。何でだろう…。
  • そうか*じゃなくて.*か。そうだったそうだった。
  • sample通ったので提出。不正解。何故だ…？
  • 結局よくわからずに終戦。後で正解データ持ってきてdiffとってみたら完全一致しないといけないところ部分一致のを通してるぽかった。
  • 自分文字列処理弱いなあ。あれあんまりワクワクしないんだよなあ。

practiceで通ったコード

計算量はO(2^|A| * ?)。?の部分は正規表現のコンパイルとマッチングに必要な分。正規表現のコンパイルってだいたい指数だった様な(NDFAに対応するDFAつくるヤツしかしらない)。

import re

def solve(a, b):
	L = len(a)
	ans = a
	for bit in range(1<<L):

		cur = ''
		tmp = ''
		reg = ''
		for j in range(L):
			if( ((bit>>j)&1) == 0):
				tmp = tmp + '*'
			else:
				tmp = tmp + a[j]
		#print(tmp)
		for j in range(L):
			if(tmp[j] != '*'):
				cur = cur + tmp[j]
				reg = reg + tmp[j]
			elif(j == L-1 or tmp[j+1] != '*'):
				cur = cur + tmp[j]
				reg = reg + '.*'
		#print(cur)
		pat = re.compile(reg)
		if( pat.match(b) is not None and pat.match(b).end() == len(b) ):
			continue
		if(len(ans) > len(cur)):
			ans = cur
		elif(len(ans) == len(cur) and ans.count('*') > cur.count('*')):
			ans = cur
		elif(len(ans) == len(cur) and ans.count('*') == cur.count('*') and ans > cur):
			ans = cur
	return ans

T = (int)(raw_input())

for i in range(T):
	a = raw_input()
	b = raw_input()
	print('Case #%d: %s' % (i+1, solve(a,b)))