問題
マルコフ連鎖は状態の間をランダムに移動し、次の状態は現在の状態だけで決まります。transition[i][j] は状態 i から状態 j へ移る確率なので、各行の和は 1 です。
p が今それぞれの状態にいる確率なら、1 ステップ後の分布は次のとおりです。
p_next[j] = i についての p[i] × transition[i][j] の和 Σ
markov_distribution(transition, start, steps) を実装し、この更新を steps 回適用してください。
入力
transition: 各行の和が 1 の n × n 行列。
start: 初期分布 (和が 1 の n 個の値)。
steps: 進めるステップ数。
出力
steps ステップ後の分布を返します。
制約
1 ≤ n ≤ 50、0 ≤ steps ≤ 1,000
0 ≤ 各確率 ≤ 1
例
入力：
start = [1.0, 0.0]
steps = 2
transition = [
[0.9, 0.1],
[0.5, 0.5]
]
期待される出力：
expected = [0.86, 0.14]入力：
std::vector<double> start = {1.0, 0.0};
long long steps = 2;
std::vector<std::vector<double>> transition = {
{0.9, 0.1},
{0.5, 0.5}
};
期待される出力：
std::vector<double> expected = {0.86, 0.14};入力：
double[] start = new double[] {1.0, 0.0};
long steps = 2;
double[][] transition = new double[][] {
new double[] {0.9, 0.1},
new double[] {0.5, 0.5}
};
期待される出力：
double[] expected = new double[] {0.86, 0.14};解説
晴れ (0) と雨 (1) の日を考え、晴れから始めます。1 ステップ後: [0.9, 0.1]。2 ステップ後: 晴れ = 0.9 × 0.9 + 0.1 × 0.5 = 0.86、雨 = 0.9 × 0.1 + 0.1 × 0.5 = 0.14。
入力：
start = [0.25, 0.75]
steps = 3
transition = [
[0.0, 1.0],
[1.0, 0.0]
]
期待される出力：
expected = [0.75, 0.25]入力：
std::vector<double> start = {0.25, 0.75};
long long steps = 3;
std::vector<std::vector<double>> transition = {
{0.0, 1.0},
{1.0, 0.0}
};
期待される出力：
std::vector<double> expected = {0.75, 0.25};入力：
double[] start = new double[] {0.25, 0.75};
long steps = 3;
double[][] transition = new double[][] {
new double[] {0.0, 1.0},
new double[] {1.0, 0.0}
};
期待される出力：
double[] expected = new double[] {0.75, 0.25};解説
この連鎖は必ず状態を切り替えるので、各ステップで 2 つの確率が入れ替わります。3 回入れ替えた後: [0.75, 0.25]。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
現在の分布から、各遷移に確率を流して次の分布を求める。
ヒント 2
1 step ずつ繰り返す行列・ベクトル積だと考える。
ヒント 3
steps が 0 のときは、開始時の分布をそのまま返す。
目安の計算量
時間 O(steps * n^2)、追加メモリ O(n)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。