SRM722 Lv1 : TCPhoneHome
作成日：2017.10.13
最終更新日：2017.10.13
問題概要
$digits$桁の電話番号のうち、$n$個ある$specialPrefixes$(以下$S$とする)のいずれでも始まらないものはいくつあるかを求めよ。
制約
$1 \leq digits \leq 17$
$0 \leq n \leq 50$
$S$は互いに異なる
考え方
$n=0$ならば答えは$10^{digits}$である。
そうでない時、$10^{digits}$から$S$で始まる電話番号の数を引けば良い。
すなわち、$S$それぞれについてその桁数を$d_i$とすると$10^{digits-d_i}$を引けば良い。
但し$S$に$1$と$12$のように片方がもう片方の接頭辞になっているものが含まれている時に重複して引かないように注意する。
ソースコード
マクロ等はこちら
class TCPhoneHome {
LL p[18]; //10^i
public:
long long validNumbers(int digits, vector<string> specialPrefixes) {
p[0] = 1;
repp(i,1,18) p[i] = p[i-1] * 10;
LL ans = p[digits];
vector<string> S = specialPrefixes;
if((int)S.size() == 0) return ans;
sort(S.begin(),S.end());
ans -= p[digits-(int)S[0].size()];
int x = 0;
repp(i,1,S.size()){
bool b = 1;
repp(j,0,S[x].size()){
if(j == (int)S[i].size()) break;
if(S[x][j] != S[i][j]) break;
if(j+1 == (int)S[x].size()) b = 0;
}
if(b){
ans -= p[digits-(int)S[i].size()];
x = i;
}
}
return ans;
}
};解法まとめ
$10^{digits}$から$S$の各要素の桁数を$d_i$として$10^{digits-d_i}$だけ引く。(7-24行)
但し、$S$の要素のうち自身の接頭辞が$S$に含まれているものは無視する。(14-19行)