ARC027 B - 大事な数なのでZ回書きまLた。

B - 大事な数なのでZ回書きまLた。

概要

数字と英大文字からなる長さNの文字列が2つ与えられる。2つの文字列中の数字と英大文字は下記の特徴がある。

• 2つの文字列は同じN桁の数字を表したものである。
• 2つの文字列の同じ位置の文字を見たとき、片方が英大文字で片方が数字であれば、その英大文字がその数字を表すことを意味する。
• 2つの文字列に現れる英大文字はどちらの文字列に現れても同じ数字を表す。
• 異なる英大文字が同じ数字を表すこともある。

2つの文字列が表すN桁の数字としてあり得るものの全ての個数を求めよ。

制約

1 <= N <= 18

方針

Union-Find木を使う。ノードは英大文字、数字(それぞれAsciiコードに対応)、およびその桁の数字が確定していることを示す特殊ノード(256)を用いる。

まず、2つの文字列の各桁の文字をUniteしてゆく。このとき少なくともどちらかが数字であれば、特殊ノードとUniteする。
その後2つの文字列の各桁を見てゆく。特殊ノードとUniteされていなければ数字が確定していないため、その桁の数字は10通り(文字列の先頭なら9通り)の可能性があり、それをかけ合わせてゆく。

一度見た桁は数字が確定するのでその時点で特殊ノードとUniteする。また、最初に2つの文字列をUniteしているため、確認するのは片方の文字列だけでよい。

感想

りかさんのブログを参考にしました。
wk1080id.hatenablog.com

解答

Submission #4399603 - AtCoder Regular Contest 027

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
// union-find tree
 
const int max_n = 300;
 
int par[max_n];
int rnk[max_n];
 
void init(int n){
	rep(i,n){
		par[i] = i;
		rnk[i] = 0;
	}
}
 
// find root of tree with x
int find(int x){
	if(par[x] == x) return x;
	else return par[x] = find(par[x]);
}
 
void unite(int x, int y){
	x = find(x);
	y = find(y);
	if(x == y) return;
 
	if(rnk[x] < rnk[y]) par[x] = y;
	else{
		par[y] = x;
		if(rnk[x] == rnk[y]) rnk[x]++;
	}
}
 
bool same(int x, int y){
	return find(x) == find(y);
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N;
	cin >> N;
 
	string s1, s2;
	cin >> s1 >> s2;
 
	init(300);
	int num = 256;
 
	for(int i = 0; i < N; i++){
		if(isdigit(s1[i]) || isdigit(s2[i])){
			unite(s1[i], num);
			unite(s2[i], num);
		}else{
			unite(s1[i], s2[i]);
		}
	}
 
	ll ans = 1;
	for(int i = 0; i < N; i++){
		if(find(s1[i]) != find(num)){
			if(i == 0){
				ans *= 9;
			}else{
				ans *= 10;
			}
 
			unite(s1[i], num);
		}
	}
 
	cout << ans << endl;
}