人生を書き換える者すらいた。人生を書き換える者すらいた。問題を公開のあと、トラックバックやはてブでいろいろ回答や感想を見ました。したコードが書ける人が何人もいることがわかり(まあそういう人がレスポンスを出しているので当たり前か)、一安心です。本当に世間のレベルがあの求人サイトの応募者のレベルだったら、マジで日本のソフトウェア産業は滅びると思っていたからな...コメントの中で特に気になったものいくつかについて書いてみます。過去に似たことをやっていれば有利、というのは確かにそうです。いう予備知識がなくても普通に考えて実装するのに充分な時間として3時間という設定でした。いうか、僕も今回の反応を見るまでA*というアルゴリズムは知らなかったよ!また、解答は単に正解が出力できるかではなく、「コードの質」も見てます。僕もこの世界は長いので、ある程度ボリュームのあるコードを見ればその人の実力はだいたいわかる。柔道の達人は帯の締め方を見るだけで相手の実力がわかる、というのと似たようなもの。事前知識の有無で結果が変わらないような出題にしたいとは最初から思ってはいたけれども、そうすると本当に無味乾燥なプログラムを書く問題になってしまって面白くないのであきらめました。本当はこういう感じで複数題やらせればいいのかもしれないけど、それは手間がかかりすぎるしで。●「業務には必要ない」「これでプログラマの実力が測れるのか?」という指摘もちろんこれと同じアルゴリズムが仕事で必要になるとは思ってませんが、似たような思考力を要することはたくさんある。少なくとも僕の仕事では毎日そうです。あとこれは書き忘れていた気がするが、この実技試験はあくまで1次試験であって、これをクリアした人は論述試験と面接を経てはじめて採用です。コーディングだけで採用を決めているわけではないです。この問題ができたから優秀な人材とは限らないけれど、できない人は"ほぼ確実に"優秀ではない、のではないかと。大学入試の問題でもそうだけど、確かに受験勉強はくだらない知識がいろいろ必要にな上に、それは人間の価値とは大して結びつかない。あの程度のことも満足にできないようでは、社会に出てから直面するもっと難しい問題には到底たちうちできないでしょう。真の実力を測る問題ではないからといって、その問題に価値がないというわけではないのです。調子に乗って、口頭試験で使う用の問題の1つを公開します。分野としては数学だけど、こういう論理的思考が得意な人はデバッグ能力も高いと期待できるのではないかと思います。6人でミーティングをする。どの2人を取っても、初対面か会ったことがあるかのいずれかである。このとき、「互いに初対面の3人組」か「互いに会ったことのある3人組」のどちらかは存在することを証明せよちなみに元ネタは最近読んだ本です。気がつけば10秒でわかります。»コメント2色以下と3色以上なんで自明ですね。23:05A*ご存じでなかったですか。あとその最後の問題は、どの二人についても初対面か会ったことがあるかの何れかって、何の制約でもないですね。その2つしかありえないでしょう。いうならば「鳩の巣原理による」といったところですか。就職活動中なので、このくらいでいいのなら少し興味あるなあと思いました。遅いだろうけど・・・。15:38間違ってたら恥ずかしいけど。>どの2人を取っても、初対面か会ったことがあるかのいずれかであるということは、初対面3人、会ったことがある3人、という事にならないので、初対面ないし合ったことがあるのいづれかで3人組ができます。16:35面識ある人の面識ある人とは面識があるとは限らないので単純な塗り分け問題では無理かなあと思いグラフを描きながら30分位考えて証明できました。おもしろいパズルでした。22:01探索問題は素養を見るものとすると、口頭試験では素質が分かりそうですね。定石は知りませんが、六角形状に配置して任意の3点で三角形を作り、辺を2色で場合分けすると必ずいずれかの三角形で3辺の色が一致するって感じでしょうか。03:42きっと定石があるのでしょうけど、、、答え?に辿り着くのに20秒程度かかってしまいました。ある一人(Aとする)に着目して、その他5人のうち3人(BCDとする)以上が会ったことがあると仮定する。BCDのうちいずれか会ったことがある組(BCとする)があるならば、ABCで互いに会ったことがある。なければ、BCDは互いに初対面。Aが会ったことがある人が2人以下であるとしたら、会ったことがある/ないを入れ替えて考えればOK。11:582人の関係を赤・青の2色で考える(どちらが初対面かは言及しない)命題が成り立たないように考えていくとABCの3者間の関係は赤2本と青1本になる(逆でも可)ここではA-B,A-Cが赤、B-Cが青とするDEFの関係のうち、青は必ず1本存在する(D-Eと仮定)ADEの関係でA-D,A-Eのどちらかは必ず赤になる(A-Dと仮定)ABDのうちA-B,A-Dは赤なのでB-Dは青。同様にACDのうちC-Dは青。ここでBCDの3辺が全て青になってしまうので、必ず命題は成立する。こんな感じでしょうかね。12:192つ上の解法の方がスマートでしたね。[Caleidoscopioの日記]またまた「人生を書き換える者すらいた。6人でミーティングをする。どの2人を取っても、初対面か会ったことがあるかのいずれかである。