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行)

SRM722の他の問題 Lv2 Lv3

広告

自己紹介

プログラミングとかUTAUとかドット絵とか
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

広告