問題概要

原文 → D: 1 - AtCoder Beginner Contest 029 | AtCoder

$1 \leqq N \lt 10^{9}$ である十進表記の自然数Nが与えられる。1からNまで書きくだす時、1という数字を何回書いたかを求めよ。

数学解法

解説

ナイーブな解法(部分点解法)はここで解説してもしょうがないので略。

桁DPで解いてる方もちらほらいるみたいだけど、私は公式の解説の方針でやりました。ただ公式解説にソースコード載ってないので、補足みたいな感じで解説します。

0から順番に数字を書き下した時を考える。(0から書き下しても1から書き下しても答えは同じ)

下から数えて $i$ 桁目は、長さ $10^{i}$ のパターンが続くことが分かり、さらにそのパターン内に「1」は $10^{i-1}$ 個含まれていることが分かる。
例: 下から1桁目 → 01234567890123…

パターンの長さは $10 (10^{1})$ 個
パターンに含まれる「1」の数は $1 (10^{0})$ 個

例:下から2桁目 → 000000000011111111112222222222…999999999900000000001111…

パターンの長さは $100 (10^{2})$ 個
パターンに含まれる「1」の数は $10 (10^{1})$ 個

なので、各桁について

パターンは何回続いたか
最後に、パターンの先頭から何個の数字が並んだか

の情報がわかれば良い。

パターンは何回続いたか

これはパターンの長さが $10^{i}$ であることから、 $\frac{n}{10^{i}}$ で計算できることがわかる。

最後に、パターンの先頭から何個の数字が並んだか

ここの条件分岐が若干面倒かも。

$i$ 桁目のパターンの中に、1は $10^{i-1}$ 個含まれるが、1は連続して登場し、何番目から何番目の間に登場するかも計算可能である。
パターン中に1が $10^{i-1}$ 個含まれるということは、当然他の数字も同じ数だけ含まれるため、1の前に登場する「0」も $10^{i-1}$ 個含まれる。
このことから、 $i$ 桁目のパターンにおいて、1は $10^{i-1} + 1$ 番目から $2 \times 10^{i-1}$ 番目の間に登場することが分かる。

以上のことから、 $b =$ ( $n$ を $10^{i}$ で割った余り)としたとき、最後のパターン中に出てくる1の数は次のように計算できる。

$2 \times 10^{i-1} \lt b$ を満たすなら、1は $10^{i-1}$ 回登場した
$10^{i-1} + 1 \leqq b \leqq 2 \times 10^{i-1}$ を満たすなら、1は $b - 10^{i-1} + 1$ 回登場した
$b \lt 10^{i-1} + 1$ を満たすなら、1は1回も登場していない

ソースコード

#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a; i<n; i++)
using namespace std;
typedef long long int ll;

int main() {
    ll n; cin >> n;
    ll m = n;
    ll digit = 0;
    // 何桁なのかを計算
    while(m != 0) {
        m /= 10;
        digit++;
    }
    
    ll ret = 0;
    rep(i,1,digit+1) {
        ll a = (n / (ll)pow(10,i)) * (ll)pow(10, i-1);
        ll b = n % (ll)pow(10,i);
        if(b >= 2 * (ll)pow(10,i-1)) b = pow(10,i-1);
        else if(b < (ll)pow(10,i-1)) b = 0;
        else b = b - (ll)pow(10,i-1) + 1;
        ret += (a + b);
    }
    cout << ret << endl;
    return 0;
}

ちなみに、数の制約が $1 \leqq N \lt 10^{9}$ で答えの最大値が900000000なので、long long intにする必要はありません(あとから直すのが面倒だったのでそのままにしてあるだけ)

桁 DP 解法

2017/07/25 追記: ふと気になったのでこちらの解法も追加しました。

解説

DP 配列を 2 つ用意します。

dp[i][j] := i 桁目まで見たとき、元の数字未満確定 flag が j であることを満たす数の総数

dp2[i][j] := i 桁目まで見たとき、元の数字未満確定 flag が j であることを満たす数を全て書いた時に登場した 1 の総数

1 つめの DP はよく出てきますが、困るのは 2 番目です。これをどうやって求めよう？というところが鍵です。

$i$ 桁目で $1$ を書いたかどうかで場合分けをしましょう。

$i$ 桁目で $1$ 以外の数字を書いた場合

このとき、 $i$ 桁目によって総数が増えることはなく、 $i-1$ 桁目までの 1 の総数を伝搬させるだけで良いです。

$i$ 桁目で $1$ を書いた場合

上の時と同様、 $i-1$ 桁目までの 1 の総数を伝搬させます。

1 を書くとき、総数は増えます。具体的にどれだけ増えるかというと、 $i-1$ 桁目まで書いた時に登場した数字の個数分増えます。したがって、1 つ目の DP 配列を使ってその分を足せば良いです。

ソースコード

int dp[15][2], dp2[15][2];

signed main() {
    string s; cin >> s;

    int N = s.length(), ans = 0;
    dp[0][0] = 1;
    rep(i,0,N) rep(j,0,2) {
        int lim = (j ? 9 : s[i] - '0');
        rep(x,0,lim+1) {
            dp[i+1][j||x<lim] += dp[i][j];
            dp2[i+1][j||x<lim] += dp2[i][j];
            if(x == 1) dp2[i+1][j||x<lim] += dp[i][j];
        }
    }
    ans = dp2[N][0] + dp2[N][1];
    cout << ans << endl;
    return 0;
}

配列が 2 つにまたがるような DP は未だにすんなり書けませんね。今回もかなり手間取りました。

ちなみにdp[i][j][k] := i 桁目まで見て、元の数未満確定 flag が j で、1 を k 回書く数字の総数 という方針でも解くことができ、この方が DP 配列が 1 つしかいらないため少し簡単です。以下に参考になるブログを貼っておきます。

ABC 029 D - 1 - srupのメモ帳

hogecoder

tsutaj 競技プログラミングの記録

AtCoder Beginner Contest 029 D: 1

問題概要

数学解法