hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

AtCoder Beginner Contest 029 D: 1

問題概要

原文 → 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のメモ帳