CodeQUEEN 2023 決勝 : F - Queen's Crown

久々。
https://atcoder.jp/contests/codequeen2023-final-open/tasks/codequeen2023_final_f

問題

N要素の整数列Rが与えられる。
なお、Rの先頭と末尾の要素は最小値である。

Rから以下の手順で生成可能なN角形の面積の最大値を求めよ。
P[i]をi番目の点とすると、

• P[i]は、原点から距離R[i]の場所にある。
• P[0]の偏角は0、P[N-1]の偏角は120度である。
• P[i+1]の偏角とP[i]の偏角の差は0以上120/N度以下である。

解法

P[i]とP[i+1]の偏角の差をφ[i]とすると、面積は、である。
前半を見ると、sin(φ(i))はiが大きくなるほど増分が小さくなる。
よって、を微分した値が極力大きなところに角度を割り振るのが良い。
そこでの上限を二分探索しよう。

int N;
double R[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	double pi=atan(1)*4;
	cin>>N;
	FOR(i,N) cin>>R[i];
	double sum=-R[0]*R[N-1]*sin(pi*2/3)/2;
	
	double VL=0,VR=10000000;
	FOR(j,200) {
		double M=(VL+VR)/2;
		double F=0;
		FOR(i,N-1) {
			double v=min(cos(pi/2/N),2/R[i]/R[i+1]*M);
			F+=acos(v);
		}
		if(F<pi*2/3) VR=M;
		if(F>=pi*2/3) VL=M;
	}
	FOR(i,N-1) {
		double v=min(cos(pi/2/N),2/R[i]/R[i+1]*VL);
		v=acos(v);
		sum+=R[i]*R[i+1]/2*sin(v);
	}
	
	
	_P("%.12lf\n",sum);
}

まとめ

微分した値を二分探索する問題、あんまり見ないな。