読者です 読者をやめる 読者になる 読者になる

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にする必要はありません(あとから直すのが面倒だったのでそのままにしてあるだけ)