くれなゐの雑記

身の回りの人や自分が困っていたことを記事にしています

Codeforces #712 Div.2 C. Memory and De-Evolution

要約

正三角形2つが与えられる.
それぞれの辺の長さは, [tex:x, y (y

やること

非縮退三角形とは, 以下の条件を満たす三角形(つまり普通の三角形) 三角形の辺の長さをa,b,c とすると,
 a+b > c \\ b+c > a \\ a+c > b

少し変形して, 辺aに着目すると, 以下のような式になる

|b-c| < a < b+c

辺の長さを減らしていく方向に考えると, 他の辺を減らす量が減ってしまうことがあり, 貪欲に考えることができない.
しかし, 辺の長さを増やしていく方向に考えると, 増やせば増やすほど他の辺もいっぱい増やせるので貪欲に増やすことができる
不等号が含まない不等号なのに注意して,

 a = max(b+c-1, x)

となるようにする.
同様に, a,b,cyから初めて順に大きくしていってxになった時点で終了

SourceCode

void solve() {
	//y -> x
	int x, y; cin >> x >> y;
	vector<int> vx(3, y);
	vector<int> vy(3, x);

	ull cnt = 0;
	ull ok = 0;
	for (ull i = 0;; ++i) {
		int tar = i % 3;
		if (vx[tar] != x) {
			vx[tar] = min(vx[(tar + 1) % 3] + vx[(tar + 2) % 3] - 1, x);
			++cnt;
		}
		else ok |= 1 << tar;
		if (ok == (1 << 3) - 1) break;
	}

	cout << cnt << endl;
}