kmjp's blog

競技プログラミング参加記です

Codeforces #434 Div1 B. Polycarp's phone book

なんだこりゃ。
http://codeforces.com/contest/860/problem/B

問題

N個の電話番号(9桁の数字)が与えられる。
これらは互いに異なる。

各番号を文字列とみなしたとき、その部分文字列のうち、他の電話番号がその部分文字列を含まないような最短の文字列を答えよ。

解法

先に全ての部分文字列の登場回数を列挙しておこう。
各電話番号に対し、その部分文字列の登場回数が自身以外にあるかどうかを判定すればよい。

int N;
string S[70707];
int num[70707][10][10];
map<int,int> M[10];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>S[i];
		for(int l=1;l<=9;l++) {
			for(x=0;x+l<=9;x++) {
				num[i][x][l]=stoi(S[i].substr(x,l).c_str());
				M[l][num[i][x][l]]++;
			}
		}
	}
	
	FOR(i,N) {
		for(int l=1;l<=9;l++) {
			int ret=-1;
			for(x=0;x+l<=9;x++) if(--M[l][num[i][x][l]]==0) ret=x;
			for(x=0;x+l<=9;x++) ++M[l][num[i][x][l]];
			
			if(ret>=0) {
				cout<<S[i].substr(ret,l)<<endl;
				break;
			}
		}
	}
}

まとめ

なんか今回のA,Bは面白味がないな…。