Codeforces #959 : D. Funny Game

中盤で失速した回。
https://codeforces.com/contest/1994/problem/D

問題

N要素の整数列Aが与えられる。
N点からなる無向グラフを考える。初期状態で辺はない。

これからN-1回以下の処理を行う。

• i回目では、|A[v]-A[u]|がiの倍数となるような頂点対(u,v)を選び、間に辺を張る

この手順で全域木に構築できるか。できるなら辺の張りかたの一例を示せ。

解法

(N-1)回目から逆順で行っていく。
今v回目の処理を行うとき、連結成分が(v+1)個ある状態なはずなので、鳩ノ巣原理より、必ず条件を満たす頂点対が存在する。

int T,N;
int A[202020];
int vis[2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>A[i];
			vis[i]=1;
		}
		vector<pair<int,int>> V;
		for(i=N-1;i>=1;i--) {
			map<int,int> C;
			FOR(j,N) if(vis[j]==1) {
				x=A[j]%i;
				if(C.count(x)) {
					V.push_back({C[x],j});
					vis[C[x]]=0;
					break;
				}
				C[x]=j;
			}
			assert(j!=N);
		}
		reverse(ALL(V));
		cout<<"YES"<<endl;
		FORR2(a,b,V) cout<<a+1<<" "<<b+1<<endl;
	}
}

まとめ

これはさっと思いつけて良かったね。