ABC196 C 解答

C - Doubled (244)

問題文

整数 N が与えられます。
以下の条件を満たす 1 以上 N 以下の整数 x は何個あるでしょうか？
・x の十進表記 (先頭に 0 を付けない) は偶数桁であり、その前半と後半は文字列として等しい。

制約

N は整数
 1 ≤ N < 10^12

考察

本問題の考え方として次の2つがあると思います。

・ N 以下の数において条件を満たすものを数え上げる。
・条件を満たす数のうち N 以下のものを数え上げる。

少々ややこしいですが、上の方法では N より小さい範囲で限定して条件を満たす数 x を数える、一方で下の方法では、とりあえず条件を満たす数 x を作ってからそれが N より小さいか判定する。

という感じです。

他の方の解法を見るに、上の方法ですとなかなかに場合分けが大変なことになりがちだと思われます。N の桁数が2桁、4桁、６桁、...と該当する桁ごとにifで分岐させる必要があり少しばかり大変です。

ですので、本記事では下の方法の説明をしていきます。

まずは、制約を気にせず時間をかければ正解のとなる方法を考えます。

条件は

x の十進表記 (先頭に 0 を付けない) は偶数桁であり、その前半と後半は文字列として等しい。

ですね。順番に見ていきます。

1, 2, 3, 4, ... ,10

ここまでは、全部ダメです。次の

11

でようやく条件を満たす数ができました。これが N 以下でしたらカウントしましょう。12, 13, ... とやっていって、次に条件を満たすのは 22 です。N 以下ならカウントします。

という感じで、これを 1 から N まで計算すれば答えが出ます。ここまでが、制約を気にしない解法です。ただし、N ≦ 10^12 です。このとき、xは最大で

999999999999 (9が12個)

ですので、間に合いません。工夫をしましょう。

今回必要なのは

x の十進表記 (先頭に 0 を付けない) は偶数桁であり、その前半と後半は文字列として等しい。

の条件を満たす数 x です。それ以外は必要ありません。ですので、条件を満たす数 x を効率的に作ってしまいましょう。

条件を満たす数を適当に並べます。

11, 22, 1010, 532532, 99999999

です。当然なのですが、この数を半分に分けた時にその前半部分と後半部分は一致してますね。

1|1
2|2
10|10
532|532
9999|9999

ですので、前半部分だけをfor文で探索して、条件を満たす数 x は「前半部分の後ろに同じものをくっつける」という操作で作りましょう。

数 x = 12341234 の場合
前半 = 1234
前半 + 後半 = 1234 | 1234 → 12341234
（＋が数学的に正しいかは置いておきます）

先程はfor文を1から10^12まで回していたのですが、この方法では前半部分だけを作れば良いので、10^6まで回せば全ての x が網羅できます。

10^6の最大値：999999 (9が6個)
10^12の最大値は9が12個だった。
9が6個ある数字を2個繋げれば12個になる

これなら間に合いそうですね。

最後に前半部分から数を作る方法です。これは次の式で可能です。

x = (前半部分）* 10 ^ (前半部分の桁数) +前半部分

例：123 (3桁)
x = 123 * 10 ^ 3 + 123
=123000 + 123
= 123123 

考察は以上です。桁数を求める際に若干定数倍がかかりますが、最大でも6桁ですので、十分間に合います。実装です。

実装

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
   ll n;
   cin >> n;
   ll ans = 0;
   for(ll i = 1;i <= (ll)1e6;++i)
   {
       ll cnt = 1;
       ll tmp = i;
       while(tmp>0)
       {
           tmp /=10;
           cnt*=10;
       }
       ll now = i * cnt + i;
       if(now <= n) ++ans;
   }
   cout << ans << endl; 
   return 0;
}

あとがき

x を作る時に10^(桁数)をしていますが、公式放送のように文字列を経由するともっと美しくかけると思います。

冒頭で、上の方法（N以下で条件を満たすものを数え上げる）は場合分けが多くなって大変と書きましたが、A問題同様、そちらの方が早く書けるのであれば問題ないと思います。前回のABC195Cで似たような問題が出題されたときには、私は場合分けを全部愚直に書きました。Aの繰り返しになりますが、はやく、バグなく、書ける方法が正解です。

ただし、コンテストの後にはきちんと賢い方法も学んでおくと後々の役に立つと思います。