ABC029D 「1」

#問題概要

• $1$以上$N$以下の数字に登場する$1$の総数を求めよ $（1\leq N<10^9）$(リンク)
• ex) $N=12$なら$1,10,11,12$に$1$はそれぞれ$1,1,2,1$回出てくる（その他の数は$0$回）ので合計$5$個

#最初に考えたこと

• 桁dpっぽい
• dp[未満flag][桁数]　:= 登場した1の個数みたいな感じ？

#考察

• 結論からいうと上記の方法ではダメ
• 保持している状態の表現が弱い(漸化式に落とし込めなかった)
• dp[未満][桁][出現する1の個数] := 左記の条件を満たす数字の個数として条件を一つ増やし、後で足す
• $dp[i][j][k]$の足しこむ先を考える
• 未満flagが立っている時$(i == 1)$
  • この場合$j+1$桁目には好きな数字を選べる
  • $j+1$桁目に$1$を選んだ時 => $dp[1][j+1][k+1]$
  • $j+1$桁目に$1$以外$(0,2\sim9)$を選んだ時 => $dp[1][j+1][k]$
• 未満flagが立っていない時$(i == 0)$
  • 今回は$N$との大小関係を気にしないといけないので少々厄介
  • $N$の上から$j+1$桁目が$0$の時 => $dp[0][j+1][k]$
    • $j+1$桁目は$0$で確定
  • $N$の上から$j+1$桁目が$1$の時 =>
    • $j+1$桁目に$1$を選ぶと$dp[0][j+1][k+1]$(未満flagは立たない)
    • $j+1$桁目に$0$を選ぶと$dp[1][j+1][k]$(未満flagが立つ)
  • $N$の上から$j+1$桁目が$d(2\leq d \leq 9)$の時 =>
    • $j+1$桁目に$1$を選ぶと$dp[1][j+1][k+1]$(未満flagは立つ)
    • $j+1$桁目に$d$を選ぶと$dp[0][j+1][k]$(未満flagは立たない)
    • $j+1$桁目に$1,d$以外を選ぶと$dp[1][j+1][k]$(未満flagは立つ)

#解答

• 以上の考察をもとに実装すると以下のようになります
• 紛らわしいのですが、文字列は0-indexedでdp配列の2項目は1-indexedです
  (つまり$j+1$桁目$(dp[i][j+1][k])$に足しこむときは文字列の$j$番目を見ています)
• 個人的なトラップとしては、毎回文字定数の'1'とすべきところを整数の1としてしまう点

answer.cpp

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define rep(n, i) Rep(0, n-1, i)

const int MAX = 16;

//dp[未満][桁][出現する1の個数] := 左記の条件を満たす数字の個数
int dp[2][MAX][MAX*2];

void solve(void){
    string S;
    cin >> S;
    int D = S.length();
    dp[0][0][0] = 1;
    //dp[i][j][k]の寄与に注目
    rep(2, i) {
        Rep(0, D, j) {
            rep(MAX, k) {
                //未満flagが立っている
                if (i == 1) {
                    //1
                    dp[1][j+1][k+1] += dp[i][j][k];
                    //0,2~9
                    dp[1][j+1][k]   += dp[i][j][k]*9;
                }
                //未満flagが立っていない
                else {
                    if (S[j] == '1') {
                        //1
                        dp[0][j+1][k+1] += dp[i][j][k];
                        //0
                        dp[1][j+1][k] += dp[i][j][k];
                    }
                    else {
                        //S[j]を選んだ場合
                        dp[0][j+1][k] += dp[i][j][k];
                        if (S[j] != '0') {
                            //1
                            dp[1][j+1][k+1] += dp[i][j][k];
                            //0,2~(S[j]-1)
                            dp[1][j+1][k] += dp[i][j][k]*(S[j]-'1');
                        }
                    }
                }
            }
        }
    }
    //制約からしてintで十分
    int ans = 0;
    rep(MAX, j) ans += (dp[0][D][j] + dp[1][D][j])*j;
    cout << ans << endl;
}

int main(void){
  solve();
  return 0;
}

(リンク)

#最後に
今回が初投稿なので、色々拙い部分も目立ちますが、どうかご容赦ください
ミスなどあれば気軽に指摘してもらえると助かります
今後も印象に残った問題などをこんな風に記事にすることがあるかもしれません