perogram

D - Lucky PIN ~4次元DPで解く編~

f:id:peroon:20191202031704p:plain

Quiz

https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d

AC

https://atcoder.jp/contests/sumitrust2019/submissions/8754255

解法

  • dp[i][j][k][l]
  • i : i番目まで見た時
  • j : 最後に選んだ数
  • k : 1つ前に選んだ数
  • l : 2つ前に選んだ数
  • としてDP
  • しかし、選んだ数が未定という状態を数字10として扱った
ll dp[30010][11][11][11];

// 初期状態
ll v = ctoi(s[0]);
dp[0][v][10][10] = 1;
dp[0][10][10][10] = 1;

Code

FOR(i, 1, N){
  char c = s[i];
  ll v = ctoi(c);

  rep(j, 11){
    rep(k, 11){
      rep(l, 11){
        // 今回のを採用しない
        dp[i][j][k][l] += dp[i-1][j][k][l];
      }
    }
  }

  rep(j, 11){
    rep(k, 11){
      // 今回のを採用
      dp[i][v][j][k] += dp[i-1][j][k][10];
    }
  }
}

ll cnt = 0;
rep(i, 10){
  rep(j, 10){
    rep(k, 10){
      if(dp[N-1][i][j][k]) cnt++;
    }
  }
}
p(cnt);

感想など

  • この解法はeditorialに載っていなかったので書いた
  • これで通せたのは成長と言えるが、時間をかけすぎた
  • editorialにはもっと簡単な解法があったので、DPにこだわりすぎないようにしたい

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?