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

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

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

いわゆる、 O(\sqrt{N}) まで調べれば十分というタイプの問題だね。最近そのタイプの問題が流行っている気がする!

問題概要

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

 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;
}