ARC058-C こだわり者いろはちゃん

問題

C - こだわり者いろはちゃん / Iroha's Obsession

考察

10進法表記で嫌いな数字が出ないようにしたい。N<10000なのでforループで実装できる？

ここで、Nが制約を満たすときの支払う金額の最大値を考える。N=9999,D[]={0,1,2,3,4,5,6,7,9}のとき、支払う金額は88888となり(恐らく)これが最悪の場合である。よって支払う金額はせいぜいO(10N)(100,000通り)未満。なのでNからスタートして条件を満たす数をforループで探せば間に合う。

for(int i=N; ; i++)として、iが条件を満たすかどうか判定する。これは10で割った余りを求めて10で割ってを繰り返せばよい。一桁一桁を嫌いな数字かどうか照らし合わせてlogN通り。上のforループと組み合わせてO(NlogN)程度で間に合う。

コード

#include<iostream>
using namespace std;

int N,K;
bool ng[11];

int main(){
    cin>>N>>K;
    for(int i=0; i<K; i++){
        int t;
        cin>>t;
        ng[t]=true;
    }
    
    for(int i=N; ; i++){
        int a=i;
        while(1){
            int d=a%10;
            if(ng[d]) break;
            a/=10;
            if(a==0){
                cout<<i<<endl;
                return 0;
            }
        }
    }
    
    return 0;
}