SRM489 Div1 Easy BallConverter

問題

問題文

まずボールを $N$ 個選び機械に入れる。 ボールには 1 から $N$ までの整数に含まれるいずれかの番号がついている。 機械は 2 個のボールを選び、その番号が $i,j$ だとすると、番号が $convert(i,j)$ のボール 1 つに変換する。 これをボールが 1 個だけになるまで繰り返す。

最初のボールの選び方に対し、変換の方法にかかわらず最後のボールがの番号が一意に定まるとき、この機械は “Good” であり、 そうでない場合は “Bad” であるとする。

$convert$ が行列で与えられる。“Good” か “Bad” かを判定せよ。

方針

分からなかったのでカンニングした。

変換を2項演算と考えて、それに結合法則が成り立つかで判定できる。 つまり、任意の 3 個のボールに対して $convert(convert(i,j),k) = convert(i,convert(j,k))$ が成り立つか調べる。 結合法則が成り立つ集合を半群というらしい。(他にも要件はありそう)

実装

class BallsConverter {
public:
    string theGood( vector <string> convert ) {
        int n = convert.size();
        vvi m(n,vi(n));
        rep(i,n)rep(j,n) m[i][j] = [](char c){
            if(isupper(c)) return c-'A';
            else return 26 + c-'a';
        }(convert[i][j]);
        bool ok = true;
        rep(i,n)rep(j,n)rep(k,n) if(m[m[i][j]][k] != m[i][m[j][k]]) ok = false;
        return ok ? "Good" : "Bad";
    }
};