Skip to content

A17

Directory actions

More options

Directory actions

More options

Latest commit

 

History

History

A17

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
A17.go
A17.go
 
 
A17.js
A17.js
 
 
A17.php
A17.php
 
 
README.md
README.md
 
 

README.md

この問題は、最短経路問題の一種であり、動的計画法 (DP) を使って解くことができます。

解法

  1. DPテーブルの定義

    • dp[i] を部屋 i までの最短時間とする。
    • prev[i] を部屋 i に到達する直前の部屋として、最短経路を復元できるようにする。

  2. 遷移

    • 部屋 i-1 から部屋 i へ移動する場合:
      dp[i] = min(dp[i], dp[i-1] + A[i-2])
    • 部屋 i-2 から部屋 i へ移動する場合 (i ≥ 3):
      dp[i] = min(dp[i], dp[i-2] + B[i-3])

  3. 経路復元

    • prev を使って逆順にたどることで、最短経路を取得する。

JavaScript 実装

function shortestPath(N, A, B) {
    // dp配列の初期化 (十分大きな値で初期化)
    let dp = Array(N + 1).fill(Infinity);
    let prev = Array(N + 1).fill(-1); // 経路復元用

    // 初期状態
    dp[1] = 0;

    // DP配列を埋める
    for (let i = 2; i <= N; i++) {
        if (dp[i] > dp[i - 1] + A[i - 2]) {
            dp[i] = dp[i - 1] + A[i - 2];
            prev[i] = i - 1;
        }
        if (i >= 3 && dp[i] > dp[i - 2] + B[i - 3]) {
            dp[i] = dp[i - 2] + B[i - 3];
            prev[i] = i - 2;
        }
    }

    // 経路復元
    let path = [];
    for (let i = N; i !== -1; i = prev[i]) {
        path.push(i);
    }
    path.reverse();

    // 出力
    console.log(path.length);
    console.log(path.join(' '));
}

// 標準入力の処理
function main(input) {
    let lines = input.trim().split('\n');
    let N = parseInt(lines[0], 10);
    let A = lines[1].split(' ').map(Number);
    let B = lines.length > 2 ? lines[2].split(' ').map(Number) : [];

    shortestPath(N, A, B);
}

// テスト実行用
const input = `5
2 4 1 3
5 3 3`;
main(input);

解説

  1. dp 配列の初期化

    • dp[1] = 0（スタート地点は移動時間0）
    • 他は Infinity で埋める。

  2. DPの遷移

    • 2部屋先にも移動できるため、dp[i] を更新する際に i-1 からの移動と i-2 からの移動を比較する。

  3. 経路の復元

    • prev 配列を用いて逆順にたどる。

  4. 標準入力の処理

    • A と B の入力を配列として取得。

計算量

  • O(N) で解けるので、最大 N=100000 でも高速に処理可能。

処理の流れを図解で説明

この問題は 動的計画法 (DP) を用いた最短経路探索 の典型例です。
以下のステップで処理を進めます。

1. 入力データの例

入力として以下のデータを考えます。

5
2 4 1 3
5 3 3
部屋番号 1 2 3 4 5
A[i] - 2 4 1 3
B[i] - - 5 3 3

2. DP配列の定義

  • dp[i]: 部屋 i までの最短時間
  • prev[i]: 部屋 i に到達する直前の部屋（経路復元用）
  • dp[1] = 0（スタート地点）

3. DPテーブルの更新

初期状態

dp = [∞, 0, ∞, ∞, ∞, ∞]
prev = [-1, -1, -1, -1, -1, -1]

部屋 2 への移動 (A[2] = 2)

  • dp[2] = dp[1] + A[2] = 0 + 2 = 2
  • prev[2] = 1
dp = [∞, 0, 2, ∞, ∞, ∞]
prev = [-1, -1, 1, -1, -1, -1]

部屋 3 への移動 (A[3] = 4, B[3] = 5)

  • dp[3] = dp[2] + A[3] = 2 + 4 = 6
  • dp[3] = min(6, dp[1] + B[3]) = min(6, 0 + 5) = 5
  • B経由が早いので選択
  • prev[3] = 1
dp = [∞, 0, 2, 5, ∞, ∞]
prev = [-1, -1, 1, 1, -1, -1]

部屋 4 への移動 (A[4] = 1, B[4] = 3)

  • dp[4] = dp[3] + A[4] = 5 + 1 = 6
  • dp[4] = min(6, dp[2] + B[4]) = min(6, 2 + 3) = 5
  • B経由が早いので選択
  • prev[4] = 2
dp = [∞, 0, 2, 5, 5, ∞]
prev = [-1, -1, 1, 1, 2, -1]

部屋 5 への移動 (A[5] = 3, B[5] = 3)

  • dp[5] = dp[4] + A[5] = 5 + 3 = 8
  • dp[5] = min(8, dp[3] + B[5]) = min(8, 5 + 3) = 8
  • どちらでも同じなので A を選択
  • prev[5] = 4
dp = [∞, 0, 2, 5, 5, 8]
prev = [-1, -1, 1, 1, 2, 4]

4. 経路復元

prev 配列を用いて逆順にたどる。

部屋 5 → 部屋 4 → 部屋 2 → 部屋 1

逆順にして出力:

4
1 2 4 5

5. 全体の図解

(1) ---2---> (2) ---4---> (3) ---1---> (4) ---3---> (5)
  \          /           /           /
   \---5----/           /---3-------/
  • 1 → 2 → 4 → 5 が最短経路（時間8分）

6. JavaScriptコード

function shortestPath(N, A, B) {
    let dp = Array(N + 1).fill(Infinity);
    let prev = Array(N + 1).fill(-1);

    dp[1] = 0;

    for (let i = 2; i <= N; i++) {
        if (dp[i] > dp[i - 1] + A[i - 2]) {
            dp[i] = dp[i - 1] + A[i - 2];
            prev[i] = i - 1;
        }
        if (i >= 3 && dp[i] > dp[i - 2] + B[i - 3]) {
            dp[i] = dp[i - 2] + B[i - 3];
            prev[i] = i - 2;
        }
    }

    let path = [];
    for (let i = N; i !== -1; i = prev[i]) {
        path.push(i);
    }
    path.reverse();

    console.log(path.length);
    console.log(path.join(' '));
}

function main(input) {
    let lines = input.trim().split('\n');
    let N = parseInt(lines[0], 10);
    let A = lines[1].split(' ').map(Number);
    let B = lines.length > 2 ? lines[2].split(' ').map(Number) : [];

    shortestPath(N, A, B);
}

const input = `5
2 4 1 3
5 3 3`;
main(input);

7. 計算量

  • O(N) で解ける（ループ1回 + 経路復元）

8. まとめ

  • 動的計画法 (DP) で解く
  • dp 配列 で最短時間を管理
  • prev 配列 で最短経路を復元
  • O(N) の計算量 で高速に解ける 🚀