SRM 507 div1 med:CubePacking

本番出したのは計算量の見積もりが甘くてclimpetさんにギリギリまで追い込まれました。

問題

TopCoder Statistics - Problem Statement

解法

B = Nc + Nb * L^3とします。最低でもこの体積分は必要です。
また,実は調べるべき体積はBからB+L^3で抑えられることもわかります(L^3をNb個縦に並べると考える)。
よって,意外に調べる範囲は大したことないのであとは体積Vに対してVですべての立方体が収まるかどうかを判定できれば嬉しいです。ということでこれをそこそこ高速で判定できれば勝ちです。

そのためには,V = a*b*cとなるa, b, cについて
(a/L) * (b/L) * (c/L) >= Nb
が成り立てば良いです。これを調べるためにVの約数を列挙して対応を調べます。

int ns, nb, l;
ll start;

bool ok(ll v) {
    vector<ll> div;
    for (ll i = 1; i * i <= v; i++) {
        if (v%i == 0) {
            div.push_back(i);
            if (i*i != v) div.push_back(v/i);
        }
    }
    int m = div.size();
    sort(div.begin(), div.end());
    for (int i = 0; i < m; i++) {
        for (int j = i; j < m; j++) {
            ll tmp = v/div[i]/div[j];
            if (div[i]*div[j]*tmp != v) continue;
            ll p = div[i]/l;
            ll q = div[j]/l;
            ll r = tmp/l;
            if (p*q*r >= nb) return true;
        }
    }
    return false;
}

class CubePacking {
public:
    int getMinimumVolume(int Ns, int Nb, int L) {
        ns = Ns, nb = Nb, l = L;
        ll V = (ll)L*L*L;
        start = V*Nb + Ns;
        for (ll v = start; ; v++) {
            if (ok(v)) return v;
        }
    }
};