くれなゐの雑記

例を上げて自分で手を動かして学習できる入門記事を多めに書いています

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,c$ を $y$ から初めて順に大きくしていって $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;
}