Skip to content

B16

Directory actions

More options

Directory actions

More options

Latest commit

 

History

History
 
 

B16

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
B16.go
B16.go
 
 
B16.js
B16.js
 
 
B16.php
B16.php
 
 
B16.py
B16.py
 
 
B16.ts
B16.ts
 
 
README.md
README.md
 
 

README.md

Error in user YAML: (<unknown>): did not find expected alphabetic or numeric character while scanning an alias at line 3 column 1
---

## 🔰 問題概要（再掲）

* 高さが `h[0] ~ h[N-1]` の足場がある。
* カエルは足場 `1`（インデックス `0`）からスタート。
* 一度に `+1` か `+2` のジャンプができ、ジャンプのコストは `|hi - hj|`。
* 足場 `N` に到達する最小コストを求める。

---

🧠 アルゴリズム概要：動的計画法（DP）

  • 定義：dp[i] = 足場 i（インデックス i）まで来る最小コスト

  • 遷移：

    dp[i] = min(
  dp[i-1] + |h[i] - h[i-1]|,
  dp[i-2] + |h[i] - h[i-2]|
)

  • 最終出力：dp[N-1]

📘 例題

N = 6
h = [30, 10, 60, 10, 60, 50]

🔁 処理の流れと図解

🔹 ステップ 1: 初期化

let prev2 = 0; // dp[0] = 0
let prev1 = Math.abs(h[1] - h[0]); // dp[1] = |10 - 30| = 20
足場:     1    2    3    4    5    6
Index:    0    1    2    3    4    5
高さh:   30   10   60   10   60   50
          ▲    ▲
        dp[0]=0
        dp[1]=|10-30|=20

🔹 ステップ 2: i = 2

cost1 = prev1 + |h[2] - h[1]| = 20 + |60 - 10| = 70
cost2 = prev2 + |h[2] - h[0]| = 0 + |60 - 30| = 30
dp[2] = min(70, 30) = 30
足場:     1    2    3
Index:    0    1    2
高さh:   30   10   60
dp:       0   20   30
                      ▲
        ←―― dp[0]→  dp[2]

🔹 ステップ 3: i = 3

cost1 = dp[2] + |10 - 60| = 30 + 50 = 80
cost2 = dp[1] + |10 - 10| = 20 + 0 = 20
dp[3] = min(80, 20) = 20
足場:     1    2    3    4
Index:    0    1    2    3
高さh:   30   10   60   10
dp:       0   20   30   20
                           ▲
              ←―― dp[1]→  dp[3]

🔹 ステップ 4: i = 4

cost1 = dp[3] + |60 - 10| = 20 + 50 = 70
cost2 = dp[2] + |60 - 60| = 30 + 0 = 30
dp[4] = min(70, 30) = 30
足場:     1    2    3    4    5
Index:    0    1    2    3    4
高さh:   30   10   60   10   60
dp:       0   20   30   20   30
                                 ▲
                    ←―― dp[2]→  dp[4]

🔹 ステップ 5: i = 5

cost1 = dp[4] + |50 - 60| = 30 + 10 = 40
cost2 = dp[3] + |50 - 10| = 20 + 40 = 60
dp[5] = min(40, 60) = 40
足場:     1    2    3    4    5    6
Index:    0    1    2    3    4    5
高さh:   30   10   60   10   60   50
dp:       0   20   30   20   30   40
                                       ▲
                          ←―― dp[4]→  dp[5]

✅ 結果

console.log(prev1); // 最終的に dp[5] = 40

✅ 最小経路の例（最小コスト経路）

足場1 → 足場3 → 足場5 → 足場6
 30     60       60       50

|30-60| + |60-60| + |60-50| = 30 + 0 + 10 = 40 ✅

🔚 結論

  • 各足場で、「1歩ジャンプ」と「2歩ジャンプ」の両方を考え、最小コストで更新。
  • 最後に到達した dp[N-1] が答え。
提出日時 問題 ユーザ 言語 得点 コード長 結果 実行時間 メモリ
2025-07-10 12:27:12 B16 - Frog 1 myoshizumi Go (go 1.20.6) 100 946 Byte 4 ms 4952 KiB 詳細
2025-07-10 12:22:28 B16 - Frog 1 myoshizumi PHP (php 8.2.8) 100 1030 Byte 32 ms 28356 KiB 詳細
2025-07-10 12:18:51 B16 - Frog 1 myoshizumi Python (CPython 3.11.4) 100 617 Byte 51 ms 21064 KiB 詳細
2025-07-10 11:46:04 B16 - Frog 1 myoshizumi TypeScript 5.1 (Node.js 18.16.1) 100 723 Byte 57 ms 52860 KiB 詳細
2025-07-10 11:41:15 B16 - Frog 1 myoshizumi JavaScript (Node.js 18.16.1) 100 535 Byte 81 ms 52832 KiB 詳細