buyoh.hateblo.jp

残念な競技プログラミング参加者

yukicoder No.533 Mysterious Stairs

前日にtesterしました.

f:id:m_buyoh:20170623205251p:plain

問題概要

No.533 Mysterious Stairs - yukicoder

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

基本解法

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

  1. まだジャンプしていない.
  2. 1段ジャンプしたので,次は1段ジャンプ出来ない.
  3. 2段ジャンプしたので,次は2段ジャンプ出来ない.
  4. 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;
}

以上の改良により,時間計算量はO(N),空間計算量はO(1)になりました.

改良2

現在のdp配列の状態をx,次のdp配列の状態をyと表現すると,上のプログラムでやってることは次のように表現できる.

  • y_{1,1} = x_{1,2} + x_{1,3}
  • y_{1,2} = x_{2,2}
  • y_{1,3} = x_{2,3}
  • y_{2,1} = x_{3,1}
  • y_{2,2} = x_{1,1} + x_{1,3}
  • y_{2,3} = x_{3,3}
  • y_{3,1} = 0
  • y_{3,2} = 0
  • y_{3,3} = x_{1,1} + x_{1,2}

  • どうやら,y_{2,1}y_{3,1}y_{3,2}は要らなさそう. しかも,見るからに連立方程式なので,行列の形で書ける.

f:id:m_buyoh:20170623205005j:plain

6x6行列をAとすると,

  • 1段目に居るときのdp配列の状態{\boldsymbol s_1}=(1,0,0,1,0,1)^T
  • 2段目に居るときのdp配列の状態{\boldsymbol s_2}=A{\boldsymbol s_1}
  • 3段目に居るときのdp配列の状態{\boldsymbol s_3}=A{\boldsymbol s_2}=A^2{\boldsymbol s_1}
  • N段目に居るときのdp配列の状態{\boldsymbol s_N}=A^{(N-1)}{\boldsymbol s_1}

つまり,A^{(N-1)}が計算できれば良い.

累乗計算は愚直にやると線形時間掛かってしまうが,O(\log N) で解く手法が編み出されている.

以上の改良により,時間計算量はO(\log N),空間計算量はO(1)になりました.