C++で解く飛行機の座席割り当て確率問題

問題概要

n人の乗客が、座席がちょうどnつ用意された飛行機に搭乗する場面を考えます。最初の乗客はチケットを紛失してしまったため、座席をランダムに選びます。それ以降の乗客は、以下のルールに従って行動します。

• チケットに記載された自分の座席が空いていれば、その座席に着席する
• 自分の座席がすでに埋まっている場合は、残りの空席からランダムに選ぶ

このとき、n番目の乗客が自分の座席に着席できる確率を求めるのが課題です。例えば入力が2の場合、出力は0.5となります。つまり、2番目の乗客が2番目の座席を確保できる確率は0.5です(1番目の乗客が1番目の座席に座った場合に限られます)。

解き方

この問題は一見複雑に思えますが、実は非常にシンプルな答えに落ち着きます。解法のステップは以下の通りです。

• nが1の場合は1を返す(乗客が1人だけなら、必ず自分の座席に座れるため)
• nが2以上の場合は0.5を返す

なぜ答えは0.5になるのか

直感的に理解するには、対称性に注目するとよいでしょう。最初の乗客が選んだ座席によって、その後の展開が決まります。

最初の乗客が1番目の座席を選べば、以降の全員が自分の座席に座れ、n番目の乗客も自分の座席を確保できます。逆に、n番目の座席を選んでしまえば、n番目の乗客は必ず失敗します。それ以外の座席(例えばk番目)を選んだ場合、k番目の乗客が到着した時点で、状況は「最初の乗客がランダムに選ぶ」という同じ構造の縮小版に置き換わります。この連鎖の結果、最終的に1番目の座席とn番目の座席のどちらが先に埋まるかは対等であり、それぞれの確率は0.5となります。

実装例(C++)

以下の実装を見ると、理解がさらに深まるでしょう。

class Solution {
public:
    double nthPersonGetsNthSeat(int n) {
        if (n == 1) return 1;
        return 0.5;
    }
};

入力

2

出力

0.50000