kmjp's blog

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

AtCoder ARC #111 : C - Too Heavy

前半がなかなか順調に解けて良かった。
https://atcoder.jp/contests/arc111/tasks/arc111_c

問題

0~(N-1)番の荷物がある。それぞれ荷物の重さが与えられる。
初期状態でi番の人はP[i]番の荷物を持っている。
2人間での荷物の交換を繰り返し、i番の人がi番の荷物を持つようにしたい。
この時、各人に「これ以上の重さの荷物を持っていると、その人はそれ以上の交換ができない」という上限が与えられる。

最小回数の荷物の交換順を求めよ。

解法

荷物が重い順に、その荷物を持つべき人と交換するようにしよう。
自分が持つべき荷物を手に入れたなら、それ以降荷物が重くても問題ないし、その重い荷物を交換した人は代わりにより軽い荷物を受け取るので、以後の処理に差支えない。

int N;
int A[202020],B[202020];
int P[202020],RE[202020];
vector<pair<int,int>> R;


void goswap(int a,int b) {
	if(A[a]<=B[P[a]]) {
		cout<<-1<<endl;
		exit(0);
	}
	if(A[b]<=B[P[b]]) {
		cout<<-1<<endl;
		exit(0);
	}
	R.push_back({a,b});
	swap(P[a],P[b]);
	RE[P[a]]=a;
	RE[P[b]]=b;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>B[i];
	vector<pair<int,int>> cand;
	FOR(i,N) {
		cin>>P[i];
		P[i]--;
		RE[P[i]]=i;
		cand.push_back({B[i],i});
	}
	sort(ALL(cand));
	reverse(ALL(cand));
	FORR(c,cand) {
		int tar=c.second;
		if(RE[tar]==tar) continue;
		
		goswap(RE[tar],tar);
	}
	
	cout<<R.size()<<endl;
	FORR(r,R) cout<<r.first+1<<" "<<r.second+1<<endl;
	
	
}

まとめ

本番は無駄な処理もしてたけどFAが取れた。