Good Bye 2025 : D. Xmas or Hysteria

可もなく不可もなく…だった回。
https://codeforces.com/contest/2178/problem/D

問題

N匹の妖精がおり、i体目の体力はH[i]である。また、攻撃力A[i]=H[i]である。なお、H[i]はdistinctである。
以下の処理を、可能な限り行う。

• 妖精のうち２匹を選ぶ。ただし少なくとも片方は過去に選ばれたことがないものでないといけない。
  • 互いの体力を、相手の攻撃力分減算し、体力が0以下になった方は死亡する。

最終的にM体妖精が残るような手順があれば、一例を示せ。

解法

１回処理すると１体は妖精が死亡するので、MはNの半分以下でなければならない。
妖精を体力順にソートしたとして、以下を行う。

• Mが正の時
  • i体目とi+M体目を選ぶ、という処理をiの昇順に行う。
  • H[i]=A[i]はdistinctなので、毎回必ず片方は残り、最終的にM体残る。
• M=0の時
  • 最大の体力を持つ妖精が、全体の過半数の体力を持っていると、その妖精を志望させられないので不可。
  • そうでない場合、妖精は弱い順にあと1撃で倒せるまで一番強い妖精と選ばせる。
  • あとは残された妖精を(元の順序で)弱いもの同士選べば、最後妖精が2体まとめて死亡し、全妖精を死亡させることができる。

int T,N,M;
ll A[202020],H[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		vector<pair<int,int>> V;
		ll S=0;
		FOR(i,N) {
			cin>>A[i];
			V.push_back({A[i],i+1});
			S+=A[i];
		}
		if(M*2>N) {
			cout<<-1<<endl;
			continue;
		}
		sort(ALL(V));
		if(M) {
			cout<<N-M<<endl;
			for(i=M;i<N;i++) {
				cout<<V[i].second<<" "<<V[i-M].second<<endl;
			}
		}
		else {
			if(S-V[N-1].first<V[N-1].first) {
				cout<<-1<<endl;
			}
			else {
				cout<<N-1<<endl;
				FOR(i,N-1) {
					if(V[i].first>=V[N-1].first) break;
					cout<<V[i].second<<" "<<V[N-1].second<<endl;
					V[N-1].first-=V[i].first;
				}
				for(j=i+1;j<N;j++) {
					cout<<V[j].second<<" "<<V[j-1].second<<endl;
				}
			}
		}
	}
	
}

まとめ

最終的に難しいことはしてないけど、なんか手間取った。