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

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版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?