SRM489 Div1 Easy(300) BallsConverter

TopCoder

BallsConverter

ボールが３個の場合について試せば良い。(a+b)+c=a+(b+c)が成り立つならばa+b+……+zが一意になるのと同じことで数学的帰納法で証明できる、らしい。わかるようなわからないような……。

#include <string>
#include <vector>
using namespace std;

class BallsConverter{public:
string theGood( vector <string> convert )
{
    int N = (int)convert.size();

    vector<vector<int> > conv( N, vector<int>( N ) );
    for ( int i=0; i<N; i++ )
    for ( int j=0; j<N; j++ )
        if ( convert[i][j] <= 'Z' )
            conv[i][j] = convert[i][j] - 'A';
        else
            conv[i][j] = convert[i][j] - 'a' + 26;

    for ( int i=0; i<N; i++ )
    for ( int j=0; j<N; j++ )
    for ( int k=0; k<N; k++ )
        if ( conv[conv[i][j]][k] != conv[i][conv[j][k]] )
            return "Bad";
    
    return "Good";
}};