yukicoder No.2607 Add One Digit 解説

問題文

解説

setを使った方針で進めていく。
$N$ を文字列にして入力しておいて、毎回insertする（stringのinsert関数についてはここでは説明しない）。
setでこれまでの操作でできた文字列をinsertしていけば、答えはsetのsizeとなる。
$N$ の桁数を $K$ としたとき、stringのinsertがボトルネックとなり $O(K^2)$ で求まる。
なお、実装時には先頭が0であるような文字列を候補に入れないことに注意。

解答例

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

int main(){
  string n;cin>>n;
  set<string> ans;
  for(int i=0;i<=n.size();i++)
    for(int j=(i==0);j<10;j++){
      string s=n;
      s.insert(s.begin()+i,j+'0');
      ans.insert(s);
    }
  cout<<ans.size()<<endl;
}