ABC154E

E - Almost Everywhere Zero

桁DPの問題ですね。

考察力不足により、コンテスト中にACできませんでした。

コンテスト後も実装に手間取ったので、水色への道は遠そうです。

解き方としては、大まかには解説の通りですが、少し自分なりに変更しています。

（そのせいでコードが複雑になっているような気がしないでもない）

まず、値の読み込みから。

なので、一旦stringに格納してからint配列に移しています。

ついでに、の桁数をとしておきます。

  string s; cin >> s;
  int d = s.size();
  int n[d];
  for (int i = 0; i < d; i++) n[i] = s[i] - '0';
  int k; cin >> k;

では、DPパートです。

を、上位桁から桁目（0-indexed）まで見た時、0でない数字がちょうど個あるようなものの個数とします。

初期値は0桁目を、0とする場合1個、未満の値とする場合その値とします。
の値の場合は、下位桁の値によってを超えてしまう場合があるので保留です。

保留は桁目までと桁の値が同じ場合に起こるので、今まで見た桁の中における0でない数字の個数をとしておきます。

  int c = 1;
  int dp[d][k+1] = {};
  dp[0][0] = 1;
  dp[0][1] = n[0] - 1;

後は順当にDPをすれば良いですが、遷移が少し複雑です。

まず、の場合は全ての桁が0であるため、必ず1通りです。
それ以外の場合、どの数字が来ても問題ないので、0でない数字の場合から、0の場合から個数を持ってきます。

後は保留の場合を処理します。
が0だった場合は保留が解除される可能性はありません。
それ以外の場合、0でない数字の場合、0の場合であれば保留を解除することができます。

  for (int i = 1; i < d; i++) {
    dp[i][0] = 1;
    for (int j = 1; j <= k; j++) {
      dp[i][j] = dp[i-1][j-1] * 9 + dp[i-1][j];
    }
    if (n[i] > 0) {
      if (c <= k) dp[i][c] += 1;
      c++;
      if (c <= k) dp[i][c] += n[i] - 1;
    }
  }

最後に、と桁の値が完全一致している場合が保留となっているので、その場合に条件を満たすかどうかを確認して完了です。

  if (c == k) dp[d-1][k]++;
  cout << dp[d-1][k] << endl;

桁DPの説明難しいですね…。上手く説明できませんでしたが、自分の中での理解は深まりました。

他の人のコードやブログを読む習慣があまり無いので、その習慣がつけば少しはマシになるかもしれません。

では。