487-3279(0)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1002
電話番号（7桁）を整理する。電話番号と言っても、アルファベットやハイフォンが混ざっていて、アルファベットは対応する一桁の整数に変換しなければならない。要するに、文字列を正しい7桁の電話番号に変換し、重複する番号をカウントするという問題だ。

kurimuraさんhttp://d.hatena.ne.jp/kurimura/20060328/1143472700が3bit整数という超シュゴーなテクニックを披露している。
kurimuraさんが日記で

最初は素直に int[10000000]にしたのですがMLEでアウトになりました。

なのでメモリを節約するためにunsigned short[10000000]にしましたが、

こんどはWrong Answerで通りません。

おそらく65536個以上重複するテストがあると思われます。

と書いているように、インプットの数が100000もあり、しかも番号が7桁ということでint型だと4×9999999÷1000で、約40000kbものメモリが必要になるがメモリの制限は30000kbまでであるし、カウント数が大きい場合もあるのでunsigned shortを使ってもWAになってしまう。Acceptされた時に表示される実行時間を見る限り、テストケースは少なくとも10回以上はありそうなのでなかなか手ごわい問題だ。

以上のことから、kurimuraさんのコードはすんばらしい。もう、おしっこちびりそうなくらいスゴイのだ。私の中では、ザ・ベストアルゴリズムだ。

ところで、私も超短いコードを書いているのだが全くアプローチが違う。ゼンゼン凄くない手法だ。何かというと、膨大なテストケースの穴を探すというもの。非正攻法に近い。しかし私は穴を発見してしまった。おそらく気合を入れて縮めたら220バイトは切れると思う。

つづく・・・と思う。