Three Girls [Kodamanと愉快な仲間たち R]

https://www.hackerrank.com/contests/kodamanwithothers/challenges/three-girls

解説

https://www.hackerrank.com/contests/kodamanwithothers/challenges/three-girls/submissions/code/1316482864

3つ選択する部分があるが、3つ選ぶ系は真ん中を固定する場合が多い。 服を女らしさでソートしておき、define君が選ぶ服を全探索する。 define君が選ぶ服が固定になると、butsurizuki君は、A+x<B+Giを満たすxしか取れなくなる。 これはソート済みの服では区間になる。 この区間がどこからどこまでかは二分探索で特定可能なため、butsurizuki君が選ぶべき組み合わせが得られる。 同様にKodaman君が選ぶべき組み合わせも得られる。 これで、2つの組み合わせをかけ合わせたものの総和が答えになる。

注意点がいくつかある。 1つ目は、二分探索で取得する区間にdefine君が選んだものが含まれる場合は1だけ引く。 2つ目は、二分探索で得られる区間はかぶっている場合がある。 かぶっている部分については二重でカウントしてしまっているので、かぶっている部分での組み合わせは引く。

int N, A, B, C, G[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> A >> B >> C;
    rep(i, 0, N) cin >> G[i];
    sort(G, G + N);

    ll ans = 0;
    rep(d, 0, N) {
        // A + x < B + G[d]
        // x < B + G[d] - A
        int ok = -1, ng = N;
        while(ok + 1 != ng) {
            int md = (ng + ok) / 2;
            if (G[md] < B+G[d]-A) ok = md;
            else ng = md;
        }
        int bu = ok + 1;
        if (0 <= d and d <= ok) bu--;
        int L1 = 0, R1 = ok;

        // B + G[d] < C + x
        // B + G[d] - C < x
        ng = -1, ok = N;
        while (ng + 1 != ok) {
            int md = (ng + ok) / 2;
            if (B + G[d] - C < G[md]) ok = md;
            else ng = md;
        }
        int ko = N - ok;
        if (ok <= d and d < N) ko--;
        int L2 = ok, R2 = N - 1;

        ans += 1LL * bu * ko;

        int L = max(L1, L2);
        int R = min(R1, R2);
        if(L <= R) {
            int cnt = R - L + 1;
            if (L <= d and d <= R) cnt--;
            ans -= cnt;
        }
    }
    cout << ans << endl;
}