yukicoder : No.1122 Plane Tickets

これ系苦手。
https://yukicoder.me/problems/no/1122

問題

A,B,C,D,Eの5種類のチケットの枚数がそれぞれ与えられる。
以下の3種のチケットを1枚ずつ組み合わせると、1回飛行機に乗れる。

• A,B,C
• B,C,D
• C,D,E
• D,E,A
• E,A,B

最適な組み合わせを行うと、最大何回飛行機に乗れるか。

解法

二分探索をすることを考える。
以下、K回飛行機に乗れるかどうかを判定することを考えよう。

「組み合わせに用いない2枚を選ぶ」と言い換えると、少し簡単になる。
これらは用いない組の回数を求めるので、回数が少ないほど良い。

• a,b
• b,c
• c,d
• d,e
• e,a

(a,b)の組の選択回数に対し、飛行機に乗れる回数は下に凸な関数となる。
そこで(a,b)の組の選択回数を三分探索していこう。
(a,b)の選択回数が決まれば、(b,c)の選択回数も決まり…と連鎖的に決まっていく。

ll A,B,C,D,E;
ll KA,KB,KC,KD,KE;

ll F(ll OE) {
	ll OA=max(0LL,KA-OE);
	ll OB=max(0LL,KB-OA);
	ll OC=max(0LL,KC-OB);
	ll OD=max({0LL,KD-OC,KE-OE});
	return OA+OB+OC+OD+OE;
}


int ok(ll K) {
	
	KA=max(0LL,K-A);
	KB=max(0LL,K-B);
	KC=max(0LL,K-C);
	KD=max(0LL,K-D);
	KE=max(0LL,K-E);
	
	ll L=0,R=K;
	while(R-L>=3) {
		ll M1=(L*2+R)/3;
		ll M2=(R*2+L)/3;
		ll V1=F(M1);
		ll V2=F(M2);
		
		if(V1==V2) {
			L=M1;
			R=M2;
		}
		else if(V1<V2) R=M2;
		else L=M1;
	}
	
	for(ll a=L;a<=R;a++) if(F(a)<=K) return 1;
	return 0;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>C>>D>>E;
	ll ret=0;
	for(i=52;i>=0;i--) if(ok(ret+(1LL<<i))) ret+=1LL<<i;
	cout<<ret<<endl;
	
}

まとめ

あー双対っぽいの来たなーと思ったけど、参加が遅かったこともありそこで時間切れしたので詰め切れなかった。