DevFestに興味を持つプログラマにとってはあまりに設問が簡単すぎたのか、締め切り前に答えをblogに雄雄しく書いちゃうちょっと自己顕示欲に比して要件定義の苦手そうな方がいたことで台無しになったのか、どっちが原因かは知りませんが後からAndroid開発者優遇問題とChromeExtention開発者優遇問題が追加されたわけですが、なんだかなー。
Issue Tracker、Hackathon、Android、Chrome Extensions、以外は満点で当たり前のはずなので、まー結果的に俺にも多少チャンスがめぐってきたかなと思わんでもないわけだったりします。といってもプログラム問題は満点デフォでこの4つのうち1つ以上書けた人でも400人は余裕で超えそう。
で、「暗号通信」と「漢字変換サーバ」はあまりに簡単すぎてネタにはしにくいのですが、「パッチワーク」は中々の良問で平均的な開発会社なら入社試験でちょっと上等なFizzBuzzとして使えそうなもの。といっても回答時間が得点に影響しない上に時間も長く取られているのでやっぱり満点がデフォなわけですが。
問題
パッチワーク
ここに “A” または “B” という文字のみを含む 600 桁、600 行のテキストがあります。これを 600 x 600 の升目状に並べ、上下左右に同じ文字がある部分をつながっているとみなします。
まず、最も多くの文字がつながっている領域をすべて “_” で塗りつぶしてください。 最も多くの文字がつながっている領域が複数存在するならば、それらすべての領域を “_”で塗りつぶすこととします。
そして、各行ごとに “_” が何個含まれているかを数え、それらの数値を改行区切りのテキスト（600 行）として答えてください。
以下の例1を見てください。この入力には単一の文字4つでつながった領域が3箇所あります。これらすべてが「最も多くの文字がつながっている領域」なので、全て”_”で塗りつぶし、その数を数えています。
例1:
入力
ABAAB
BABAA
BAABB
ABABB
BABAA
塗りつぶしたところ.
AB__B
B_B__
B____
AB___
BABAA
答え
2
3
4
3
0例2:
入力
ABBABBABBB
BAABAAAAAB
AAAAABBAAB
ABBABABAAB
BABBABAAAB
ABBBBAABAA
AAABBBAABA
ABABABAABB
AAABBBABBA
BABAABAAAB
塗りつぶしたところ.
ABBABB_BBB
B__B_____B
_____BB__B
_BB_BAB__B
BABBAB___B
ABBBB__B__
AAABBB__B_
ABABAB__BB
AAABBB_BBA
BABAAB___B
答え
1
7
7
4
3
4
3
2
1
3
まあ600×600のぷよぷよ。
C++で愚直に実装したみたもの
オリジナルのデータ、各セルに対して検査済みかどうかを示すフラグ、現在調査中のうち最も多くリンクしたセル群のリンク数と座標のリスト、があって、未検査のセルから再帰的にマークを付けていく、という理屈をそのまま実装したもの。
これでAthlonの2GくらいのCPUで600×600の実行時間が30msくらい。
LLで書いても全く同じロジックで数秒以内に終わるはず。LLで書いて強烈に遅くなる場合はメモリ確保(データの持ち方)が問題かも。
上記C++コードを愚直にPHP移植したもの
読み込み部分とか超遅くて全然最適化してないけどまあ6秒くらい