SRM 461 300pt: ColoringRectangle

TopCoder

問題概要

H*W(H,W<10^4)の長方形の板がある。赤い様々な直径の円盤をN(<50)枚、青いのをM枚持っている(直径<10^4)。最小何枚の円盤で板を被覆できるか求める問題。ただし、左から順に板を置いていき、同じ色の板が重なってはならない。

考えたこと

  • (はじめて参加したDiv 1のSRM。Div 1ではじめて通したのはこの問題)
  • 問題読むの2回目で問題の内容大体覚えてた。
  • 円盤は大きいものからつかうのが最善な気がする。
  • 赤からはじめるか青からはじめるかの2通りあるけど、両方シミュレーションしてやる。
  • 同じような処理が出てきたので関数にして処理する。
  • 計算でdoubleが出てくるけど流石にこれは避けようがない。
  • 何か通らないと思っていたら1ヶ所等号間違えてたのと、半径と直径を勘違いしていた。
  • 時間はかかったけど無事通った。当時と比べるとコードの内容もスコアも改善されていることが分かる。

practiceで通ったコード

計算量O(N+M)。書いてるときはオーバーフローのこと全然考えて無かった。通ったのは運が良かっただけ。

#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const int INF = 1<<29;
const double EPS = 1e-9;

struct ColoringRectangle {

	int chooseDisks(int width, int height, vector <int> red, vector <int> blue) {
		int ret = INF;
		sort(red.rbegin(), red.rend());
		sort(blue.rbegin(), blue.rend());

		ret = min(ret, solve(width, height, red, blue));
		ret = min(ret, solve(width, height, blue, red));

		return ret == INF ? -1 : ret;
	}

	int solve(int width, int height, const vector<int>& red, const vector<int>& blue){

		double left = 0;
		for(int i=0; ;i++){
			const vector<int> balls = (i&1)?red:blue;
			int id = i>>1;
			if(id >= (int)balls.size() || balls[id] < height){
				return INF;
			}
			int r = balls[id];

			double dist = 0.5 * sqrt(r*r - height*height);
			left += 2*dist;
			if(left > width - EPS){
				return i + 1;
			}

		}

		return INF;
	}

};