yukicoder : No.2182 KODOKU Stone

操作が割と複雑な問題。
https://yukicoder.me/problems/no/2182

問題

N個の袋があり、それぞれいくつかの石が入っている。
各石の重さはあらかじめ与えられている。

N要素の整数列Kに対し、以下をNターン順に行う。

• 石が入っている袋を任意に1つ選び、中身の石を全部箱に入れる。
• iターン目では、箱の中の石のうち、上位K[i]番目の重さの石を1つ残し、残りを捨てる。

最後に残った石の重さの最大値を求めよ。

解法

重さMを二分探索することを考える。すなわち、石をM以上と未満で分類し、M以上の石を最後に残す手段があるかを考える。
まず袋を分類する。
M未満の石がある袋を、M以上の石の個数で昇順ソートした列をP、ない袋の集合をQとする。
R=(ラスト|Q|ターンにおけるK[i]の多重集合)
r=Rの最小値
とする。

• Pが空なら、最後の石の重さM以上を達成可能。
• Q中に、rより石の数が多い袋があれば、最後の石の重さM以上を達成可能。

そうでない場合、以下を順に試す。

• 初期状態としてi=|P|とする
• u=min(r, K[i])としてP[i]中にu個以上のM以上の重さの石があるなら、M以上を達成可能。u-2以下しかないなら達成不可。
• いずれでもない場合、(i-1)ターン目でM以上の重さの石をiターン目に持ち込めればよいことになる。
  • P[i]に(r-1)個のM以上の重さの石があり、Q中にK[i]以上の石を持つ袋があるなら、両者を使うターンを入れ替え、達成可。
  • i=1なら、達成不可。
  • P[i]が(r-2)以下なら、iをデクリメントしてまたループする。
  • そうでないなら、Rからrを取り除き、代わりにK[i]を挿入して、iをデクリメントしてまたループする。

int N;
int T[101010];
vector<int> A[101010];
int K[101010];

int ok(int v) {
	vector<int> P,Q;
	
	int i;
	Q.push_back(-1);
	FOR(i,N) {
		int X=0,Y=0;
		FORR(a,A[i]) {
			if(a<v) X++;
			else Y++;
		}
		if(X) P.push_back(Y);
		else Q.push_back(Y);
	}
	multiset<int> R;
	R.insert(1<<30);
	FOR(i,Q.size()-1) R.insert(K[N-1-i]);
	sort(ALL(P));
	sort(ALL(Q));
	
	if(P.empty()||Q.back()>=*R.begin()) return 1;
	for(i=P.size()-1;i>=0;i--) {
		if(P[i]>=min(*R.begin(),K[i])) return 1;
		if(P[i]<=min(*R.begin(),K[i])-2) return 0;
		if(P[i]==*R.begin()-1&&Q.back()>=K[i]) return 1;
		if(P[i]<=*R.begin()-2) continue;
		R.erase(R.begin());
		R.insert(K[i]);
		
		
	}
	return 0;
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>K[i];
	FOR(i,N) {
		cin>>T[i];
		A[i].resize(T[i]);
		FORR(t,A[i]) cin>>t;
	}
	
	int ma=0;
	for(i=29;i>=0;i--) if(ok(ma+(1<<i))) ma+=1<<i;
	cout<<ma<<endl;
}

まとめ

これを漏れなくさっと書くのは難しいな…。