💭

ノート:「3.7.7動的計画法の例③:階段の上り方」

2022/01/02に公開

DP問題を解く上で思考ミスがあったので、その記録。

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ab

基礎的な問題のはずだけど、今日、こういう間違ったコードを書いてしまった。

let N = Int(readLine()!)!

var dp = [Int](repeating: 0, count: N)
dp[1] = 1

for i in 2..<N {
    let v1 = dp[i - 2] + 1
    let v2 = dp[i - 1] + 1
    dp[i] = v1 + v2
}

print(dp[N - 1])

間違い-1

v1 と v2 のところでそれぞれ1 を足しているのが誤っているが、そもそもなぜ1を足してしまったのかというと...
「これから1歩踏み出すから、その行動分1個増えるのでは」
と考えたのだと思われる。

ただ、これはちょっと考えれば間違っていると気づく。

  • 仮に1歩しか登れないと仮定すると、階段を登るたびに「登る方法」が1つずつ増えることになるが、実際は各段においてその段に到達する方法は1通りしか無いので矛盾する。

ということで1を足すのは誤りとわかる。

-    let v1 = dp[i - 2] + 1
+    let v1 = dp[i - 2]
-    let v2 = dp[i - 1] + 1
+    let v2 = dp[i - 1]

今後の対策

上手く行かないときは、簡単な例を作って丁寧にたどって考えてみよう...

間違い-2

ただ、そうすると今度は計算結果があわない。

原因は dp[0] にあると気づいた。

なぜdp[0] = 0 と考えてしまったのかと言うと...
「0段目に 登る 方法は0通り」
と考えてしまったからだと思われる。

確かにスタート地点が0段目なので、登るというのはできないわけだが...
dp[0] = 1 とすると、サンプルは通る。
この"割り当て"を、問題文の設定においてどのように解釈すべきかよくわかってはいない...

とりあえず、「そうやると上手くいく」と考えることにする。

 var dp = [Int](repeating: 0, count: N)
+dp[0] = 1
 dp[1] = 1

追記

「『なにもしない』を1通りとしてカウントする」という説が自分の中で有力になりつつある。
たしかに問題文をよく読むと、「登る」ではなく「たどり着く」と書いてあるので、なにもしなくてもたどり着く方法が1通りあるという解釈は、わりと通りそう...?

今後の対策

これは解釈の問題を含むから今後も結構ハマりそう...
問題の数をこなせばどうにか克服できるのかな...

間違い-3

https://atcoder.jp/contests/math-and-algorithm/submissions/28289506

N = 1 の考慮漏れ...というより Swift の仕様誤認。

https://developer.apple.com/documentation/swift/comparable/2949700

要するに 0..<(-1) はセーフだけど、 0...(-1) はランタイムエラー。

-for i in 2...N {
+for i in 2..<(N + 1) {

今後の対策

Swiftの仕様を覚えよう

(というかこのトラップにハマるの3回目くらいなのでそろそろ覚えたい...(ノД`))

正解

勉強のために、かなり分解してある。

https://atcoder.jp/contests/math-and-algorithm/submissions/28289571

脚注
  1. 米田 優峻. 問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本 (Japanese Edition) (p.241). Kindle 版. ↩︎

Discussion