SRM552 Div1 Easy - FoxPaintingBalls

f:id:creep040:20181009184504p:plain
これはどういうことですかね

問題

1辺の長さがnである正三角形を成すようにボールが並べられている (合計n(n+1)/2個)
このball triangleは無限にある
ball triangleのボールを全て赤or緑or青で、隣り合う2つのボールは違う色であるように塗りたい
赤緑青で塗れるボールの個数は最大でそれぞれr, g, bであるとき、最大で何個のball triangleを塗り切れるか

0 <= r, g, b <= 10^18
1 <= n <= 10^9

解法

同じ色が隣り合わないという制約より、ball triangleの塗り方は1頂点だけ決めると残りは一意に定まる
またp = n(n+1)/2とすると、使う色の個数は
n(or p)を3で割った余りが1のとき) 2色はp/3個で残りのもう1色はp/3+1個
そうでないとき) 3色ともp/3個
となる (∵ 1,2,3,...を3で割った余りは1,2,0,1,2,0,...と繰り返されるため和をとっていくと余りは0か1しかあり得ない)

↑を踏まえて二分探索する
m個のtriangleを塗るとすると、まずnの余りに関係なく3色それぞれpm/3回は塗る必要がある
nの余りが1のときはこれに加えてm回(独立に)塗る必要がある
残っている色の個数の総和とmの大小関係だけでこれが可能かは判断できる

(追記)
nの余りが1じゃないときは明らかに二分探索が要らなかった
まあ結果は変わらないから・・🧐💦

実装

オーバーフローに注意
pm/3がlonglongの上限を超えてたら引くまでもなく不可能とわかるからそこで終了していい

何も考えないで(le+ri)/2も避けたけど答えの上限が3e18だから別にそこは大丈夫だった

class FoxPaintingBalls {
public:
	ll theMax(ll r, ll g, ll b, int n) {
		ll p = (ll)n*(n+1)/2, le = 0, ri = 5e18;
		while (ri-le>1) {
			ll m = (le-ri)/2+ri, x = r, y = g, z = b, ok = 1;
			if (p/3*m/m!=p/3) ok = 0;
			x -= p/3*m, y -= p/3*m, z -= p/3*m;
			if (x<0 || y<0 || z<0) ok = 0;
			if (x+y+z<p%3*m) ok = 0;
			(ok ? le : ri) = m;
		}
		return le;
	}
};