yukicoder No.533 Mysterious Stairs

前日にtesterしました．

f:id:m_buyoh:20170623205251p:plain

問題概要
基本解法
改良1
改良2

問題概要

No.533 Mysterious Stairs - yukicoder

N段の階段がある．
1回の飛躍で1step,2step,3stepずつ登れる．
同じstep数を連続して使えない
N段目に到達するパターン数を出力せよ．

基本解法

4つの状態が考えられる．

まだジャンプしていない．
1段ジャンプしたので，次は1段ジャンプ出来ない．
2段ジャンプしたので，次は2段ジャンプ出来ない．
3段ジャンプしたので，次は3段ジャンプ出来ない．

0の状態はスタート時以外では発生し得ないので，1回ジャンプした状態を初期状態とすることで，0の状態を排除出来る．

あとは残り3つの状態について，どう遷移するのかを考えればいい．

今， $i$ 段目に居るとして，

$i+1$ 段目にジャンプできるのは状態2,状態3．
$i+2$ 段目にジャンプできるのは状態1,状態3．
$i+3$ 段目にジャンプできるのは状態1,状態2．

f:id:m_buyoh:20170623211537p:plain:w200 f:id:m_buyoh:20170623211540p:plain:w200 f:id:m_buyoh:20170623211534p:plain:w200

これをコードとして書けばAccept．

ll solve_MLE(int n) {
    vector<array<ll, 4>> dp(n + 4);

    dp[1][1] = 1; // 1jump で 1step 登る．次は 1jump は使えない．
    dp[2][2] = 1; // 2jump で 2step 登る．次は 2jump は使えない．
    dp[3][3] = 1; // 3jump で 3step 登る．次は 3jump は使えない．

    for (int i = 1; i < n; ++i) {
        // +1jumpする．
        dp[i + 1][1] = (dp[i + 1][1] + (dp[i][2] + dp[i][3])) % MD;
        // +2jumpする．
        dp[i + 2][2] = (dp[i + 2][2] + (dp[i][1] + dp[i][3])) % MD;
        // +3jumpする．
        dp[i + 3][3] = (dp[i + 3][3] + (dp[i][1] + dp[i][2])) % MD;
    }
    return (dp[n][1] + dp[n][2] + dp[n][3]) % MD;
}

時間計算量は $O(N)$ ，空間計算量も $O(N)$

改良1

問題制約を確認すると， $N$ は100万．
つまり，上のプログラムでは400万×8byteをメモリに載せる．
これを改善できないか？

上のコードをもう一度見てみると， $i$ より小さい要素には一切アクセスしないことが分かる．アクセスしない領域なら，再利用するべきでしょう．

配列の参照先をずらすんじゃなくて，配列の値をずらしましょう，という仕様です．

ll dp[4][4];
ll solve(int n) {

    dp[0][1] = 1; // 1jump で 1step 登る．次は 1jump は使えない．
    dp[1][2] = 1; // 2jump で 2step 登る．次は 2jump は使えない．
    dp[2][3] = 1; // 3jump で 3step 登る．次は 3jump は使えない．

    for (int i = 1; i < n; ++i) {
        // 1jumpする．
        dp[1][1] = (dp[1][1] + (dp[0][2] + dp[0][3])) % MD;
        // 2jumpする．
        dp[2][2] = (dp[2][2] + (dp[0][1] + dp[0][3])) % MD;
        // 3jumpする．
        dp[3][3] = (dp[0][1] + dp[0][2]) % MD;

        // dp配列をずらす．
        for (int u = 1; u <= 3; ++u) {
            for (int v = 1; v <= 3; ++v) {
                dp[u - 1][v] = dp[u][v];
            }
        }
        
    }
    return (dp[0][1] + dp[0][2] + dp[0][3]) % MD;
}