AtCoder ARC #029 : A - 高橋君とお肉、B - 高橋君と禁断の書

今日のARCは不参加。
練習の感じではギリギリ全完で来てたので、出られればよかったな…。
http://arc029.contest.atcoder.jp/tasks/arc029_1
http://arc029.contest.atcoder.jp/tasks/arc029_2

A - 高橋君とお肉

N個の肉を２個の肉焼き機で焼く。
各肉を焼くには、T[i]の連続した時間肉焼き機を占有しなければならない。
全部の肉を焼き終わる最短時間を答えよ。

Nが小さいので、2^N通り各肉を焼く機械を総当たりすればよい。

int N;
int T[4];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>T[i];
	int ret=10000000;
	for(int mask=0;mask<1<<N;mask++) {
		int t[2]={};
		FOR(i,N) t[(mask>>i)&1]+=T[i];
		ret=min(ret,max(t[0],t[1]));
	}
	cout << ret << endl;
}

B - 高橋君と禁断の書

A*Bの大きさの長方形がある。
N個のクエリC[i],D[i]が与えられるので、この長方形を回転または平行移動し、C[i]*D[i]の大きさの長方形に収められるかどうかを答えよ。

まずA*BとC[i]*D[i]両方の長方形を高さの方が長くなるように並べる。
すなわちA,C[i]が幅、B,D[i]が高さとする。

• 幅も高さもクエリの長方形の方が大きければ、明らかに収められる。
• 幅AがC[i]より大きい場合、どう回転しても収められない。
• 残るケースは、幅は余裕がある(A＜C[i])が高さに余裕がない(B＞D[i])場合、長方形を回転させて収められるかどうか判定する。
  • 自分は以下のようにやった。まず両長方形を重心が一致するように置き、右回転したときにA*Bの長方形の右上がC[i]*D[i]の長方形の右辺に接する座標を求める。
  • あとはこの時の回転角をもとに、A*Bの左上点がどこに来るかを求め、そこが上辺の内側に収まるか判定する。

ll A,B;

int okok(ll X,ll Y) {
	if(A>X) return false;
	if(B<=Y) return true;
	double diag = sqrt(A*A+B*B)/2;
	double rad=2*atan2(A,B);
	double x=X/2.0,y=sqrt(diag*diag-x*x);
	double ny=y*cos(rad)+x*sin(rad);
	return 2*ny-0.000001<=Y;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B;
	if(A>B) swap(A,B);
	cin>>j;
	while(j--) {
		cin>>x>>y;
		if(x>y) swap(x,y);
		if(okok(x,y)) _P("YES\n");
		else _P("NO\n");
	}
}

まとめ

Bがちょっと考えさせられる問題だった。
A,BをintにしていたせいでA*Aがoverflowして25分+5WA損した。