プログラマを面接する際に出すコードの問題について

Fizz Buzzは解けてもAntsは解けないwyukawaです。こんにちは。

Antsというのはこういう問題です。

長さLcmの竿の上をn匹のアリが毎秒1cmのスピードで歩いています。アリが竿の端に到達すると竿の下に落ちていきます。また、竿の上は狭くてすれ違えないので、二匹のアリが出会うと、それぞれ反対を向いて戻っていきます。各アリについて、現在の竿の左端からの距離 $x_i$ はわかりますが、どちらの方向を向いているのかはわかりません。すべてのアリが竿から落ちるまでにかかる最小の時間と最大の時間をそれぞれ求めなさい。

制約

$1 <= L <= 10^6$
$1 <= n <= 10^6$
$0 <= x_i <= L$

下記の本にのってます。

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

作者: 秋葉拓哉,岩田陽一,北川宜稔
出版社/メーカー: マイナビ
発売日: 2012/01/28
メディア: 単行本（ソフトカバー）
購入: 25人クリック: 473回
この商品を含むブログ (36件) を見る

例えば僕が面接の場で、この問題を解いてホワイトボードにコード書いてくださいって言われたら間違いなくフリーズします。というか初めて問題を見たときまず問題の意味がわからなかったです。

ただこれに関しては入力と出力が例示されていれば問題の意味も少しはわかると思います。
例えばL=10つまり10cmの竿があってn=3つまり3匹のアリがそれぞれ竿の左端から2, 6, 7の距離の位置にいるとします。
この場合最小の時間が4(6の位置にいるアリが右に行く)で最大の時間が8(2の位置にいるアリが右に行く)になります。

Pythonで書くと入出力、実行結果はこんなイメージ。

def solve(length, ants):
  ...


solve(10, [2, 6, 7]) # min=4, max=8 と出力される。

これでなんとなく問題のイメージがつかめるかもしれませんが、アリが出会ったときをどう考えるんじゃい？ってところでフリーズする気がします。

このギャップを超えるには発想の柔軟性が求められます。

答えを言ってしまうと、
アリが出会っても出会わなくても見かけ上同じ状態のようになるので、アリは独立していると考えることができるから、出会った時の事を考慮しなくて良いです。つまり最小の時間は端までの最小距離で最大の時間は端までの最大距離です。

ここまでくれば何とかコードを書ける気がします。

ちなみにPythonで書くとこんな感じでしょうか。

実行結果はこんな感じ。
http://codepad.org/TpBS8eNk

実装言語は何でもいいんですけど面接の場でAnts問題出されてこのように解ける人というのはかなり少ない気がします。スーパープログラマ以外はお断りというのならそれでもいいんですが多分それは採用側も意図していないと思います。

入出力例やコードの外枠まで見せて問題を理解したとしても、面接の場でコード書いてくださいっていうのはよほど簡単な問題でない限り解くのは難しい気がします。緊張しているだろうし時間の制約もあるだろうし。ましてAnts問題は発想の柔軟性が求められるのでなかなか難しいです。逆に言うと知っていれば解けるという側面もあります。面接官がヒントだしながらとかならアリかも。あるいは面接の場で軽くペアプログラミングしてみるとか。

あとは家で時間制限なしにネットや書籍を見ずにサンクトガーレンのビールでも飲みながらリラックスした状態で解いてくださいというのはアリだと思います。まあネットや書籍を見なかったという証拠は出せないでしょうけどね。ただ僕がAnts問題を家でやって解けるかというと多分解けないでしょう。ビール飲んでいい気分になって寝ておしまいでしょうね。

そんなことしないで応募者のgithubを見ればいいじゃんという話もあるかもしれませんが、それだと面接官が見たいポイントが違うかもしれないですよね。例えばJoelが言っていたような再帰とポインタを理解しているかみてみたいとかあるかもしれないわけですね。実装言語に関するスキルというよりはどちらかというとアルゴリズムに関するスキルを見たいというのは理解できます。なので面接の場なのか家での宿題なのかはおいておいて何かしらコードというかアルゴリズムに関する問題を出したいというのは理解できます。ただその際にAnts問題のような発想の柔軟性が求められる問題を出してしまうと白紙解答が増えてしまいそうです。なのでもうちょっと手を出しやすい問題を出すほうがいい気がしますね。それがどういう問題なのかうまく例示はできないですが、何かしら再帰をからめたほうが能力をはかれる気がします。ただ再帰がからむプログラムをいちから実装するのは難しいんですけどね。。。いちから実装するのではなくヒントありで出すか、出し方なり見せ方なり変えるかぐらいがいい案配な気がします。

ちなみに僕は情報処理試験の基本情報やソフトウェア開発（今だと応用情報だっけか）の試験勉強ぐらいでしかアルゴリズムにみっちり触れてないです。なので試験勉強から10年近くたった今となってはアルゴリズムの問題をいきなりだされるとちと辛いｗ

どれぐらい辛いかというとプログラミングコンテストチャレンジブックのくじびき問題は解けて上述のAnts問題と再帰を使う部分和問題はカンニングしたというレベルですｗ　正直にいってアルゴリズムをかなりみっちりやってないとプログラミングコンテストチャレンジブックの問題を解くのは難しいと思います。

ちなみにくじびき問題というのはこんな問題です。

あなたの友人は次のようなゲームをあなたに仕掛けてきました。数字が書かれたn枚の紙切れが袋に入っています。あなたはこの袋から紙切れを取り出し、数字を見ては袋に戻すということを4回行い、4回の紙切れの数字の和がmになっていればあなたの勝ち、そうでなければ友人の勝ちとなります。あなたはこのゲームに何度か挑戦しましたが、一度も勝つことができませんでした。怒ったあなたは袋を破り、すべての紙切れを取り出して本当に勝つ可能性があるのか調べることにしました。紙切れに書かれている数字が $k_1, k_2,...,k_n$ であったとき、和がmになる取り出し方が存在するかどうかを計算し、存在するならYes、存在しないならNoと出力するプログラムを作成してください。