Posted at

atcoder ABC114 C問題

ABC114 C問題の解法をメモ

方針は合っていたが、数の列挙ができなかった。

https://atcoder.jp/contests/abc115/tasks/abc115_c


考え方

明らかにNまでの全ての整数に対し、七五三数かどうか判別するのはTLEになるので、別の方法を考える。ここで、七五三数の定義を確認すると3,5,7からのみ構成され、なおかつ3,5,7が全て最低でも一つは含まれている数である。このことから3,5,7のみで構成される数の個数は最大で3の9乗である(Nが9桁の時)。よって3,5,7のみで構成される数を列挙し、それらに対し、3,5,7を全て最低でも一つずつ含んでいるかを判別することで、七五三数をカウントすれば良い。ちなみに計算量は(3のN乗 * 9)だと考えられる(自信ないです)

ちなみに、3,5,7で構成される数の列挙は再帰的に書くと次のようになる


static void dfs(long x){

if(x > n){
return;
}
if(check(x)){
ans++;
}
dfs(10*x + 3);
dfs(10*x + 5);
dfs(10*x + 7);
}

static boolean check(long x){
String mozi = String.valueOf(x);
if(mozi.contains("3") && mozi.contains("5" )&& mozi.contains("7")){
return true;
}else{
return false;

}
}