MovingTokens [SRM 705 : Div1 Med]

問題

https://community.topcoder.com/stat?c=problem_statement&pm=14471

N個のトークンが1つずつ入ったビンがある。
N*Mの行列Aがあり、以下の操作がある。

0 <= i <= M-1 を1つ選び、j番目のビンの中身を全てA[j][i]に全てのビンで同時に移す

この操作を無限回最適な順番で行う時、中身があるビンの個数の最小値は？

1 <= N, M <= 50

この問題はさっぱり分からなかったので、以下のサイトを参考にした。

• http://codeforces.com/blog/entry/49001?#comment-336677
• RAVEmanさんの提出プログラム

解法

実際はちゃんと理解していないんだけど、一応解法

1. eq[i][j] = true/false の計算
eq[i][j]を「i番目とj番目のビンに入っているトークンが任意回数の操作によって同じビンに入るかどうか」と定める。
これは、dfsをすることにより、求めることができる。
"equivalent"というワードがコドフォ議論で出ていたが、その計算だと思われる。

2. eq[i][j]を使ってv[k]の計算
v[k]を「k番目のビンにトークンが入っているか」と定める。
eq[i][j]がequivalentであれば、v[i]にv[j]を全部入れられるみたい。
それをやる。
正直、この貪欲法で解ける意味が分からん。

実装

int M[55][55];
bool eq[55][55];
bool done[55][55];
bool v[55];
struct MovingTokens {
	int move(int n, int m, vector <int> moves) {
		rep(i, 0, n) rep(j, 0, m) M[i][j] = moves[j * n + i];

		// 1
		rep(i, 0, n) rep(j, 0, n) {
			rep(ii, 0, n) rep(jj, 0, n) done[ii][jj] = false;

			queue<pair<int, int>> que;
			que.push({ i,j });
			done[i][j] = done[j][i] = true;
			while (!que.empty()) {
				auto p = que.front();

				int x = p.first;
				int y = p.second;
				que.pop();

				rep(k, 0, m) {
					int xx = M[x][k];
					int yy = M[y][k];
					if (!done[xx][yy]) {
						done[xx][yy] = done[yy][xx] = true;
						que.push({ xx, yy });
					}
				}
			}

			rep(ii, 0, n) if (done[ii][ii]) eq[i][j] = true;
		}

		// 2
		rep(i, 0, n) v[i] = true;
		rep(i, 0, n) rep(j, 0, n) if ((v[i] && v[j]) && (i != j && eq[i][j])) {
			v[j] = false;
			rep(k, 0, n) if (!(eq[i][k] && eq[j][k])) eq[k][i] = eq[i][k] = false;
		}

		int ans = 0;
		rep(i, 0, n) if (v[i]) ans++;
		return ans;
	}
};