SRM 567 Div1 500 StringGame

2013-01-23

19:08 |

同じ長さの文字列集合Sが与えられる。自分は１コ(xとする)を選んで文字を並び替えて X とする。さらにアルファベットの順序を決める。相手は x 以外について文字を好きに並び替える。相手がどう並び替えても X が辞書式順序で最小になる（勝つ）ような x のインデックスを全て求める。
文字列の長さ≦50, 2≦|S|≦50, 文字はa～z

観察: xとアルファベットの並び順が決まるとXは一通りに定まる。(その並び順でxをソートしたものがXになる)
ので、どういう並び順にしたら勝つるかを考えればいい。

x の候補それぞれについて、それに含まれるある文字 c の個数が他の全ての文字列における c の個数より多い場合、
cを先頭に定めれば勝つる、そうじゃない場合は負ける可能性があるのでだめ、というコードを書いてあっさり challenge される。

(あとで)
hotpepsiさんやsimezi_tanさんのを見る

自分が書いたやつは勝利の十分条件でしかなくて、実はもっと勝てる場合があるみたい。
"aabcdd", "aabbcd", "aabbcc" の場合、文字カウントは

a b c d
-------
2 1 1 2
2 2 1 1
2 2 2 0

なので、明らかに他より多い文字があるというやつは 0, 2 しかない
が、1 はアルファベット順を "bdac" にすれば勝てる

というわけで、アルファベットの順序を順々に決めていく方針でやってみる
a-zについて、
(1)他の文字列に多く含まれるような文字を採用すると自分が負け確定になるなのでだめ
(2) そうでない場合、次のアルファベットとしてその文字を採用すれば、その文字の個数が自分のより少ない他の文字列を負けにできるのでそうする
自分が負け確定になるのでだめだと思っていたアルファベットを含む文字列は、実は別のa-zについて(2)で負けになってるかもしれない。ので、再度(1)を評価する。具体的には情報が伝搬するまで(1)(2)を最大 26 回繰り返す
自分以外が負け確定になってたら自分が勝てるので答えに追加する

というアルゴリズムでよいみたい。

↓あとで (accepted in practice)

class StringGame {
	public:
	vector <int> getWinningStrings(vector <string> S) {
		int N=S.size();
		VVI hi(N, VI(26));
		REP(i, N) {
			REP(j, S[i].size()) {
				hi[i][S[i][j]-'a']++;
			}
		}
		cout<<hi<<endl;
		vector<int> ans;
		REP(i, N) {
			string alpha;
			VI live(N, 1);
			live[i]=0;
			REP(loop, 26) {
				REP(c, 26) {
					int lose_char=0;
					REP(j, N) {
						if(live[j] && hi[j][c] > hi[i][c]) lose_char=1;
					}
					if(lose_char) continue;
					
					REP(j, N) {
						if(live[j] && hi[j][c] < hi[i][c]) {
							live[j]=0;
							// アルファベットの順番（のうち確定したものだけ）も出すようにしてみる
							if(alpha.find(c+'a')==string::npos) alpha.PB(c+'a');
						}
					}
				}
			}
			//cout<<live<<endl;
			cout<<i<<" "<<(accumulate(ALL(live), 0LL)==0 ? "OK":"NG")<<" Alphabet: "<<alpha<<endl;
			if(accumulate(ALL(live), 0LL)==0) ans.PB(i);
		}
		return ans;
	}
};

出力例

"aabcdd", "aabbcd", "aabbcc" の場合

0 OK Alphabet: d
1 OK Alphabet: bd
2 OK Alphabet: bc