SRM 552 div1 easy FoxPaintingBalls

いろんな意味で嫌らしい問題だった…

問題

TopCoder Statistics - Problem Statement

i 行目に i 個のボールを並べるようにして N 行の三角形を作る。この三角形に色を塗るが,

• 塗る色は R, G, B の 3 種類のみ
• 三角形内の任意のボールについて, 隣り合ったボールとは色が異なっていなければならない

という条件を満たすように塗らなければならない。

R, G, B のボールを使って良い個数が与えられるので, 適当に組み合わせて N 行の三角形が最大何個生成できるか求めよ(場合の数を聞いているわけではないので注意)。

解法

N 行の三角形には合計で sum = N*(N+1)/2 個のボールがあります。
調べてみると,

• sum が 3 で割り切れる場合, 各色のボールは sum/3 個ずつ使う
• sum が 3 で割り切れない場合, 各色のボールは sum/3, sum/3, sum/3+1 個ずつ使う

ということがわかります。N = 1, 2, 3 の場合はそうなります。 N >= 4 の場合は, 真ん中のほうにあるボールが 必ず 6 個のボールに囲まれていますが, 6 個に囲まれていてかつ上記の条件を満たすためには,

というような形で並んでいる必要があります。これを考えると, 6 個のボールに囲まれたボールの色を決めるとすべてのボールの色が一意に定まります。で, 上のことがわかります。

以上のことから, need = sum/3 として, sum が 3 で割り切れる場合は, min(R/need, G/need, B/need) です。3 で割り切れない場合は二分探索をします。

f(x) = (x 個の三角形を作れるか)という問題を考えると, そもそも R-x*need, G-x*need, B-x*need のどれかが 0 未満になったらアウトです。そうでない場合は, これらの和が x 以上になっていれば, need+1 の +1 の分を賄えることが分かるので f(x) = true です。

気を付けないとオーバーフローするので注意。

class FoxPaintingBalls {
public:
    long long theMax(long long R, long long G, long long B, int N) {
        ll sum = (ll)(N+1)*N/2;
        ll need = sum/3;
        if (sum%3 == 0) {
            return min(R/need, min(G/need, B/need));
        } else {
            ll low = 0, high = max(1ll<<62, R+G+B);
            while (high - low > 1) {
                const ll med = (high+low)/2;
                auto f = [&]() {
                    if (R/med < need || G/med < need || B/med < need) return false;
                    ll r = R-med*need, g = G-med*need, b = B-med*need;
                    if (r+g+b >= med) return true;
                    else return false;
                };
                if (f()) low = med;
                else high = med;
            }
            return low;
        }
    }
};

久しぶりに問題解いたからかオーバーフローは全く意識してなくて, 2 箇所オーバーフローで死ぬところがありました。間抜け。