Doubled [AtCoder Beginner Contest 196 C]

https://atcoder.jp/contests/abc196/tasks/abc196_c

解説

https://atcoder.jp/contests/abc196/submissions/21118718 全探索をすると10¹²通りあるので、これは難しい。

余談、経験則

10¹²通りというのは中途半端な気がしないだろうか。
これの平方根を取ると10⁶となり、全探索可能な範囲に収まる。
10¹²通りというのはしばしばO(sqrt(N))となることがある。
今回もそう。

後半だけ全列挙

条件を満たす整数はAAABBBと表記されたときに、AAA=BBBとなるものとなっている。
条件を満たす整数を効率良く全列挙したいと考えたときに、片方だけ全列挙すればもう片方はその値で確定してしまう。
よって、10¹²桁の数があったとしても後半だけを全列挙すればいいので、10⁶通りの全列挙にすることができた。

あとは、後半から前半を作って、数xを作った後、N以下であるものを判定していけばいい。
後半部分から数xを作る部分が少し面倒なのだが、多少計算量をサボっても問題ない。

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

    int ans = 0;
    rep(post, 1, 1010101) {
        ll pre = post;

        string s = to_string(post);
        int digits = s.length();
        rep(_, 0, digits) pre *= 10;

        ll x = pre + post;

        if (x <= N) ans++;
        else break;
    }
    cout << ans << endl;
}