今のところ自分が作った問題の中では最高傑作。~~にしてはストーリーが暴走気味。~~
問題へのリンク

問題概要

$N$ 個の 1次関数 $f_1, f_2, \cdots , f_N$ が与えられます。
$i$ ( $1 \leq i \leq N$ ) 番目の関数は $f_i (x) = a_i x + b_i$ です。
このとき、以下のクエリが $Q$ 個与えられるので答えてください。

整数 $x$ が与えられる。このとき、 $f_q( f_p(x) )$ ( $p \ne q$ ) の最大値を出力してください。

略解

惚れ薬を1回しか使わない場合は、Convex Hull Trick により充分高速に解くことができます。
また、1回目に選ぶべき惚れ薬の候補は、好感度が1番大きくなるもの、2番目に大きくなるもの、1番小さくなるもの、2番目に小さくなるもの、の4つしかありません。
なぜなら、1回目に上記以外のものを選んだ場合、1回目の惚れ薬を制約に反することなく上記のもののどれかに変更することが可能であり、なおかつ、そのような変更によって結果が悪化しないような惚れ薬が上記のものの中に必ず存在するからです。
よって、1回目に選ぶべき惚れ薬の候補は高々定数個しかないので、惚れ薬を1回しか使わない場合の問題に帰着させて解くことが可能です。

解説

まず、より簡単な問題として惚れ薬を1回しか使わない場合について考えてみます。この問題は、Convex Hull Trick により充分高速に解くことができます。
（writerはLi Chao Treeを用いて実装したので、1クエリあたり $O(\log Q)$ かかる。以下、Li Chao Treeを用いた場合を想定。）

これを踏まえて、惚れ薬を2回使う場合について考えます。愚直な解法として、1回目に使う惚れ薬を全通り試す方法が考えられます。 1回目に使う惚れ薬を固定すると、先程の惚れ薬を1回しか使わない場合の解法が利用できるようになります。先程と違うのは、「1回目に使った惚れ薬を使ってはならない」という点のみであり、これは「左右からの累積を考える」や「Segment Treeを用いる」ことによって処理することができます。前者の方法により処理した場合の計算量は $O(QN \log Q)$ となるため、正解するためには高速化をする必要があります。

そこで、より効率的な解法を考えてみましょう。まず、惚れ薬を選ぶ戦略ですが、

1回目: 使用後の好感度がなるべく大きく or 小さくなるように選ぶ
2回目: 1回目で使ったものを除いた惚れ薬の中から、使用後の好感度がなるべく大きくなるように選ぶ

のが最適です。惚れ薬による好感度の変化は、1次関数で表されているため（広義）単調増加か（広義）単調減少の2種類しかありません。そのため、好感度を最大化する方法として考えられるのは以下の2つしかありません。

1回目で好感度をなるべく大きくして、2回目で（広義）単調増加となるものを使用
1回目で好感度をなるべく小さくして、2回目で（広義）単調減少となるものを使用

この問題では、「1回目と2回目で重複を許す場合において、2回とも同じものを選ぶのが最適となるケース」をどのように処理するかが鍵となります。なぜなら、重複を許す場合においても2回目で1回目と異なるものを選ぶのが最適な場合、 1回目と2回目でそれぞれ「惚れ薬を1回しか使わない場合」の解法を適用することによって解けてしまうからです。 2回とも同じものを選ぶのが最適になってしまうケースでは、少なくともどちらかの選択を変更する必要があります。 2回目の選択を変更する場合における選択の仕方は、これまでの議論から明らかです。では、1回目の選択を変更する場合において、どのように選択するのが良いのでしょうか？

実は、1回目に選ぶべき惚れ薬の候補は以下の高々4つしかありません。

使用後の好感度が1番大きくなる惚れ薬（ $i_1$ とする）
使用後の好感度が $i_1$ を除いて1番大きくなる惚れ薬（ $i_2$ とする）
使用後の好感度が1番小さくなる惚れ薬（ $i_3$ とする）
使用後の好感度が $i_3$ を除いて1番小さくなる惚れ薬（ $i_4$ とする）

（これらの条件を満たす惚れ薬の候補は複数通り考えられますが、何でも良いので1つ取ってこれば大丈夫です。）

よって、1回目に使う惚れ薬としてこれらの4つを全て試し、先程の愚直な解法と同様に処理することで、この問題を充分高速に解くことができます。
（writerの想定解の実装の計算量は $O( (N + Q)(\log N + \log Q) )$ 。)

「1回目に選ぶべき惚れ薬の候補が高々4個しかない」ことの証明

1回目に選んだ惚れ薬を $i$ 、 2回目に選んだ惚れ薬を $j$ とします ( $i \ne j$ )。また、 $y = a_i x + b_i$ 、 $z = a_j y + b_j$ とします。目標は、 $z$ の最大化です。
2回目の惚れ薬を1つ固定した場合において、1回目の惚れ薬をどのように選ぶのが最適であるかを考えます。
2回目に選ぶものについて、 $a_j \ge 0$ と $a_j \lt 0$ で場合分けしてみます。

(1) $a_j \ge 0$

$y$ が大きいほど、 $z$ は大きくなります。なので、 $i$ は $y$ がなるべく大きくなるように選択するのが最適です。 $y$ が1番大きくなるのは $i = i_1$ のときなので、 $a_j \ge 0$ かつ $j \ne i_1$ を満たすような $j$ を2回目に選ぶ場合は、1回目に $i_1$ を選ぶのが最適です。 $a_{i_1} \lt 0$ の場合、 $a_j \ge 0$ を満たす全ての $j$ について考慮出来ています。しかし、 $a_{i_1} \ge 0$ を満たす場合、 $j = i_1$ の場合について考える必要があります。 $j = i_1$ の場合、 $i$ は $i \ne i_1$ かつ $y$ がなるべく大きくなるように選ぶのが最適です。つまり $y$ が2番目に大きくなるような $i$ ( $= i_2$ ) を選べば良いです。以上の考察より、2回目に $a_j \ge 0$ となるような $j$ を選ぶ場合、1回目は $i_1$ か $i_2$ のどちらかを選択するのが最適です。

(2) $a_j \lt 0$

$y$ が小さいほど、 $z$ は大きくなります。なので、 $i$ は $y$ がなるべく小さくなるように選択するのが最適です。 (1)と同様の考察をすると、 2回目に $a_j \lt 0$ となるような j を選ぶ場合、 1回目は $y$ が1番小さくなるような $i$ ( $= i_3$ ) か $y$ が2番目に小さくなるような $i$ ( $= i_4$ ) のどちらかを選択するのが最適です。

以上の考察より、 $z$ を最大化するために最適な選択は以下の4つの中に必ず含まれることがわかります。

1回目で $i_1$ を選び、2回目で $i_1$ 以外で $z$ が最大となる惚れ薬を選択
1回目で $i_2$ を選び、2回目で $i_1$ を選択
1回目で $i_3$ を選び、2回目で $i_3$ 以外で $z$ が最大となる惚れ薬を選択
1回目で $i_4$ を選び、2回目で $i_3$ を選択

writer解

#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

using ll = long long;
using P = pair<ll, ll>;

const ll INF = 3e18;

// 参照: https://github.com/LumaKernel/lib-cpp/blob/master/src/dynamic-programming/convex-hull-trick/LiChaoTree.cpp
// 最小化: Comp = less<T>, 最大化: Comp = greater<T>
template<class T = ll, class Comp = less<T> >
struct LiChaoTree {
    using Line = pair<T, T>;
    static inline T f(const Line& line, T x) { return line.first * x + line.second; }

    static Comp comp;

    int n;
    vector<Line> data;
    vector<int> used;
    vector<T> xs;

private:
    // [l, r)
    void add(int l, int r, const Line& line) {
        int l0 = l, r0 = r;
        int sz = 1;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1, sz <<= 1) {
            if (l & 1) add(l, l0, l0 + sz, line), l0 += sz, ++l;
            if (r & 1) --r, r0 -= sz, add(r, r0, r0 + sz, line);
        }
    }

    void add(int k, int l, int r, Line line) {
        if (!used[k]) {
            used[k] = true;
            data[k] = line;
            return;
        }

        T cur_ly = f(data[k], xs[l]), cur_ry = f(data[k], xs[r - 1]);
        T nex_ly = f(line, xs[l]), nex_ry = f(line, xs[r - 1]);

        if (comp(cur_ly, nex_ly) && comp(cur_ry, nex_ry)) return;
        if (comp(nex_ly, cur_ly) && comp(nex_ry, cur_ry)) {
            data[k] = line;
            return;
        }

        if (r - l == 1) return;

        int m = (l + r) >> 1;
        if (comp(cur_ly, nex_ly)) swap(data[k], line);
        if (comp(f(line, xs[m]), f(data[k], xs[m]))) {
            swap(data[k], line);
            add((k << 1) | 1, m, r, line);
        } else {
            add(k << 1, l, m, line);
        }
    }

public:
    // 前処理（事前にクエリのx座標を渡す必要あり）
    void addx(T x) { xs.emplace_back(x); }
    void prebuild() {
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());

        int sz = xs.size();
        n = 1;
        while (n < sz) n <<= 1;
        xs.resize(n, xs.back());

        data.resize(n << 1);
        used.resize(n << 1);
    }

    // 直線追加: ax + b
    void add(T a, T b) { add(0, n, Line(a, b)); }

    // 線分追加: ax + b (l <= x <= r)
    void add(T a, T b, T l, T r) {
        int li = lower_bound(xs.begin(), xs.end(), l) - xs.begin();
        int ri = upper_bound(xs.begin(), xs.end(), r) - xs.begin();
        add(li, ri, Line(a, b));
    }

    // ax+bが最小/最大となる(a,b)を取得
    Line get(T x) {
        int idx = -1;
        for (int i = lower_bound(xs.begin(), xs.end(), x) - xs.begin() + n; i > 0; i >>= 1) {
            if (!used[i]) continue;
            if (idx == -1 || comp(f(data[i], x), f(data[idx], x))) idx = i;
        }
        assert(idx > 0 && idx < (n << 1));
        return data[idx];
    }

    // ax+bの最小/最大値を取得
    T query(T x) { return f(get(x), x); }
};

template<class T, class Comp>
Comp LiChaoTree<T, Comp>::comp;

template<class Comp = greater<ll> >
vector< vector<int> > calcRank1(int n, const vector<ll>& a, const vector<ll>& b, 
                            int q, const vector<ll>& x, map<P, int>& ids) 
{
    LiChaoTree<ll, Comp> cht;
    for (int i = 0; i < q; ++i) {
        cht.addx(x[i]);
    }
    cht.prebuild();

    for (int i = 0; i < n; ++i) {
        cht.add(a[i], b[i]);
    }

    // rank1[i]:
    // i番目の惚れ薬を使うと好感度が最大/最小となるようなクエリ番号の集合
    vector< vector<int> > rank1(n);
    for (int i = 0; i < q; ++i) {
        int j = ids[cht.get(x[i])];
        rank1[j].push_back(i);
    }
    return rank1;
}

template<class Comp = greater<ll> >
vector<int> calcRank2(int n, const vector<ll>& a, const vector<ll>& b, 
                            int q, const vector<ll>& x, map<P, int>& ids,
                            const vector< vector<int> >& rank1) 
{
    LiChaoTree<ll, Comp> chtL;
    for (int i = 0; i < q; ++i) {
        chtL.addx(x[i]);
    }
    chtL.prebuild();

    LiChaoTree<ll, Comp> chtR = chtL;

    // rank2[i]: i番目のクエリにおいて、好感度が2番目に大きく/小さくなるような惚れ薬の番号
    vector<int> rank2(q, -1);
    Comp comp;
    for (int i = 0; i < n; ++i) {
        if (i > 0) {
            for (int j : rank1[i]) {
                int k = ids[chtL.get(x[j])];
                ll val = a[k] * x[j] + b[k];

                if (rank2[j] == -1 || comp(val, a[rank2[j]] * x[j] + b[rank2[j]])) {
                    rank2[j] = k;
                }
            }
        }

        chtL.add(a[i], b[i]);
    }

    for (int i = n - 1; i >= 0; --i) {
        if (i < n - 1) {
            for (int j : rank1[i]) {
                int k = ids[chtR.get(x[j])];
                ll val = a[k] * x[j] + b[k];

                if (rank2[j] == -1 || comp(val, a[rank2[j]] * x[j] + b[rank2[j]])) {
                    rank2[j] = k;
                }
            }            
        }

        chtR.add(a[i], b[i]);
    }

    return rank2;
}

vector<ll> solve(int n, const vector<ll>& a, const vector<ll>& b, 
                int q, const vector<ll>& x, map<P, int>& ids,
                const vector< vector<int> >& rank1_max,
                const vector< vector<int> >& rank1_min,
                const vector<int>& rank2_max,
                const vector<int>& rank2_min) 
{
    // cands[i]: 1回目にi番目の惚れ薬を使うようなクエリ番号の集合
    vector< vector<int> > cands(n);

    for (int i = 0; i < n; ++i) {
        for (int j : rank1_max[i]) {
            cands[i].push_back(j);
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j : rank1_min[i]) {
            cands[i].push_back(j);
        }
    }

    for (int i = 0; i < q; ++i) {
        cands[rank2_max[i]].push_back(i);
    }

    for (int i = 0; i < q; ++i) {
        cands[rank2_min[i]].push_back(i);
    }

    LiChaoTree<ll, greater<ll> > chtL;
    for (int i = 0; i < n; ++i) {
        for (int j : cands[i]) {
            chtL.addx(a[i] * x[j] + b[i]);
        }
    }
    chtL.prebuild();

    auto chtR = chtL;

    vector<ll> ans(q, -INF);
    for (int i = 0; i < n; ++i) {
        if (i > 0) {
            for (int j : cands[i]) {
                ll val = chtL.query(a[i] * x[j] + b[i]);
                ans[j] = max(ans[j], val);
            }
        }

        chtL.add(a[i], b[i]);
    }

    for (int i = n - 1; i >= 0; --i) {
        if (i < n - 1) {
            for (int j : cands[i]) {
                ll val = chtR.query(a[i] * x[j] + b[i]);
                ans[j] = max(ans[j], val);
            }
        }

        chtR.add(a[i], b[i]);
    }

    return ans;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;

    vector<ll> a(n), b(n);
    map<P, int> ids;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
        ids[P(a[i], b[i])] = i;
    }

    int q;
    cin >> q;

    vector<ll> x(q);
    for (int i = 0; i < q; ++i) {
        cin >> x[i];
    }

    auto rank1_max = calcRank1< greater<ll> >(n, a, b, q, x, ids);
    auto rank1_min = calcRank1< less<ll> >(n, a, b, q, x, ids);

    auto rank2_max = calcRank2< greater<ll> >(n, a, b, q, x, ids, rank1_max);
    auto rank2_min = calcRank2< less<ll> >(n, a, b, q, x, ids, rank1_min);

    vector<ll> ans = solve(n, a, b, q, x, ids, rank1_max, rank1_min, rank2_max, rank2_min);
    for (int i = 0; i < q; ++i) {
        cout << ans[i] << "\n";
    }
    return 0;
}

こんな無茶苦茶なストーリーの問題を出題することを許可してくれたスギノキさん、本当にありがとうございます。

ビビジランテソンテネグロホメストーニカルマンドーレポポス

さあ、いつまでたってもオレンジコーダーになれない子はどんどんしまっちゃおうねー

OUPC2020 H. ラブラブデート大作戦スギノキさん解説

問題概要

略解

解説

「1回目に選ぶべき惚れ薬の候補が高々4個しかない」ことの証明

(1) $a_j \ge 0$

(2) $a_j \lt 0$

writer解

コメント