SRM 433 Div1 easy MagicWords

2011-12-29

14:49 |

文字列を回転させたもののうち、元の文字列と一致するものが K 個になるようなのを magic word ということにして、

いくつかの文字列をいろんな順序でつなげたもののうち magic word になるようなやつの個数を求める。

文字列の個数は最大8個なので、8! = 40320 ということでこれはそのまま全部試せばよさそう。
くっつけた文字列の長さ L の最大値は 8*20=160。magic word 判定は普通にやると長さ^2なので、160 * 160 * 40 320 = 1,032,192,000となってちょっと微妙そうな感じがする
回転して元と一致する個数が k 個なら、その文字列は長さL/kの文字列が k 個つながってる　という性質を利用
先頭の L/k 文字と L/k*j からの L/k 文字がすべて一致する → 一致するものは k 個以上
このチェックだと一致する個数が 2 つの場合は 4 つの場合に含まれるので、一致する個数を大きい方から L～1 として見ていく。
k 個一致したらそこで終わりなので K と同じなら答えを１コ増やす。
N^2 っぽいけど、L mod k != 0 のときはチェックを端折れるので N^1.5 ほどになると思う。

class MagicWords {
	public:
	int count(vector <string> S, int K) {
		int N=S.size();
		VI p(N);
		REP(i, N) p[i]=i;
		int L = 0;
		REP(i, N) L+=S[i].size();
		if(L%K==0) {
			int ans = 0;
			do {
				string s = "";
				REP(i, N) s+=S[p[i]];
				for(int l=1;l<=L;l++) {
					if(L%l!=0) continue;
					int k=L/l;
					int ok=1;
					REP(i, L/k) REP(j, k) if(s[i]!=s[j*L/k+i]) ok=0;
					if(ok) {
						if(k==K) ans++;
						break;
					}
				}
				//cout<<s<<"  "<<ok<<endl;
			} while(next_permutation(ALL(p)));
			return ans;
		}
		return 0;
	}