問題
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; } };