AtCoder ARC #027 : A - 門限、B - 大事な数なのでZ回書きまLた。

ARC027に参加。
AでFirst Accept取ったのはいいけど、B,CでもたついてDは部分点どまりでした。
http://arc027.contest.atcoder.jp/tasks/arc027_1
http://arc027.contest.atcoder.jp/tasks/arc027_2

A - 門限

現在時刻が何時何分か与えられるので、18時まであと何分か答えよ。
時刻を分換算して18*60から引けばよい。

void solve() {
	int H,M;
	cin>>H>>M;
	cout << 18*60-H*60-M << endl;
}

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

N桁の数字がある。
この数字を覆面算の要領でいくつかの桁をアルファベットで隠し、2回表記した。
この数字としてあり得るものは何通りあるか答えよ。

まず、2つの表記で同じ桁に2回アルファベットが登場した場合、それらは同じ数字でなければならない。
よってUnion-findを使ってアルファベット群をまとめて管理していく。
あとはそれぞれ以下のように処理していく。

• 2つの表記のうち片方数字・片方アルファベットの桁がある場合、そのアルファベット群の数値は一意に決まる。
• それ以外のアルファベット群は未定なので10通り考えられる。ただし先頭桁に関しては0は取れないので9通りのみ。

int N;
string S1,S2;
int mask[256],on[256];

class UF {
	public:
	static const int ufmax=10002;
	int ufpar[ufmax],ufrank[ufmax],ufcnt[ufmax];
	UF() { init();}
	void init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; ufcnt[i]=1; } }
	int find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = find(ufpar[x]));}
	int operator[](int x) {return find(x);}
	int count(int x) {return ufcnt[x];}
	void unite(int x,int y) {
		x = find(x); y = find(y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y, ufcnt[y]+=ufcnt[x];
		else {ufpar[y]=x; ufcnt[x]+=ufcnt[y]; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

void solve() {
	int f,i,j,k,l,x,y;
	UF uf;
	
	cin>>N>>S1>>S2;
	
	FOR(i,N) if(isalpha(S1[i])) on[S1[i]]++;
	FOR(i,N) if(isalpha(S2[i])) on[S2[i]]++;
	FOR(i,N) if(isalpha(S1[i]) && isalpha(S2[i])) uf.unite(S1[i],S2[i]);
	
	FOR(i,256) mask[i]=10;
	if(isalpha(S1[0])) mask[uf[S1[0]]] = 9;
	if(isalpha(S2[0])) mask[uf[S2[0]]] = 9;
	
	FOR(i,N) {
		if(isdigit(S1[i]) && isalpha(S2[i])) mask[uf[S2[i]]] = 1;
		if(isdigit(S2[i]) && isalpha(S1[i])) mask[uf[S1[i]]] = 1;
	}
	
	ll ret=1;
	FOR(i,256) if(on[i] && uf[i]==i) ret *= mask[i];
	cout << ret << endl;
}

まとめ

今までに比べてBが難しめ。