zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC114-C「755」です。
ポイント
全探索は全探索でも，少し工夫をする問題です。単純な全探索では，与えられた$N$以下の整数を全て列挙して条件に当てはまる数を探していけばよさそうです。しかし，今回は$N$が最大で$10^9$であり，少し間に合いません。
そこで，今回は整数の桁数に注目している問題ですので「整数の各桁に対して」全探索を行うという方針にします。すると，各桁の候補は「7,5,3,0」の4種類しかありませんので，最大9桁に対して考えるべき整数は$4^9=262144$程度しかありません。十分間に合いそうです。
問題となるのは，各桁に「7,5,3,(0)」の候補をどのように当てはめていくかという点です（0は先頭につけるだけ）。例えば，bit全探索を利用すれば，2つの候補に対しては簡単に全探索を行うことができます。ここでは，再帰関数を利用することでbit全探索の4bitバージョンを考えていきたいと思います。細かいコメントは実装の中に挿入していきます。
おさえるべき内容
bit全探索の拡張としての再帰関数
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;
ll N;
// ここから再帰関数
int rec(string S, ll N){
// Sに候補となる整数を用意していく
// もし考えている候補SがNよりも大きければ条件を満たさない
if (stol(S) > N) return 0;
// 7,5,3の全てが使われているかチェックする
bool check_7 = false;
bool check_5 = false;
bool check_3 = false;
rep(i, S.size()){
if (S[i]=='7') check_7 = true;
else if (S[i]=='5') check_5 = true;
else if (S[i]=='3') check_3 = true;
}
// 再帰関数の返り値
int res;
// もし7,5,3全てが出現していれば条件に当てはまる整数が見つかったので res=1 とする
if (check_7 && check_5 && check_3) res = 1;
// もし7,5,3全てが出現していなければ条件に当てはまる整数が見つからなかったので res=0 とする
else res = 0;
// いま考えているSの末尾に7,5,3をくっつけて再帰関数を実行する
// 例えばSが7753であれば，次は「77537」「77535」「77533」のそれぞれを考えることになる
res += rec(S + "7", N);
res += rec(S + "5", N);
res += rec(S + "3", N);
// 返り値はres
return res;
}
int main(){
cin >> N;
// 初期値は0とする
// Sとして「07753」のように先頭に0がつくがresの計算やstoiには関係ないのでOK
cout << rec("0", N) << endl;
}
コメント