Comma [パナソニックプログラミングコンテスト（AtCoder Beginner Contest 195） C]

https://atcoder.jp/contests/abc195/tasks/abc195_c

解説

https://atcoder.jp/contests/abc195/submissions/20908056 状況が同じものをまとめながら数え上げる問題。

基本考察

1からNに順番に数え上げていくと、
1～999はコンマ0個
1000～999999はコンマ1個
…
みたいになる。
グループ分けをすると、1,000,000,000,000,000でコンマ5個まである。
グループは5つなので、このグループについて範囲を確認して数えていけばいい。

自分の実装

※ [L,R)はL以上R未満という意味

[1,10) -> comma 0
[10,100) -> comma 0
[100,1000) -> comma 0
[1000,10000) -> comma 1
[10000,100000) -> comma 1
[100000,1000000) -> comma 1
[1000000,10000000) -> comma 2

のような感じで[L,R)のLもRも10倍すれば、次の桁数での場合を考えることができる。
commaの数は3回に1回インクリメントすれば合う。

[L,R)において、R≦Nであれば、[L,R)はすべて対象となるので、すべてのコンマを足し合わせる。
L≦N＜Rであれば、L～Nは対象となるので、その部分のコンマを足し合わせる。
そうでないなら、範囲外なので無視。

これで総和を取ってこたえる。

ll N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    int comma = 0;
    ll ans = 0;
    ll L = 1, R = 10;
    rep(i, 0, 16) {
        if (R <= N) ans += (R - L) * comma;
        else if(L <= N && N < R) ans += (N - L + 1) * comma;

        L *= 10;
        R *= 10;
        if (i % 3 == 2) comma++;
    }
    cout << ans << endl;
}