読者です 読者をやめる 読者になる 読者になる

n-knuu's logs

憧れ駆動。だいたい競プロ

SRM552 div.1 250 FoxPaintingBalls

二分探索 topcoder

練習会で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は作れるので、これをもとに二分探索すればよい。

コード

C++はオーバーフローがつらそうだった(練習会終わったあとにC++で書きなおしたら、手元ではオーバーフローするけど、Run System Testは通るようなコードが生成されて悲しい気持ちになった)