前回はこちらから。

AtCoder Beginner Contest 129に参加した。けど、寝過ごして、1時間ほど遅れての参戦となってしまった...

時間内に正解できたのは、AとB問題のみ。C問題は、時間内に取り組むことはできたのだけど、アルゴリズムがわからなかった。

コンテストが終わった後にC問題の解説を読んで納得。フィボナッチ数列の求め方の応用だったかぁ...
悔しいなぁと思いつつ、アルゴリズムがわかったので、実装に挑戦することに。

というわけで、今回は、ABC129Cを解いていこう。

ABC129Cの問題

問題文
N 段の階段があります。高橋君は現在、上り口(0 段目)にいます。
高橋君は一歩で 1 段か 2 段上ることができます。
ただし、a1,a2,a3,....aM 段目の床は壊れており、その段に足を踏み入れることは危険です。
壊れている床を踏まないようにしながら、最上段(N 段目)にたどりつくまでの移動方法は何通りあるでしょうか？
総数を 1,000,000,007 で割った余りを求めてください。

制約
- 1≦N≦10^5
- 0≦M≦N−1
- 1≦a1<a2< ... <aM≦N−1

さぁ解くぞ～。

アルゴリズム

解説をざっと読んで、フィボナッチ数列を求めるときのアルゴリズムと似たものを考えてみた。

1. 壊れた床の番号を受け取る
2. ｘ=2とする
3. ｘ段目が壊れた床ならｘ段目の移動パターン数を0にして、手順5へ
4. ｘ段目に行く移動パターン数を、ｘ－１段目とｘ－２段目に行く移動パターン数の和で求める
5. ｘがN(最上段)ではないならｘを＋１して、手順3へ
6. N段目に行く移動パターンを解答する

こんな感じかな。
各段に移動するパターン数をスライスで保持して、次の移動パターン数を求めるのに利用すれば、特に計算量も大きくなく計算できそう。

というわけで、手順3の処理は以下のようにすれば、すっきりかけていい感じかな。

// steps[i]: i段目に行くための移動パターン数
for i := 2; i <= n; i++ {
    steps[i] *= (steps[i-1] + steps[i-2]) % 1000000007
}

stepsスライスはすべて1で初期化し、通れない段は0にしている。これによって、各段の移動パターン数が上記のコードだけで求められることに。

最初は、1で初期化せずにやろうとして、ここの処理がもう少しだけ複雑化しそうだった。けれども、シンプルにしたくて考えた結果、初期化処理を入れることに。その結果が上記のコード。シンプルで結構気に入っている。

あとは、入力処理と出力処理入れたら完成だぁ～！

解答

最終的に以下のようなコードに。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

func main() {
    sc := bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    sc.Scan()
    n, _ := strconv.Atoi(sc.Text())
    sc.Scan()
    m, _ := strconv.Atoi(sc.Text())

    steps := make([]int, n+1)
    for i := range steps {
	steps[i] = 1
    }

    for i := 0; i < m; i++ {
    	sc.Scan()
	a, _ := strconv.Atoi(sc.Text())
	steps[a] = 0
    }

    for i := 2; i <= n; i++ {
	steps[i] *= (steps[i-1] + steps[i-2]) % 1000000007
    }

    fmt.Println(steps[n])
}

今回初めて、解説を読みながら実装することになった。いずれは、読まずともサラサラ～っと解けるように修行しなきゃ。

さぁ、成長目指して次回も頑張るぞ！