ABC198 B 解答

B - Palindrome with leading zeros(58)

問題文

整数 N が与えられます。N を十進法で表した文字列の先頭に
0 個以上の 0 をつけることで、回文にすることはできますか？

制約

0 ≤ N ≤ 10^9

考察

まず、可能な操作についてです。回文を作るために私たちができるのは

数字の先頭に0をつける

ただこれだけです。となると、作れる回文の種類も自ずと絞れてきます。

10 →  010
121000 → 000121000

当たり前ですが、先頭に0をいくつかつけたものが回文のとなります(ならない場合もあります。)

ここで制約に注目すると

N ≦ 10^9

ですね。

1000000000

こいつです。こいつが最大のケースになります。つまり、回文判定のために最も多く0をつけなければならない数(入力 N )です。

この場合には先頭に0を9個つけると回文になります。

ですので、どんな場合においても0を9個つければ回文かどうかを判断することができます。逆にいうと、0を9個つけても回文にならないものは、どうやっても回文になりません。

これなら全部試せそうです。
ですので、以下の通りにやるとACがもらえます。

1、回文かどうか判定
2、回文:Yes 回文じゃない:0をつける
3、0が10個以上:No
     9個以下: 1に戻る

注意点として0をつけなくても回文になっている場合がありますので、まずはチェックをしましょう。

最後に0の加え方について。まず入力を数字ではなく、文字列で受け取りましょう。string 型の先頭に0をつけるのはちょっと大変なので、思い切って文字列を反転させましょう。回文かどうかを判定するだけなら問題ありません。先頭に加える操作は、反転したものの末尾に加える操作と一致するので、無事0を加えることができました。

細かな点はコメントアウトで補足していますので、そちらもご覧ください。

実装

 #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()
{
   //文字列で受け取る
   string n;
   cin >> n;
   //反転する
   reverse(n.begin(),n.end());
   //回文が作れるかどうか
   bool ok = false;
   //とりあえず15回まわしとく（10回で十分）
   rep(i,15)
   {
       bool tok = true;
       //まず判定をする
       rep(j,n.size())
       {
           if(n[j] != n[n.size()-1-j]) tok = false;
       }
       if(tok) ok = true;
       //0を加える
       n += '0'; 
   }
   if(ok) cout << "Yes" << endl;
   else cout << "No" << endl;

   return 0;
}

あとがき

回文のチェックは前と後ろから一つずつ見ましたが、「反転させた文字列が完全に一致するか」でできるみたいですね。スマートです。

また、0をいくつか加えて回文を作る。ですので、ようは元の文字列の末尾に0がいくつあるかが重要なわけです。ということで、末尾の0を全て取っ払ったものが回文になっているかで判定することも可能みたいです。これもまたスマートです。