GCJ Qualificationまとめ

問題Aは、トライとか作ってやってみたものの、考察すると実は大したこと無くて、正規表現がまともに使える言語を使えばすぐだった。
要は与えられるのはマッチパターンなので、それを正規表現の形式に直して全部調べるだけ。()と[]を置換すれば正規表現として通用するので、そうやって書く。具体的には、下のPerlスクリプトで終わる。手順的にはほぼ最短だと思う。でも時間が心配だったので、JavaのTrieでちゃんと書いた奴をsubmit。後で検証したら正規表現でもすぐに終わった。というか時間が変わらない。

while(my $f = <>){
	my ($l, $m, $k) = split /\s/, $f;
	my @lines;
	for(1..$m){
		my $i = <>;
		push @lines, $i;
	}
	for my $case(1..$k){
		my $line = <>;
		$line =~ tr/\(\)/[]/;
		printf "case #%d: %d\n", $case, scalar(grep {/$line/} @lines);
	}
}

Bの問題は、書くだけ。MF-Setをやってもよしだけど、アルファベットの順序が右上から左下に順番につける、という話なので、ひとマスずつシミュレートしていけばいい。
Cの問題はDPだけど、これくらいのDPがかけない人はいないでしょう。といいながら、下4桁というのを間違えてlargeはWA。outputを一回も見ずにsubmitしたら、そりゃ間違うよなあ。

意外と難易度が高い気がしているが、去年よりはマシかも。