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したら、そりゃ間違うよなあ。
意外と難易度が高い気がしているが、去年よりはマシかも。