問題
$N$ 人の応募者をランダム順に面接。各面接後に「採用」or「次へ進む」を即座に決定。一度パスした応募者は採用不可。面接ごとにコスト $C$ が発生し、スコア $k$ の人を採用すれば報酬 $k$。最後まで誰も採用しない場合は報酬 $0$。最適戦略の期待利益を有理数で求めよ。
制約
$1 \le N \le 5000$
$1 \le C \le 100$
入出力例
入力例 1
3 1出力例 1
11/6ヒント (段階的開示)
ヒント1: 方向性
DP を後ろから。$dp[i][j]$ = 「$i$ 番目以降を面接、これまでの最高スコアが $j$」のときの最適期待利益。
ヒント2: アプローチ
残り人数の条件付きでスコア分布を計算。順列の対称性から「残り N-i+1 個のスコア」は等確率に分布。
ヒント3: 誘導
$dp[i][j] = -C + E_s[\max(s, dp[i+1][\max(j,s)])]$。
Fraction で誤差なし計算。模範解答 (Python)
from fractions import Fraction
import sys
input = sys.stdin.readline
def solve():
N, C = map(int, input().split())
C_frac = Fraction(C)
# 後ろから DP（簡易版）
dp = [Fraction(0)] * (N + 1)
for i in range(N, 0, -1):
dp_new = [Fraction(0)] * (N + 1)
denom = Fraction(1, N - i + 1)
for j in range(i - 1, N + 1):
val = Fraction(0)
cnt_low = j - (i - 1)
if cnt_low > 0 and j > 0:
floor_val = dp[j]
s_sum = Fraction(0)
for s in range(1, j + 1):
s_sum += max(Fraction(s), floor_val)
val += denom * Fraction(cnt_low, j) * s_sum
for s in range(j + 1, N + 1):
val += denom * max(Fraction(s), dp[s])
dp_new[j] = -C_frac + val
dp = dp_new
print(dp[0])
solve()Step-by-Step 解説
1定式化
秘書問題のコスト・スコア拡張。最適停止理論の典型。
秘書問題のコスト・スコア拡張。最適停止理論の典型。
2状態設計
$dp[i][j]$ = 残り面接時の期待利益。後ろから DP。
$dp[i][j]$ = 残り面接時の期待利益。後ろから DP。
3遷移
各 $s$ について「採用 ($s$)」 vs 「パス ($dp[i+1][\max(j,s)]$)」を $\max$ で選ぶ。
各 $s$ について「採用 ($s$)」 vs 「パス ($dp[i+1][\max(j,s)]$)」を $\max$ で選ぶ。
4分数演算
Fraction で誤差なしの期待値計算。よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| コストを後で引く | コストは面接ごと | 各ステップで -C |
| 最後の人を強制採用 | パスも選択肢 | dp[N+1][j] = 0 |
| 浮動小数点誤差 | float 利用 | Fraction を使う |
次のステップ
- 複数採用枠の秘書問題
- 最適停止と American option pricing