ARC027 B 大事な数なのでZ回書きまLた。
問題概要
2つの文字列が与えられる。同じアルファベットは同じ数字を表し、異なるアルファベットは異なる数字を表す場合と同じ数字を表す場合がある。2つの文字列が同じ 桁の数を表すとき、その数は何通りあるか。
制約
解法
アルファベットをUnion Findを使って管理する。
各桁の文字において、両方共が数字の場合は無視して良い。
片方が数字の場合は、もう片方のアルファベットは数字が固定されるため、そのアルファベットのとりうる値は1通りしかないので、アルファベットに使われることのないある数(numとする)を用意して、その数にuniteする。
両方がアルファベットの場合は、それらのアルファベットは同じ数字を表すため、uniteする。
あとは、片方の文字列を最初から見て、そのアルファベットがnumにつながっていたら(すでにuniteしていたら)、その桁のとりうる数字は1通りしかないので何もしない。numにつながっていなかったら(uniteされてなくて親が違ったら)、そのアルファベットは10通り(文字列の先頭ならば9通り)の数字をとるので、答えにかけあわせる。そしてそのアルファベットは値を決めたとして、numにuniteする。