WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM567 Div1 Medium "StringGame"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12378

マナオは"String Game"と呼ばれる、奇妙な2人用ゲームを考案した。このゲームは小文字のアルファベットで構成される文字列のセットを使って遊ぶ。

まず始めに、先攻プレイヤーがそのセットから文字列Xを選び、好きなように文字を並べ替える。さらに、アルファベットの順列(a-zが一文字ずつあるもの)を紙に書き出す。その後、後攻プレイヤーはX以外のセットの文字列それぞれで文字を好きなように並べ替えていく。そして、Xとその他の文字列それぞれを、アルファべットの順列を使った辞書順で比較していく。もし他の文字列よりもXが小さければ先攻の勝ち、そうでなければ後攻の勝ちとなる。

2つの異なる文字列A, Bを比較するためには、それらの文字列において、違う文字が出現する最初の場所を見つける必要がある。A, Bのそのような場所の文字をa, bとする。もしアルファベットの順列において、bよりaが前にあればAは辞書順でBより小さく、そうでなければBは辞書順でAより小さいとする。例えば、アルファベットの順列が{b, a, c, d, ... z}であったとき、"aba"は辞書順で"aab"より小さい。なぜなら'b'は'a'よりも順列において前にあるからである。

あなたは"String Game"で使われる文字列のセットSが与えられる。各文字列において、それを先攻プレイヤーが選んだときに、両者が最善を尽くすとして、先攻プレイヤーが勝てるかどうかを判断せよ。それはつまり、先攻プレイヤーは選んだ文字列Xの文字の並べ替えと、アルファベットの順列の選択に最善をつくし、後攻プレイヤーはX以外の全ての文字列の並べ替えに最善をつくすとする。

制約

2 <= S <= 50
1 <= S[i].length <= 50



考えた事

例)
S = aaabbb, aaaccc, aabbcc

文字列Xと順列のアルファベットは、同じ順番で並べないとダメ。

(先攻)つ"aaabbb"  (先攻)つ{ b, a, c, ... } ←食い違っている
(後攻)つ"bbaacc"

文字列Xの文字は、他の文字列の文字の数より大きいか等しいものでないとダメ

(先攻)つ"aabbcc" (先攻)つ{ a, b, c, ... }
(後攻)つ"aaabbb"

ある文字が置かれたときに、文字列Xの文字の数よりも小さい文字列は脱落

(先攻)つ"aaabbb"  (先攻)つ{ a, b, c, ... }
(後攻)ノ コレジャムリッ! ---===≡≡≡"aabbcc"

要は、Xを並べ替えるときに、他の文字列より数の多い、または等しい文字を置いていく。
その文字の数が文字列Xより少ない文字列は抜かしていく。
文字列が無くなったら先攻の勝ち。
おける文字が無くなったら後攻の勝ち


ソースコード

int N, M;
int cn[55][26];
bool rem[55];

class StringGame {
public:

    bool solve( int id ){

        int remNum = N - 1;
        memset( rem, true, sizeof(rem) );

        while( remNum > 0 ){
            bool update = false;
            // 他の文字列と比べ、全て数が大きいか等しい文字を選ぶ
            for( int c = 0; c < 26; c++ ){
                bool ok = true;
                for( int j = 0; j < N; j++ ){
                    if( j == id || !rem[j] ) continue;
                    if( cn[id][c] < cn[j][c] ){
                        ok = false;
                    }
                }

                if( !ok ) continue;

                // その文字で数が小さい文字列は消す
                for( int j = 0; j < N; j++ ){
                    if( j == id || !rem[j] ) continue;
                    if( cn[j][c] < cn[id][c] ){
                        rem[j] = false;
                        remNum--;
                        update = true;
                    }
                }
            }

            // そのような文字列がなければダメ
            if( !update ) return false;
        }
        return true;
    }

    vector <int> getWinningStrings(vector <string> S){
        N = S.size();
        M = S[0].length();

        // cn初期化
        memset( cn, 0, sizeof(cn) );
        for( int i = 0; i < N; i++ ){
            for( int j = 0; j < M; j++ ){
                cn[i][ S[i][j] - 'a' ]++;
            }
        }

        vector<int> res;
        for( int i = 0; i < N; i++ ){
            if( solve( i ) ) res.push_back( i );
        }

        return res;
    }
}