問題概要

十進法表記で偶数桁で、かつ、その前半と後半とが文字列として等しいようなものを「良い整数」と呼ぶことにします。

$1$ 以上 $N$ 以下の整数のうち、「良い整数」が何個あるかを求めよ。

制約

$1 \le N \lt 10^{12}$

考えたこと

一見すると、 $1$ から $N$ までループを回して、「良い整数」が何個あるかを調べないといけないように感じてしまう。その場合の計算量は $O(N \log N)$ となる (整数 $n$ が良い整数かどうかの判定は $O(\log n)$ かかる)。

このままでは間に合わない。

しかしよく考えてみると、たとえば 1234512345 は「良い整数」だが、これは「12345」という整数と同一視できる。つまり、良い整数はその情報を失わずに、より小さい整数に情報を圧縮できるのだ。

よって、このように圧縮した整数の方を全探索すればよいことに気づく。つまり、

1 番目：11
2 番目：22
3 番目：33
...
9 番目：99
10 番目：1010
11 番目：1111
12 番目：1212
...
99 番目：9999
100 番目：100100
...

という風に良い整数は列挙できる。これが $N$ を超えるまでやっていく感じ。最悪でも 100000 までやれば十分 (100000100000 は $10^{12}$ より大きい) なので、全探索で間に合う。

なお、 $n$ 番目の「良い整数」を求める関数は、たとえば次のように実装できる。

long long reconstruct(long long n) {
    long long val = 1, nn = n;
    while (nn) {
        val *= 10;
        nn /= 10;
    }
    return n * val + n;
}

この関数は、次のようなことをしている

n = 12345 であるとき、
その桁数を $d$ として val = $10^{d}$ とする (val = 100000 となる)
求める整数は n * val + n で求められる (1234512345 になる)

コード

#include <bits/stdc++.h>
using namespace std;

long long reconstruct(long long n) {
    long long val = 1, nn = n;
    while (nn) {
        val *= 10;
        nn /= 10;
    }
    return n * val + n;
}

int main() {
    long long N;
    cin >> N;
    long long res = 0;
    for (long long n = 1; n <= 1000000; ++n) {
        if (reconstruct(n) <= N) ++res;
        else break;
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 196 C - Doubled (灰色, 300 点)

問題概要

制約

考えたこと

コード