SRM552 div.1 250 FoxPaintingBalls
練習会で1完だった
問題
TopCoder Statistics - Problem Statement
リンク先の図のように、ボールを並べてN段のtriangleにR,G,Bの3色で、ボールどうしで色が隣り合わないように色を塗る(図はN=3)とする。
R, G, Bで塗れる回数がそれぞれ決まっているときに、最大何個のN段のtriangleを作ることができるか？
制約
0 <= R, G, B <= 10^18
1 <= N <= 10^9
解法
並べてみればわかるが、Nによって必要なボールの数はほぼ決まる。
さらに、N%2≠1のときは、全てのボールの数が同じなり、N%2=1のときは、1種類だけ必要なボールの数が1つ多くなる。
3の倍数ごとに必要な数を見ていくと、階差数列になっていることがわかり、N段のtriangleを1個作るのに必要な個数を計算すると以下のようになる。
n=(N-1)/3+1とすると、
- N%2=0 のとき: 3種類とも n*(3*n+1)/2 個
- N%2=1 のとき: 2種類は 3*n*(n-1)/2 個で、1種類は 3*n*(n-1)/2 + 1 個
- N%2=2 のとき: 3種類とも n*(3*n-1)/2
よって、N%2≠1のときは、min(R, G, B) / (必要な個数)
N%2=1のときは、二分探索をする。
c=3*n*(n-1)/2と置くと、min(R, G, B) >= c * M かつ R+G+B >= M(3 * c + 1) を満たせば、M個のtriangleは作れるので、これをもとに二分探索すればよい。
