ABC110-C 備忘録 p.29

itsukiです。
AtCoderの過去問を解いた様子です。解説記事ではありません。

C - String Transformation

考察の流れ

異なる文字 c_1, c_2 を選んで、
S に含まれる "すべての" c_1 を c_2 へ、c_2 を c_1 へ、ということは…

T では同じ文字なのに、S で同位置にある文字の種類がバラバラだとダメ？
例えば下記の場合、T[0], T[7] どらも r なのに、S[0] が c で S[7] が i
S = chokudai　→　ci, ha, od
T = redcoder　→　rr, ee, dd

逆に、
S では同じ文字なのに、T で同位置にある文字の種類がバラバラでもダメ？
例えば下記の場合、S[1], S[6] どらも e なのに、T[1] が h、T[6] が a
S = redcoder　→　rr, ee, dd
T = chokudai　→　ci, ha, od

全探索してると間に合わない
配列（例えば db[26] ）を作って、S[i] に対応する T[i] が必ず一対一になるかをチェックすれば良さそう

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Yes()       printf("Yes\n")
#define No()        printf("No\n")

int main(){
	char s[200001]={0}, t[200001]={0}, db[27]={0};
	scanf("%s%s",s,t);
	for(int i=0; i<strlen(s); i++){
		if	   ( db[s[i]-'a']==t[i] ){ continue; }
		else if( db[s[i]-'a']==0	){ db[s[i]-'a'] = t[i]; }
		else						 { No(); return 0; }
	}
	qsort( db, 26, sizeof(char), strcmp );
	for(int i=0; i<26; i++){
		if( db[i]!=0 && db[i]==db[i+1] ){ No(); return 0; }
	}
	Yes();
 	return 0;
}

まとめ

・解説をみて、自分が長々と考えていたことはこんなに簡単に表現できるのかと感動
・解説：S_i=S_j ならば、T_i=T_j である。T_i=T_j ならば、S_i=S_j である (!)

引き続き、のんびり精進します。

#備忘録 #AtCoder #ABC #競技プログラミング #競プロ #C言語