競プロ典型90問をRustで解いていこう（動的計画法）14日目

2022-05-19

はじめに

息子が1歳になりました。実にめでたいです。歩くのもずいぶん上手くなり、バランスを崩して後ろにコケることは減りました。子供の学習能力の高さに驚くばかりです。コンピュータだと、強化学習で簡単な動きを学ばせたときでも数千回、数万回は軽く試行する必要があるのに子供はそこまでの試行回数はこなしてないですもんね。

実際に試す以外にも、脳内でシミュレーション回して学習してるんですかね。それか情報量が視覚以外にも触覚があるのも良いんですかね。立ち上がるときに、床から返ってくる反動とかを学習パラメータに使うと良いのかな。

自分の動き以外にも環境から受け取るパラメータや、環境に対して働きかけて返ってくるパラメータの変化とかも考慮して学習回すのが良いのでしょうか。

近況ニュース

明治用水の底に穴が開いたというニュースがやってました。会社でのニュースになってて、農業用、工業用水の今年一杯は農業ができないというニュースがやってました。会社もその影響を受けて断水し、出勤禁止措置が取られています。結構な大事のニュースにはなっているようなのですが、他の地域だと「へぇそうなんだ」ぐらいのニュースなんだろうなとは思ってます。

愛知県産の野菜や米が無くなるか、値段が高くなるかがありそうだなと少しげんなりしてます。

あとは、ソフトウェアデザインの発売日です。かれこれニ年ぐらい定期購読してます。あと同じ日に発売なのは知らなかったのですが、大西泰斗の英文法定番レシピも合わせて買ってきました。ビデオで見るのが性にあってるのか結構長く続いています。本に比べると効率は劣るかもしれないですが、長く続けようという気持ちでやってます。

本日の問題

競プロ典型90問をRustで解いていこう（準備）0日目

今日は上の記事から14問目を解いていきます。

050 - Stair Jump（★3）を解いていこうと思います。

050 - Stair Jump（★3）

Ｎ段の階段を上るときに、1段かＬ段上ることができる。 0段目から出発してＮ段にたどり着くまでの移動方法が何通りあるかを問われています。

何通りかを求めた後、$ {10^9 +7} $ で割った余りを求める問題となります。

Rustでの回答例

規則性を見つけて、漸化式を立てて計算して解く問題のようです。

$$ \begin{cases} dp[i] = 1 (i = 0)\ dp[i] = dp[i = 1](1 ≦ i < L)\ dp[i] = dp[i = 1]+dp[i-L] (i ≧ L) \end{cases} $$

例えば、$N=10$段の階段を$2$段飛ばしで登れる場合を考える。この場合5段目に辿り着く方法としては2パターンある。・4段目から1段登る・3段目から2段登る同じように、4段目に辿り着く方法を考えると 3段目から1段登る、2段目から2段登る同じようにその組み合わせの数を数えていくと、上のような漸化式を立てることができますと。

その漸化式に実際に値を当てはめてみると、

$$ i=5\ L=2\ \begin{cases} dp[5] = 1 \ dp[5] = dp[5-1] \
dp[5] = dp[5-1] + dp[5-2]\ \end{cases} $$

use proconio::input;

fn main() {
    input! {
        n: usize,
        l: usize,
    }

    let mut dp = vec![0; n + 1];
    dp[0] = 1;
    for i in 1..=n {
        if i < l {
            dp[i] = dp[i - 1];
        } else {
            dp[i] = (dp[i - 1] + dp[i - l]) % 1000000007;
        }
    }
    println!("{:?}", dp[n]);
}

この方法で上手くいきましたね。よかった。