ABC 030 D - 語呂合わせ ( Enumeration )

D: 語呂合わせ - AtCoder Beginner Contest 031 | AtCoder
Since there are only 9 s, each |s| within range [ 1, 3 ], we can enumerate in 3^9. Then check whether it is valid with O( N ).
Total ( 3^9 * N ).

const int MAXK = 9 + 1;
const int MAXN = 50 + 2;

int K, N;
string nums[ MAXN ], word[ MAXN ];

bool ok( int S, bool show ){
    int t = S;
    vi len( K );
    for( int i = 0; i < K; ++i )
        len[ i ] = S % 3 + 1,
        S /= 3;
    map< int, string > i2s;
    for( int i = 0; i < N; ++i ){
        int len_sum = 0;
        for( int j = 0; j < nums[ i ].size(); ++j )
            len_sum += len[ nums[ i ][ j ] - '0' - 1 ];
        if( len_sum != word[ i ].size() ) return false;
        for( int j = 0, k = 0; j < nums[ i ].size(); ++j ){
            int d = nums[ i ][ j ] - '0' - 1;
            string ns = word[ i ].substr( k, len[ d ] );
            if( i2s.count( d ) and i2s[ d ] != ns ) return false;
            i2s[ d ] = ns;
            k += len[ d ];
        }
    }
    if( show ){
        for( int i = 0; i < K; ++i )
            cout << i2s[ i ] << "\n";
    }
    return true;
}

void solve(){
    cin >> K >> N;
    for( int i = 0; i < N; ++i )
        cin >> nums[ i ] >> word[ i ];
    int S = 1; for( int i = 0; i < K; ++i ) S *= 3;
    for( int i = 0; i < S; ++i )
        if( ok( i, false ) )
            return ( void ) ok( i, true );
}