CF514 Div2 D - Nature Reserve

問題

n個の点があり、i番目の点の座標は(x[i],y[i])である
これらの点を全て内側(または境界)に含み、かつy=0と接する円を1つ描きたい
描けるならその半径の最小値を求めよ
描けない場合は-1

1 <= n <= 10^5
|x[i]|, |y[i]| <= 10^7

解法

各点のy座標の正負が全て一致していれば必ず描ける
そうでなければ描けない

半径の二分探索で解ける
半径をrと仮定すると、まず求めたい円のy座標はもちろんrになる
この円がi番目の点を内側に含むためには、この円のx座標が、「直線y=rのうち、点iを中心とした半径rの円の内側(境界含)に含まれる部分(線分)」上にある必要がある
全ての点を含むには全ての点における↑の線分の共通範囲が存在する必要がある
共通範囲が存在しなかったり、↑のような線分すら存在しない点があったら半径rでは条件を満たす円は描けない

俺は本番では↑まで辿り着けなくて、x座標を三分探索してその中で半径を二分探索する方針でやろうとした
結局誤差とか二分探索の上限ミスとかで解けなかったけど、ちゃんと書けたとしてもコドフォだとTLEしてたと思う
(計算量は5*10^8前後になる気がした)

実装

深く考えずに半径の上限を10^9にしてたんだけどそれだと足りなかった
テストケース4が (-10^7, 1) (10^7, 1) (-10^7, 10^7) (10^7, 10^7) っていう最強のケースで、これの答えが5*10^13になる

誤差がヤバイ
editorialの模範解答がlong double使ってる
あと俺は上限を10^30にしたんだけど、ここまでデカイと三平方の定理で線分の長さを求めるとき
(m*m - (y[i]-m)*(y[i]-m))
って書くとy[i]が1のときy[i]がスルーされて0になってしまう
2*y[i]*m - y[i]*y[i]
まで式展開してやったら通った
いろいろヤバイ

#define double long double

int n, fu;
double x[100100], y[100100], l = 0, r = 1e30;

bool ok(double m) {
	double lb = -1e100, rb = 1e100;
	rep(i,n) {
		if (m*2<y[i]) return 0;
		double d = sqrt(y[i]*m*2 - y[i]*y[i]);
		chmax(lb, x[i]-d), chmin(rb, x[i]+d);
	}
	return lb<=rb;
}

signed main() {
	cin >> n;
	rep(i,n) {
		cin >> x[i] >> y[i];
		if (!fu) fu = (y[i]<0 ? -1 : 1);
		else if (fu*y[i]<0) return cout << -1 << endl, 0;
	}
	rep(i,n) y[i] *= fu;
	rep(i,200) {
		double m = (l+r)/2;
		(ok(m) ? r : l) = m;
	}
	printf("%.14Lf\n",r);
}

yukicoder 743 - Segments on a Polygon

問題

m頂点の凸多角形があり、各頂点には0〜m-1の番号が割り振られている
ここに2つの頂点同士を結ぶような線分をn個追加する
追加した線分同士の交点の数を求めよ

1 <= n <= 10^5
3 <= m <= 2*10^5

解法

任意のiでa[i] < b[i]となるようにswapし、線分たちをa[i]の昇順にソートすると、i本目の線分がj(＜i)本目の線分と交わるのは
a[i] < b[j] < b[i]
を満たすときになる
BITで↑を満たすようなjの個数を求めていけばいい

ll n, m, x, y, res;
pair<int,int> p[100100];
BIT<int,20> b;

signed main() {
	cin >> n >> m;
	rep(i,n) {
		cin >> x >> y;
		if (x>y) swap(x,y);
		p[i] = {x,y};
	}
	sort(p,p+n);
	rep(i,n) {
		res += b.sum(p[i].second) - b.sum(p[i].first);
		b.add(p[i].second, 1);
	}
	cout << res << endl;
}

SRM551 Div1 Easy - ColorfulChocolates

問題

長さnの文字列sが与えられる
sの隣り合う2文字をswapするという操作を最大k回まで行い、sで同じ文字が連続している部分の長さの最大値を最大化せよ

解法

s[i]を真ん中にして、s[i]と同じ文字をなるべく多く隣まで持ってくることを考えればいい
便宜上、s[i]に隣接するs[i]と同じ文字たちをグループと呼びます
(例えばs=BAABAならs[1]とs[2]は同じグループ)
s[i]より右にある文字s[j]をs[i]と同じグループにするには、(区間(i,j)に存在するs[i]とは異なる文字の個数)回だけswapが必要
s[i]より左にある文字も同様
限られたswap回数でグループの最大化するには、左右は問わず、この値が小さいものから順に引っ張ってくるのが明らかに最善

実装

答えを0で初期化してて1回死んだ

class ColorfulChocolates {
public:
	int maximumSpread(string s, int k) {
		int n = s.size(), res = 1;
		rep(i,n) {
			vector<int> d;
			int c = 0;
			reps(j,i+1,n) {
				if (s[j]==s[i]) d.push_back(c);
				else c++;
			}
			c = 0;
			for (int j=i-1; j>=0; j--) {
				if (s[j]==s[i]) d.push_back(c);
				else c++;
			}
			sort(all(d));
			rep(j,d.size()) {
				if (j) d[j] += d[j-1];
				if (d[j]<=k) chmax(res,j+1);
			}
		}
		return res;
	}
};

SRM549 Div1 Easy - PointyWizardHats

問題

円錐状の帽子を2つ組み合わせて魔女の帽子を作りたい
上側用の帽子がn個、下側用の帽子がm個ある
上側用の帽子iと下側用の帽子jは以下の条件を満たすときのみ組み合わせて魔女の帽子にできる
1) 上側の帽子の頂点は下側の帽子の頂点より上にある
2) 下側の帽子が上側の帽子に完全に隠れていない
n+m個の帽子をうまくペアにすることで最大で何個の魔女の帽子が作れるか

1 <= n, m <= 50
1 <= (各帽子の高さと半径) <= 10^4

解法

2組の帽子がペアにできる条件は、上側の帽子の高さと半径をha, ra、下側のそれらをhb, rbとすると、
1) hb*ra < ha*rb
2) ra < rb
という式で表せることが図↓からわかる

↑の判定でペアにできる帽子同士を辺で結び、できた二部グラフの最大マッチングをDinicとかで求めればok

class PointyWizardHats {
public:
	int getNumHats(vector<int> ha, vector<int> ra, vector<int> hb, vector<int> rb) {
		int n = ha.size(), m = hb.size();
		Dinic din;
		rep(i,n) din.add_edge(0,100+i,1);
		rep(i,m) din.add_edge(200+i,300,1);
		rep(i,n) rep(j,m) if (ra[i]<rb[j] && hb[j]*ra[i]<ha[i]*rb[j])
			din.add_edge(100+i,200+j,1);
		return din.getflow(0,300);
	}
};

SRM548 Div1 Easy - KingdomAndTrees

問題

木がn本あり、i本目の高さはa[i]である
コストxの魔法を使うと各木の高さを0〜xだけ増やすか減らすことができる
aを競技単調増加にするために使う必要のある魔法の最小コストを求めよ

2 <= n <= 50
1 <= a[i] <= 10^9

解法

二分探索
使う魔法のコストを決めたとき、各木の高さは単調増加になる範囲でなるべく低くしていけばいい

class KingdomAndTrees {
public:
	int minLevel(vector<int> a) {
		int n = a.size(), l = -1, r = 1<<30;
		while (r-l>1) {
			int m = (l+r)/2, b = 0, ok = 1;
			rep(i,n) {
				if (a[i]+m<=b) ok = 0;
				else b = max(b+1, a[i]-m);
			}
			(ok ? r : l) = m;
		}
		return r;
	}
};

SRM547 Div1 Easy - Pillars

問題

2本の塔があり、距離はwである
これらの塔の高さは1本目が[1,x]、2本目が[1,y]の範囲から等確率で決まる
2本の塔それぞれの頂上同士をまっすぐなロープで繋ぐ
ロープの長さの期待値を求めよ

1 <= w <= 10^3
1 <= x, y <= 10^5

解法

1本目の塔の高さをkに固定する
更に2本目の高さがmになる場合、
ロープの長さ L(m) = sqrt(|k-m|^2 + w^2)
確率 p(m) = 1/xy
となる
1本目の塔の高さがkになる場合の期待値はΣL(i)p(m) = 1/xy * ΣL(m)である
ΣL(m)は累積和を使っていい感じに計算すればO(1)で求められる

・いい感じとは？
s[i]: Σ (|k-m|がjであるときのpの値) (0 <= j <= i)
を事前に求めておいて、

(kがyより大きいとき)
s[k-1] - s[k-y-1]
(そうじゃないとき)
m<=kのぶん: s[k-1]
k＜mのぶん: s[y-k] - s[0]

これらをxyで割ったものを答えに足していく

実装

s[]を埋めるときのiはlonglongです

class Pillars {
public:
	double getExpectedLength(int w, int x, int y) {
		double s[100100] = {}, res = 0;
		rep(i,100010) s[i] = sqrt(w*w + i*i) + (i ? s[i-1] : 0);
		reps(k,1,x+1) {
			if (y<k) res += s[k-1] - s[k-y-1];
			else res += s[k-1] + s[y-k] - s[0];
		}
		return res/x/y;
	}
};

SRM546 Div2 Medium - TwoRectangles

問題

長方形が2つ、それぞれ左下と右上の点の座標が与えられる
これらの長方形の共通範囲が 長方形 or 線 or 点 or 存在しない のどれであるか判定せよ

0 <= 各座標 <= 1000

解法

初期値0の2次元配列で2つの長方形が占める領域をそれぞれ全部+1すると、重なってる部分は2になる
2のマスが1個でもあれば答えは少なくともpointにはなる
ある2のマスと上下左右で隣接する2のマスがあれば答えは少なくともsegmentになる
2のマスが4つ固まった正方形があれば答えはrectangleになる

俺はスタックオーバーフローがトラウマになってるんだけど、調べてみたらtopcoderはスタック領域は8MBくれるらしい
(ソースはhelpのgeneral Q&A)
今回のint10^6個は大丈夫だけどlonglong10^6個は無理(というかぴったり入るけど他のことが何も出来ない)って感じ
Linuxのデフォルトが8MBらしいけど他のサイトでもそうなのかな？

class TwoRectangles {
public:
	string describeIntersection(vector<int> a, vector<int> b) {
		int s[1010][1010] = {};
		reps(i,a[0],a[2]+1) reps(j,a[1],a[3]+1) s[i+1][j+1]++;
		reps(i,b[0],b[2]+1) reps(j,b[1],b[3]+1) s[i+1][j+1]++;
		int res = 0;
		reps(i,1,1005) reps(j,1,1005) if (s[i][j]==2) {
			chmax(res, 1);
			if (s[i-1][j]==2 || s[i+1][j]==2 || s[i][j-1]==2 || s[i][j+1]==2) chmax(res, 2);
			if (s[i+1][j]==2 && s[i][j+1]==2 && s[i+1][j+1]==2) chmax(res, 3);
		}
		if (res==3) return "rectangle";
		if (res==2) return "segment";
		if (res==1) return "point";
		return "none";
	}
};