AtCoder ARC #089 : E - GraphXY

色々グダグダでした。
https://beta.atcoder.jp/contests/arc089/tasks/arc089_c

問題

A*Bの2次元配列D(x,y)が与えられる。
以下の条件を満たすグラフを構築せよ。

• N頂点以下の単純有向グラフである。
• 各辺は0～100の整数か、もしくは変数X,Yのコストを持つ。
• X,Yに1～A、1～Bを代入したとき、ある2頂点間の最小コストがD(X,Y)に一致する。

解法

0～100番の頂点を0から順にコストXの辺でつないでいく。
同様に、101番から201番まで順にコストYの辺でつないでいこう。

こうすると、S番から(202-T)番にコストP(S,T)の辺を張ると、総コストは(S*X+T*Y+P(S,T))になる。
よってD(X,Y)の配列をもとに、その辺を通るケースのコストがD(X,Y)を下回ってしまうことが内容、P(S,T)を設定しよう。
そうしてP(S,T)を一通り設定した後、改めてD(X,Y)をそれぞれ計算し検証しよう。

int A,B;
int C[12][12];
int D[101][101];
int DX[12][12];
int DY[12][12];
int NV;
int V[303][303];

int K=100;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(V);
	
	cin>>A>>B;
	for(x=1;x<=A;x++) {
		for(y=1;y<=B;y++) {
			cin>>C[x][y];
		}
	}
	
	vector<int> Xs,Ys;
	NV=1;
	Xs.push_back(NV);
	FOR(i,K) {
		V[NV][NV+1]=-2;
		NV++;
		Xs.push_back(NV);
	}
	NV++;
	Ys.push_back(NV);
	FOR(i,K) {
		V[NV+1][NV]=-3;
		NV++;
		Ys.push_back(NV);
	}
	
	for(x=0;x<=K;x++) {
		for(y=0;y<=K;y++) {
			int ret=0;
			for(i=1;i<=A;i++) {
				for(j=1;j<=B;j++) {
					ret=max(ret,C[i][j]-x*i-y*j);
				}
			}
			D[x][y]=V[Xs[x]][Ys[y]]=ret;
		}
	}
	
	for(i=1;i<=A;i++) {
		for(j=1;j<=B;j++) {
			int mi=1010;
			for(x=0;x<=K;x++) {
				for(y=0;y<=K;y++) {
					mi=min(mi,x*i+j*y+D[x][y]);
				}
			}
			if(mi!=C[i][j]) return _P("Impossible\n");
			
		}
	}
	
	int cnt=0;
	FOR(x,303) FOR(y,303) if(V[x][y]!=-1) cnt++;
	cout<<"Possible"<<endl;
	cout<<NV<<" "<<cnt<<endl;
	FOR(x,303) FOR(y,303) if(V[x][y]!=-1) {
		cout<<x<<" "<<y<<" ";
		if(V[x][y]==-2) cout<<"X"<<endl;
		if(V[x][y]==-3) cout<<"Y"<<endl;
		if(V[x][y]>=0) cout<<V[x][y]<<endl;
	}
	cout<<Xs[0]<<" "<<Ys[0]<<endl;
}

まとめ

うーん、本番もう少しややこしいことを考えてしまった。