みごとに醜態晒した

おわた。マジでおわた。あと1分でCがLargeまで解けていたのにというのが、本気で悔しい。
言い訳をすると、ソース中に２ヶ所間違いがあって、二つの間違いが相殺してN=1の時には正しい答えを出すようなプログラムを書いてたせいで、WA連発してしまった。
俺、順列組み合わせを小学生からやり直した方がいいかもしれん。あと、高校の数列。

GCJ qualification round problem A analysis

ってことで、Problem Aの周りの人たち(勝手にfriendに入れた人たち)のソースをちょろちょろ読んだ結果を報告。
正規表現で()と[]を変換すりゃいいよねってのは、書いたとおりなのだけど、正規表現でやってるひとは周りの人たちで30%くらいかなあ。k.inaba氏はJava Scriptでやってた。kogitsune氏はPerlで、ショートコーディングをやってた。118byte。ただ、最初のforを後置にするだけであと2byte減ったけど・・・？
LayCurse氏は、C。下の二行のマクロが特徴的。

#define REP(i,a,b) for(i=a;i

確かに、ループをまわすのになんでiを3回も書かなきゃいけないのかとは思うし、

for(j = 0; j

見たいなよくある間違いも無くなるな。ちなみにLayCurse氏とmayah氏、wata氏、iwi氏あたりは、言語を除いてほぼ同じアルゴリズム。手法としては、パターンに含まれる文字をフラグとして用いる。例えば、(ac)ってパターンに対しては

chk['a']=1
chk['c']=1

見たいな感じで保持。26種類しか文字が無いからって、ビットで管理している人はいなくて、みんなintで管理してたと思う。枝狩りとして、マッチが失敗したときのbreak処理を入れてるのはこの中だとmayah氏だけかな。時間的にはほとんど問題ないので関係ないけど。あと、LayCurse氏だけはパターンの方を読みながら、1文字ごとにマッチングチェックをしていた。
で、誰も・・・誰もTrieなんて作ってねえようわあああぁぁぁぁぁぁん。

本末転倒

id:hitode909:20090904:1251991887
ブックマーク上位にあったので見たのだけど、

ファイルの編集くらいはできるようになったと思う．
Vimperatorと同じだと思えば容易に覚えられそう．

叩く気はサラサラないのだけど、vim使わないのになんでまたVimperatorなんて入れてるんだろう？

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したら、そりゃ間違うよなあ。

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

先週末あれこれ

金曜日は某社のイベントで、ひどい格好をした。このために費やした時間はかなりものだったのだけれど、それはさておき社外にあの写真が流出しないことを祈る。

土曜日は、LLTV。いろいろ思うところはあった。最初の朝から生TVとやらで質問してみたりした。相変わらずの俺のキモさに悶えるといいと思う。これを並列に並べる事には、非常に抵抗はあるが、金曜日の某社のイベントでの様々なやりくりを思い出してみるに、このイベントの実施の大変さを垣間見た気がする。毎年本当にありがとうございます。ただ、企画としてはもうちょっと濃い人向けのものがあるとうれしいと思う。

日曜日は、選挙行って昼からOcaml Meeting。ゴルフとかさっぱりやってなかったわけだけど、なるほどなあと思ったのは、Ocamlのゴルフのソースは比較的読みやすい。というのも、さすがに型安全なだけあって未定義なソースとか実装依存なんてことは無い。その分ゴルフには不向きなのだけど。その後飲み会にも顔を出す。まあ、なんというか、居心地がいい。
日曜の帰りに、S社に行ったG氏に新宿で偶然出くわす。ISの飲み会もそのうちやりましょう。

そんな感じ。