Codeforces #774 : Div2 F. Playing Around the Table

Eまでは順調だったのに。
https://codeforces.com/contest/1646/problem/F

問題

N人の人が円周状に並んでいる。
各人はN枚のカードを持っている。
カードは、1～Nの数字が書かれたものがN枚ずつある。

この状態で、各人手持ちのカードを1枚選択して右隣の人に同時に送る、ということを繰り返す。
最終的に、i番の人はi番のカードをN枚持った状態にしたい。
(N^2-N)回以下の処理で条件を達成せよ。

解法

以下の2ステップで行うことができる。

• 前半では、全員が1～Nのカードを1枚ずつ持つようにする。
  • これは、各人重複があるカードを送りだせばよい。もし重複がない場合、手前の人から送ってくるだろうカードを送ればよい。
• 後半で、各人が自身の番号のカードを持つようにする。
  • これは容易で、各人vが(0-originで)(v+i)%Nのカードを送る、という手順を各iに対し行えばよい。

int N;
int C[101][101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		FOR(j,N) {
			cin>>x;
			C[i][x-1]++;
		}
	}
	vector<vector<int>> ret;
	while(1) {
		vector<int> V;
		int ok=1;
		FOR(i,N) {
			x=-1;
			FOR(j,N) if(C[i][j]>1) x=j;
			if(x!=-1) ok=0;
			V.push_back(x);
		}
		if(ok) break;
		FOR(i,2) {
			FOR(j,N) if(V[j]==-1) V[j]=V[(j+N-1)%N];
		}
		
		FOR(i,N) {
			C[i][V[i]]--;
			C[(i+1)%N][V[i]]++;
		}
		ret.push_back(V);
	}
	for(i=1;i<=N-1;i++) {
		x=i;
		while(x) {
			vector<int> V;
			FOR(j,N) V.push_back((j+x)%N);
			x--;
			ret.push_back(V);
		}
	}
		
	
	cout<<ret.size()<<endl;
	FORR(v,ret) {
		FORR(a,v) cout<<a+1<<" ";
		cout<<endl;
	}
}

まとめ

意外にシンプルな解法。