mayoko’s diary

プロコンとかいろいろ。

yukicoder No.376 立方体のN等分 (2)

解法

最大のものについては明らかに N-1 が答えです。

最小のものが問題ですが, よくわからない方法で解いてしまった感があります。

まず N の約数を全列挙します。これをすべて格納した配列を div として, 後は約数の組 (div[i], div[j], div[k]) を全列挙すれば良いです。

ただ, これだと遅そうなので工夫をしていきます。まず, i, j を決めれば k については割り算で決定すれば良いだけなので, i, j だけ考えるようにしましょう。

で, i, j については, div[i] <= div[j] が成り立つようにします。こうすると, 必要な分割平面の数は, 少なくとも div[i]+div[j]-3 >= 2*div[i]-3 であると見積もれます。ans がある程度の値になっている場合, ans <= 2*div[i]-3 だったら枝刈りする, という高速化ができます。

また, div[i]*div[j] > N の場合は, j をそれより大きくする必要はないので, これで j についても枝刈りができます。

以上の枝刈りをすると, 十分高速に答えを求めることができました。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    vector<ll> div;
    for (ll i = 2; i*i <= N; i++) {
        if (N%i == 0) {
            div.push_back(i);
            if (i*i != N) div.push_back(N/i);
        }
    }
    sort(div.begin(), div.end());
    int sz = div.size();
    ll ans = N-1;
    for (int i = 0; i < sz; i++) {
        if (ans+3 <= 2*div[i]) break;
        for (int j = i; j < sz; j++) {
            ll tmp = div[i]*div[j];
            if (N < tmp) break;
            if (N%tmp) continue;
            tmp = N/tmp;
            ans = min(ans, div[i]+div[j]+tmp-3);
        }
    }
    cout << ans << " " << N-1 << endl;
    return 0;
}