【AtCoder-Ruby】C - Typical Stairs（& ABC129 振返り）

ABC129 振返り

とりあえず、A, B のタイムは「20:17」。
10分を目標にしていたが、問題によって時間がかかる。。。

課題は練習の回答数が少ない。（現在100問弱というところ）
とりあえず、ABC AB 全問は解いてみようと思う。

C に関しては法則がピンとこなかった。
正解を見て、なるほど（フィボナッチとDP）と納得できたが、これも勉強と経験両方不足しているということだろう。

C - Typical Stairs 理解

参考にさせて頂きました。

• 動的計画法（DP）について学ぶ。
• トップダウン形式とボトムアップ形式と2種類のDPのうち、今回はボトムアップ形式の説明。

アルゴリズムのお勉強（３）- 動的計画法(DP) : ボトムアップ形式

ただ、ボトムアップ方式（配るDP）より、トップダウン（貰うDP）の方が好みなので、こちらで実装。

参考: 動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集

問題

問題文

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

制約

• 1 ≦ N ≦ 10 ** 5
• 0 ≦ M ≦ N − 1
• 1 ≦ a 1 < a 2 < ... < a M ≦ N − 1

問題リンク

回答

N, M = gets.strip.split.map(&:to_i)

mod = 10 ** 9 + 7

# bf: broken floors
bf = {}
M.times.map { bf[gets.strip.to_i] = 1 }

dp = Array.new(N + 1){0}

dp[0] = 1
dp[1] = 1 if bf[1].nil?

(2..N).each do |i|
  next unless bf[i].nil?
  # 自動型変換 version
  # dp[i] = dp[i - 1] + dp[i - 2]
  dp[i] = (dp[i - 1] + dp[i - 2]) % mod
end

# 自動型変換 version
# puts dp[N] % mod
puts dp[N]

考察

Ruby では演算結果により自動で型変換されるので、最後にあまりの計算して実行結果を確認したところ、3倍程度の差が出た。（コメント # 自動変換 version）

RubyではFixnumクラスとBignumクラスで整数値を、Floatクラスで浮動小数点を扱うことができます。
またMathモジュールでは三角関数や対数などを計算する関数が提供されます。
Fixnumは31ビットまたは63ビットの固定長整数を扱うクラスですが、演算結果をこの範囲を超える場合、自動的にBignumに拡張されます。
Bignumは無限多倍長整数でメモリの許す限りの大きな値を扱うことができます。

Fixnum: 32bit 符号付き整数なので、取りうる範囲は「−2,147,483,648 から 2,147,483,647」

自動変換 version

自動変換 なしversion

早く茶色になりたいなー

www.instagram.com