- N段の三角形が無限にある。１つ１つはi段目にi個の球を置く形でビリヤードみたいになっている
- 各球を赤緑青の三色どれかで塗る。接する球は同じ色には塗れない。
- 赤緑青の色はそれぞれ R, G, B 回使える。
- 全部が塗られた三角形は最大何個作れるか。
- N≦10^9, R, G, B≦10^18
- １コの三角形について、１番上と（もしあれば）２番目の色を決めるとあとは全部一意に決まる。
- その三角形で使う各色の回数 (a, b, c) を求めるのにしばらく苦労して謎の複雑な関数が完成
- その回数(a, b, c)を赤緑青に最適に割り振って R, G, B を超えなければいい
- 最適な割り振り方がわからず、謎の貪欲法でサンプルが通ったので提出
- →failed system test
- あとで
- M = N(N+1)/2 として、(a, b, c) = (M/3, M/3, M/3 + M%3) となるらしい。(証明できず)
- さらに解を仮定した２分探索をするらしい。
- （そういえばこないだの高さを調整する問題も２分探索が思いつかなかったなぁ）
- 解を mid として
- どんな割り振り方でも最低 M/3 ずつは消費するので、R, G, B からそれぞれ mid * M/3 を引いて
- 大丈夫なら、mid * M%3 の分を残りの R, G, B でまかなえるか判定する。
↓あとで (passed system test in practice room)
class FoxPaintingBalls {
public:
long long theMax(long long R, long long G, long long B, int N) {
ll tot = (ll)N*(N+1)/2;
ll to3 = tot/3;
ll lo=0, hi=(R+G+B)/tot+1;
while(lo+1<hi) {
ll mid = (lo+hi)/2;
ll r=R-mid*to3;
ll g=G-mid*to3;
ll b=B-mid*to3;
if(r>=0 && g>=0 && b>=0 && (tot%3 ? (mid <= (r+g+b)/(tot%3)) : 1)) lo=mid;
else hi=mid;
}
return lo;
}
};
