DigitalArts プログラミングコンテスト2012 の表彰式に参加してみた
前に参加したコンテストの解説を兼ねた表彰式に参加してきました。
場所は大手町1stSQUAREにあるデジタルアーツ株式会社。
どうせまた道に迷うと思い35分前に行ったところ、一番乗りでした。
スーパー有名なAtCoder株式会社代表取締役、chokudaiさんと直に話せて感動。とても柔らかな雰囲気の気さくな方でした。
参加者は全員で18人くらい。遠いためにSkypeで参加している人もいました。参加賞はペンとマスク（なんで？？）でした。
表彰式は大きく分けてDigitalArts社の説明、chokudaiさんの問題解説、表彰、懇親会でした。
DigitalArts社はWebのフィルタリングなどに力を入れているセキュリティ会社。フィルタリングのシェアはNo.1だそうです。僕のバイト先もセキュリティ会社なのでちょっと親近感。新卒採用もしているみたいです。
chokudaiさんの解説はとても分かりやすかったです。
以下、解説概要（Aは省略）。
B - Password
違うハッシュ値を持つ文字列を作る変換方法はいろいろある。
例えば、文字列の反転をしたり、貪欲に大きい文字を取っていったり。しかし、これらの方法を単体で用いても、元の文字列と一致してしまうことがあり上手くいかない。
そこで、2つの方法を両方試して、元の文字列と違うものを採用すればよい。
C - Chokutter
単純に上からログのイベントを実行していくと、計算量が25億とかのオーダーになるので無理。ツイートをフォロー、アンフォローが起きるまで溜めておくのも、ツイートとフォローが交互に来ると失敗してしまう。
そこで、ログのイベントを最後から実行していくと、少ない計算量で計算出来る。
どちらもそんな発想思いつきません・・・orz
表彰では上位5人にアマゾンギフト券と賞状の授与が行われました。1位は有名なiwiwiさん。4位のb-inaryさんはまだコンテスト歴半年とからしいです。すごい・・・。
最後は懇親会です。僕はぼっちで終わるんだろうなーと思ってましたが、DigitalArts社員の方を始め、気さくな方が多く楽しめました。
僕はHaskell使いのsinkeyさん、Ruby使いのkyontanさんと話をしました。kyontanさんは偶然にも僕の大学の付属高校に通っており、僕の大学にもよく来るとか。しかし高校生でこれだけプログラミング出来るとは末恐ろしい・・・。
以上で表彰式レポートは終わりです。また機会があったらぜひ参加したいです！！
最後にcyokudaiさんの解説を受けて解けなかった問題B、Cを解いてみました。kyontanさんリスペクトでRubyで解きました。
B - Password
ソースコード
・文字列変換方法は「貪欲にハッシュ値の大きい文字を使い最短の文字列」と「なるべく文字数を大きくし、後ろの文字のハッシュ値が前の文字のハッシュ値以上となる文字列」を作った。これらが衝突するのは元の文字列と等しいハッシュ値の文字列が存在しない場合のみとなる。
・Rubyは文字列の扱い方がよく分からない。StringはCharacterの配列ではないらしい。Stringの作り方が分からないので、Characterの配列で文字列を作り、StringをsplitでCharacterの配列にして無理矢理比較している。ただ、getsで取ったStringは改行文字があるのでその処理が面倒。あと、Character配列をputsすると要素毎に改行される。1行で出せないものか。
今調べてみたところ、javaとかみたいにStringは +演算子とかで構成できるみたい・・・。Stringで実装すれば良かった。
