子どもと歩くようになって、手すりが上下二段になっている階段の価値が分かるようになった。……なったのだけど、なぜか下の子は背伸びして上の方の手すりを持ちたがる。子どもはそういうところがある。
口の中を噛んだ。よくやる。自覚はないけど、疲れているのかも……。たぶん噛むたびに思っている。
https://iris.to/note13plpyg27afrez75hjsusv09dtj7da4e8p2fnc6ev4qmzr67f7dfqelze38
- Typical Stairs (AtCoder Beginner Contest 129 C問題)
https://atcoder.jp/contests/abc129/tasks/abc129_c
- https://atcoder.jp/contests/abc129/submissions/41481462
- カエルの DP に踏んじゃいけない足場を足したような問題
- 遷移時に踏んでいい足場かどうかを見ればよい
- 最初の足場が 1 通り、そこから遷移先に自分の足場までの通り数を足していけば良い
use modint::ModInt1000000007 as ModInt; use proconio::input; fn main() { input! { n: usize, m: usize, a: [usize; m], } let mut ok = vec![true; n + 1]; for a_i in a { ok[a_i] = false; } let mut dp = vec![ModInt::new(0); n + 1]; dp[0] = ModInt::new(1); for i in 0..=n { for j in i + 1..=i + 2 { if j <= n && ok[j] { dp[j] = dp[j] + dp[i]; } } } let ans = dp[n]; println!("{}", ans); } // modint
今日のコミット。