HackerRank Boxes for Toys

問題文

https://www.hackerrank.com/contests/101hack50/challenges/boxes-for-toys

問題概要

N個の箱が一列に並んでいて, それぞれ大きさは a_i * b_i * c_i . これらは自由に回転させられる.
これらのうちランダムな区間を選び, 含まれる箱のどれでも包含することができるような箱の体積の最小値の期待値 mod 1e9+7 を求めよ.

解法

期待値なので任意の区間の値の総和を求めて N*(N+1)/2 で割る.

まず, 区間に含まれる箱をどれでも包含できる箱の体積の最小値を求める方法を考える.
各箱は自由に回転させられるが, この３つの辺を１番長いもの、２番目に長い辺、３番目に長い辺でそれぞれ独立に長さの最大値を求めてその積が最小になる.
これはすぐ証明できる.
しかし, これでもまだ O(N^2) かかる.

そこで, 分割統治で考えてみる.

区間が長さ１のとき, その体積を返す.
区間が長さ２以上のとき, 真ん中の２つを含むような任意の区間を数える.
左を一つずつ伸ばしながら固定すると, 右端は４つに分類できる.

• 各辺の左側の最大値が右側の最大値より３つとも大きいもの.
• 各辺の左側の最大値が右側の最大値より２つ大きいもの.
• 各辺の左側の最大値が右側の最大値より１つ大きいもの.
• 各辺の左側の最大値が右側の最大値より全て小さいもの.

これらはそれぞれ連続する区間になっていて, 各区間の右端での最小の体積の和はそれぞれの辺を使うか使わないかの bit 全列挙で全て求めておくと, いい感じに求まる.

すると各再帰で計算量は (区間の長さ) * 24 くらいなので全体で O(NlogN) でできる.

ソースコード

#include <bits/stdc++.h>
using namespace std;

// ライブラリ部分は省略 (mint : mod 取り構造体)

const int MAX = 3e5;

int a[3][MAX];
int ms[3][MAX];

mint calc(int lb, int ub) {
    if (ub - lb == 1) return mint(a[0][lb]) * a[1][lb] * a[2][lb];
    int m = (lb + ub) >> 1;
    mint res = calc(lb, m) + calc(m, ub);
    int rid[3] = { m, m, m };
    int lm[3] = {};
    int rm[3] = {};
    mint sum[4][8];
    mint all = 0;
    {
        int tm[3] = {};
        for (int i = m; i < ub; i++) {
            for (int j = 0; j < 3; j++) {
                tm[j] = max(tm[j], a[j][i]);
                ms[j][i] = tm[j];
            }
        }
    }
    for (int i = m; i < ub; i++) {
        all += mint(ms[0][i]) * ms[1][i] * ms[2][i];
    }
    for (int l = m - 1; l >= lb; l--) {
        for (int i = 0; i < 3; i++) {
            lm[i] = max(lm[i], a[i][l]);
        }
        for (int i = 0; i < 3; i++) {
            while (rid[i] < ub && rm[i] < lm[i] && a[i][rid[i]] < lm[i]) {
                for (int j = 0; j < 8; j++) {
                    mint v = 1;
                    for (int k = 0; k < 3; k++) if (j & (1 << k)) {
                        v *= ms[k][rid[i]];
                    }
                    sum[i][j] += v;
                }
                rm[i] = max(rm[i], a[i][rid[i]++]);
            }
        }
        int vs[3] = { 0, 1, 2 };
        sort(vs, vs + 3, [&](int i1, int i2) {
            return rid[i1] < rid[i2];
        });
        int s = 0;
        for (int i = 0; i < 4; i++) {
            mint kei = 1;
            for (int j = 0; j < 3; j++) if ((~s) & (1 << j)) {
                kei *= lm[j];
            }
            res += ((i < 3 ? sum[vs[i]][s] : all) - (i ? sum[vs[i - 1]][s] : 0)) * kei;
            if (i < 3) s |= 1 << vs[i];
        }
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[0][i] >> a[1][i] >> a[2][i];
        if (a[0][i] < a[1][i]) swap(a[0][i], a[1][i]);
        if (a[0][i] < a[2][i]) swap(a[0][i], a[2][i]);
        if (a[1][i] < a[2][i]) swap(a[1][i], a[2][i]);
    }
    mint res = calc(0, n) * 2 / n / (n + 1);
    cout << res << endl;
    return 0;
}

感想

かなりよくできてて面白い問題だと思った.
分割統治と決めてかかってもかなり難しくて, これをまともな時間で通せる気がしない.