kmjp's blog

競技プログラミング参加記です

TopCoder SRM 705 Div1 Medium MovingTokens

450ptの割に苦戦。
https://community.topcoder.com/stat?c=problem_statement&pm=14471

問題

N要素からなる数列M個からなる数列群moves[i]が与えられる。
今初期状態で0~(N-1)のマスすべてにトークンが1つずつ置かれている。
ここで、いずれかのmoves[i]を選択すると、マスjにおかれたトークンはすべてmoves[i][j]に移動する。
これらの移動は全トークン同時に行われる。

上記操作を任意の回数行えるとき、トークンが置かれたマスの数を最小化せよ。

解法

Nマスのトークンを同時に考えるのは面倒なので、ある2マスのトークンが同じマスに集まるようにできるかを考えよう。
まず以下の真偽値を列挙しておく。
f(x,y) := マスxとマスyにあったトークンが同じマスに集まるような操作手順が存在する
これはメモ化探索すればO(N^2*M)程度で間に合う。(以下のコードは手抜きでもう少し計算量が多い)

一度同じマスに集まったトークンは再び離れることはない。
あとは上記f(x,y)の値を用いて0~(N-1)のマスのトークンを最小何マスに集められるか考える。

なお、f(x,y)=1かつf(x,z)=1だからといって、x,y,zが1マスに集まるとは限らない。
x,yを1マスのまとめるための手順をとる過程で、zが以後二度と同じマスに集められないようなマスに移動してしまうためである。
そのため最小値を求める手順は大変そうだが、他のコードで簡潔な貪欲法があったので紹介。

未訪問のトークンxがあったとする。対応して他のトークンyを総当たりしていこう。
yが未訪問かつf(x,y)=trueなら、ほかのzの存在は無視してyを取り入れる(すなわちxとyは同じマスに集められると判断し、yを訪問済み)ことにしよう。
そうすると、上記zのようなケースをうまく対処しなければならない。
ここはf(x,z)かf(y,z)のどちらかが0なら、xとyを同じマスに集めた段階でさらにzを集めることは不可能になる。
よってその場合f(x,z)=f(y,z)=0としてしまえばよい。
あとは貪欲にyに相当するものを集めていこう。

class MovingTokens {
	public:
	
	int move(int n, int m, vector <int> moves) {
		int mat[50][50];
		int ok[50][50]={};
		int did[50][50]={};
		int yes[50]={};
		
		int y,x,i,j;
		FOR(y,n) FOR(x,m) mat[y][x]=moves[x*n+y];
		vector<int> Q;
		FOR(i,n) ok[i][i]=did[i][i]=1, Q.push_back(i*100+i);
		
		while(Q.size()) {
			int a=Q.back()/100;
			int b=Q.back()%100;
			Q.pop_back();
			
			FOR(i,m) {
				FOR(x,n) if(mat[x][i]==a) {
					FOR(y,n) if(mat[y][i]==b && did[x][y]==0) {
						ok[x][y]=did[x][y]=1;
						ok[y][x]=did[y][x]=1;
						Q.push_back(x*100+y);
					}
				}
			}
		}
		
		int cnt=0;
		FOR(i,n) if(yes[i]==0) {
			yes[i]=1;
			cnt++;
			FOR(j,n) if(i!=j && yes[j]==0 && ok[i][j]) {
				yes[j]=1;
				FOR(x,n) if(ok[i][x]==0 || ok[j][x]==0) ok[i][x]=ok[x][i]=0;
			}
		}
		
		return cnt;
	}
}

まとめ

このテク、昔のSRMでも見た気がするけど思い出せない…。