Zepto Code Rush 2014 : C. Dungeons and Candies

苦戦したけど何とかクリア。
http://codeforces.com/contest/436/problem/C

問題

K個のレベルからなるステージがある。
各レベルはN*M文字の文字列で構成される。

このステージ表現を圧縮して送信する際、必要なバイト数を最小化せよ。
なお、レベルの送信順は入れ替えても良い。

各レベルの表現方法は以下のいずれかである。

• N*M文字すべてをそのまま送信する。N*Mバイト必要。
• 送信済みのいずれかのレベルの値および、そのレベルとの差分を送る。差分文字数×Wバイト必要。

解法

レベルxのあとyを送っても、yのあとxを送っても、かかるコストはN*M+diff(x,y)*Wで同じである。
よって送る順はどうでも良い。
後は差分を送る際適切なレベルを選択すればよい。

これには以下の処理を繰り返し行えばよい。

• 未送信のレベルのうち、バイト数最小のものを送る。
• 上記送信の結果、残された未送信の送信必要バイト数の最小値を更新する。

int N,M,K,W;
string S[1001];
int cost[1001][1001];
int mcost[1001],tar[1001];
int vis[2001];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M>>K>>W;
	FOR(i,K) {
		FOR(y,N) {
			string s;
			cin>>s;
			S[i]+=s;
		}
	}
	N=N*M;
	FOR(x,K) for(y=x+1;y<K;y++) {
		l=0;
		FOR(i,N) l+=S[x][i]!=S[y][i];
		cost[x][y]=cost[y][x]=l*W;
	}
	
	FOR(x,K) mcost[x]=N;
	
	pair<int,int> R[2001];
	x=0;
	ll ret=0;
	while(1) {
		int id=-1;
		FOR(i,K) if(vis[i]==0 && (id==-1 || mcost[i]<mcost[id])) id=i;
		if(id==-1) break;
		R[x].first=id+1;
		R[x].second=tar[id];
		x++;
		ret+=mcost[id];
		vis[id]=1;
		FOR(i,K) if(vis[i]==0 && mcost[i]>cost[id][i]) mcost[i]=cost[id][i],tar[i]=id+1;
	}
	
	_P("%lld\n",ret);
	FOR(i,K) _P("%d %d\n",R[i].first,R[i].second);
}

まとめ

実は順番はどうでもいい、ということに気づくとあっさり。