2020-12-12

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

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

問題概要

$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;
}

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

2020-12-12

OUPC2020 E. Xor Mart 解説

人生で初めて作った問題。いかがだったでしょうか。
問題へのリンク

略解

半分全列挙とAtCoderのXXORで出てくる考え方を組み合わせると解けます。

解説

この問題において、「支払う金額を各商品の金額の総和で計算する」と問題の設定を変更した場合、これは典型的なナップサック問題と等しくなります。
上記のような設定の変更を行った問題は、 $N$ が充分小さいので半分全列挙+金額に対する二分探索による結果のマージを行うことで解くことができます。
（参考: AtCoder ABC032 D）

しかし、この問題においては「支払う金額を各商品の金額の排他的論理和で計算する」ため単調性が成立しなくなります。なので、金額に対する二分探索による結果のマージは利用できません。

そこで、他の方法による結果のマージを考えます。
まず、商品の集合を2つの集合 $S$ , $T$ に分割するものとします。また、 $S$ および $T$ から選ばれた商品の集合における支払う金額をそれぞれ $x$ , $y$ とします。さらに、最終的に支払う金額を $z = x \oplus y$ とすると、 $z \leq M$ を満たす必要があります。
このとき、 $z$ を2進数表記したもののprefixに関して分類を行うと、
実は高々 $O(\log M)$ 種類しかないことがわかります。
$y = z \oplus x$ より、 $z$ のprefix および $x$ を固定すると $y$ のprefixは一意に定まります。
同じprefixを持つものについてはまとめて計算することが可能（詳細はwriter解を見てください）なので、
$z$ のprefix および $x$ を全探索することで解を求めることができます。
writerの実装の計算量は $O(2^{N/2} N \log M)$ となっています。

prefixに関する分類

「 $z$ を2進数表記したもののprefixに関する分類」について例を用いて説明します。
例えば、 $M$ を10進数表記で 150 とすると、2進数で表すと 10010110 となります。
ここで、0と1のどちらでも良いビットを X と表記することにすると、
$z$ のprefixは必ず以下のどれかになります。

0XXXXXXX
1000XXXX
100100XX
1001010X
10010110

このような分類は、 $z$ の値を最上位ビットから順番に決定していくことで得られます。
$z$ の値が $M$ 未満となることが確定した場合、残りのビットは必ずXとなります。
このような分類の数は、高々 $O(\log M)$ 個しかありません。
（このような分類方法は、桁DPなどで使われている考え方です。けんちょんさんの記事が参考になると思います。）

writer解

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

using namespace std;

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

constexpr char newl = '\n';
constexpr ll INF = 1e16;

// 半分全列挙する関数
vector<P> rekkyo(int L, int R, vector<ll>& A, vector<ll>& B) {
    int n = R - L;
    map<ll, ll> memo;
    for (int i = 0; i < (1 << n); i++) {
        ll money = 0;
        ll value = 0;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                money ^= A[L + j];
                value += B[L + j];
            }
        }
        
        // memo[money] = max(memo[money], value); だけだとダメ！！！
        // memo[money]でやるとデフォルトの値が0になるが、
        // valueが負になる場合があるので死ぬ
        if (memo.find(money) == memo.end()) memo[money] = value;
        else memo[money] = max(memo[money], value);
    }

    vector<P> res;
    for (auto& p : memo) res.push_back(p);
    return res;
}

// 0と1のどちらでも良いビットを切り捨てて、同じprefixのものをまとめていくための関数
vector<P> update(const vector<P>& v, int shift) {
    // rekkyo() により v はソートされており、
    // なおかつ、update()によりソートの順番が崩壊することはないので線形で処理が可能
    if (shift == 0) return v;  // shiftしないなら v は変化しない
    vector<P> nex;
    for (const P& p : v) {
        ll tar = (p.first >> shift);
        if (!nex.empty() && nex.back().first == tar) {
            nex.back().second = max(nex.back().second, p.second);
        } else {
            nex.emplace_back(tar, p.second);
        }
    }
    return nex;
}

ll solve(int N, ll M, vector<ll>& A, vector<ll>& B) {
    vector<P> v1 = rekkyo(0, N / 2, A, B);
    vector<P> v2 = rekkyo(N / 2, N, A, B);

    ll res = 0;
    while (M >= 0) {　// prefixに関する分類をMから順番に降順に見ていく
        for (P& p : v1) {
            ll tar = p.first ^ M;
            auto it = lower_bound(v2.begin(), v2.end(), P(tar, -INF));
            if (it == v2.end()) continue;  // 不正な値にアクセスしないように
            P p2 = *it;
            if (p2.first != tar) continue;
            ll value = p.second + p2.second;
            res = max(res, value);
        }

        if (M == 0) break;
        
        // 次に見るprefixを計算
        int shift = 0;
        while (M > 0 && (M & 1) == 0) {
            M >>= 1;
            shift++;
        }
        M ^= 1;

        v1 = update(v1, shift);
        v2 = update(v2, shift);
    }
    return res;
}

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

    int N;
    ll M;
    cin >> N >> M;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

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

    cout << solve(N, M, A, B) << newl;

    return 0;
}

testerさんに解いてもらった結果、大量の嘘解法と別解が飛び交ってかなり焦りました。別解の中にはwriterの想定解より効率の良い解法もありました。
自力でACできた方も他の解法を考えてみると面白いかもしれません。

2020-08-16

多点BFS 解説

はじめに

「多点BFS」でググったときに出てくる一番まともな解説が僕のツイートであることに危機感を覚えたので（雑な）解説記事を書くことにしました。（ツイ消ししてしまう可能性があるので）

多点BFSは、始点を一つ作って、そこからコスト0の辺が多点(今回だと黒いマス)につながってるグラフを考えて、始点から普通のBFSをするっていうのを思い浮かべるとわかりやすい
— fine (@refine_P) 2019年5月4日

多点BFS とは

通常のBFSを、さらに始点が複数になっても扱えるように拡張したものが多点BFSです。
「始点が複数あって、各終点に対してそれぞれの始点との最短距離を計算した上でそれらの最短距離の最小値を求めたい」みたいなときに使います。
英語だと、multi-source BFSって言うっぽい？
多点BFSもmulti-source BFSもあまりメジャーな用語ではなさそうなので、使うときにはちょっと注意した方が良さそう？

多点BFSで解ける問題

数式を使って、もう少し厳密に書くと以下の通りになります。

$K$ 個の始点 $s_1,\cdots,s_K$ が与えられるものとし、これらの始点の集合を $S$ とする。このとき、各終点 $t$ に対して $\min \{ dist(i, t) \ | \ i \in S \}$ を求めよ。
ただし、 $dist(i, t)$ は始点 $i$ から終点 $t$ までの最短距離を表す。

これを通常のBFSと同じ計算量で解けるのが多点BFSです。

アルゴリズム (実装)

通常のBFSからの変更点は以下の2つだけです。

最初に全ての始点をキューに追加する。
全ての始点において最短距離の値（求めたい値）を0に初期化する。

発想

元のグラフに対して、新しい（ダミーの）頂点を1つ追加し、その頂点から全ての始点に対してコスト0の辺を追加することを考えます。
このとき、それぞれの始点と各終点の最短距離は、新しく追加した頂点からそれぞれの始点を通って各終点に向かう場合の最短距離と等しくなります。
よって、求めたい値は、新しく追加した頂点と各終点の最短距離に等しくなります。

なので、新しく追加した頂点から通常のBFSをすれば、求めたい値が計算できます。
このBFSをシミュレートすると、

キューに入っているのは始点の集合のみ
全ての始点において最短距離の値が0である

という2つの条件を満たすような状態に必ずたどり着くので、結局のところ、先程のアルゴリズムで問題ないことがわかります。

問題例

ゾンビ島
僕が、初めて多点BFSに出会った問題です。
A - Darker and Darker
この問題が出題されたときに多点BFSの解説ツイートをしました。

発展

新しく頂点や辺を追加することで問題を解きやすくするというアイデアは、割と重要なので覚えておくと良さそうです。
参考になりそうな記事を載せておきます。

コスト0辺のテクニック - Senの競技プログラミング備忘録
 区間に辺を貼る一般的なテクニック - 情報妖精の競プロ日記

おまけ（元ツイートの魚拓）

多点BFSは、始点を一つ作って、そこからコスト0の辺が多点(今回だと黒いマス)につながってるグラフを考えて、始点から普通のBFSをするっていうのを思い浮かべるとわかりやすい

2020-03-21

【OUPC β】ビブンケイスウ解説

問題

writer: fine
問題文のストーリー部分: sarashin(Nキチ)
URL: https://www.hackerrank.com/contests/oupc-beta/challenges/bibun-keisu

解説

クエリ2で聞かれている $g'(0)$ の値は、
$x$ についての多項式 $g(x)$ の1次の項の係数に等しい。

例えば、 $g(x)$ が2つの1次関数をかけ合わせたものである場合、
すなわち、 $g(x) = (ax+b) (cx+d)$ とすると、 $g(x) = acx^ 2 + (ad+bc) x + bd$ であり、 $g'(0) = ad+bc$ となる。

ここで、 $g(x)$ が複数の1次関数をかけ合わせたものであることから、
2次以上の項を無視して良いことがわかる。
すなわち、1次関数をかけ合わせるたびに2次以上の項を捨てることで、
より効率的な計算が可能となる。

以上より、1次関数 $f(x) = ax+b$ を $(a, b)$ と表記し、
2つの1次関数に対する演算 $*$ を $(a, b) * (c, d) = (ad+bc, bd)$ と定義したとき、クエリ2において、 $f_l(x) * \cdots * f_r(x) = (g'(0), g(0))$ となることがわかる。

後は、1次関数と演算 $*$ をSegment Treeに載せれば解ける。

Writer解

#include <iostream>
#include <vector>

using namespace std;

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

const ll MOD = 1000000007;

template <class Monoid>
struct SegmentTree {
    using T = typename Monoid::T;

    int n;
    vector<T> data;

    SegmentTree() {}

    SegmentTree(int size, T initial_value = Monoid::unit()) {
        n = 1;
        while (n < size) n <<= 1;
        data.assign(2 * n - 1, initial_value);

        if (initial_value != Monoid::unit()) {
            for (int i = n - 2; i >= 0; i--) data[i] = Monoid::merge(data[i * 2 + 1], data[i * 2 + 2]);
        }
    }

    SegmentTree(const vector<T>& v) {
        int size = v.size();
        n = 1;
        while (n < size) n <<= 1;
        data.assign(2 * n - 1, Monoid::unit());

        for (int i = 0; i < size; i++) data[i + n - 1] = v[i];
        for (int i = n - 2; i >= 0; i--) data[i] = Monoid::merge(data[i * 2 + 1], data[i * 2 + 2]);
    }

    void update(int k, T x) {
        k += n - 1; //葉の節点
        Monoid::update(data[k], x);
        while (k > 0) {
            k = (k - 1) / 2;
            data[k] = Monoid::merge(data[k * 2 + 1], data[k * 2 + 2]);
        }
    }

    //区間[a, b)に対するクエリに答える
    //k:節点番号, [l, r):節点に対応する区間
    T query(int a, int b, int k, int l, int r) {
        //[a, b)と[l, r)が交差しない場合
        if (r <= a || b <= l) return Monoid::unit();
        //[a, b)が[l, r)を含む場合、節点の値
        if (a <= l && r <= b) return data[k];
        else {
            //二つの子をマージ
            T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
            T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
            return Monoid::merge(vl, vr);
        }
    }

    //外から呼ぶ用
    T query(int a, int b) {
        return query(a, b, 0, 0, n);
    }
};

// (1次の係数, 0次の係数)をpair<ll, ll>で持つ
template <class U = P>
struct RangeQuery {
    using T = U;
    static T merge(const T& x, const T& y) { 
        return T((x.first * y.second % MOD + x.second * y.first % MOD) % MOD, x.second * y.second % MOD);
    }
    static void update(T& target, const T& x) { target = x; }
    static constexpr T unit() { return T(0, 1); }
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    vector<ll> a(n), b(n);
    vector<P> v;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
        v.emplace_back(a[i], b[i]);
    }

    SegmentTree<RangeQuery<> > st(v);

    int q;
    cin >> q;
    for (int loop = 0; loop < q; ++loop) {
        int query_no;
        cin >> query_no;

        if (query_no == 1) {
            int p;
            ll c, d;
            cin >> p >> c >> d;
            --p;
            st.update(p, P(c, d));
        } else if (query_no == 2) {
            int l, r;
            cin >> l >> r;
            --l;
            
            cout << st.query(l, r).first << "\n";
        }
    }
    return 0;
}

2019-11-04

HACK TO THE FUTURE 2020予選参加記

HACK TO THE FUTURE 2020予選に参加しました。
最終成績は4970204点で、なんと予選1位でした！！！
まさか、自分がコンテストで優勝できるとは全く思っていなかったので、
メチャクチャ嬉しいです！！！！
今回は、優勝記念に参加記を書こうと思います。
自分が考えたことをなるべくたくさん書いた結果、読みにくい文章になっていて申し訳ないですが、頑張って読んでいただけると幸いです。

問題概要

まあ、問題概要は説明しなくても大丈夫ですよね？
A - ロボットの誘導

コンテスト中にやったこと

2:30 01BFS解法の実装 (4965088点)

とりあえず、ロボットがたくさんあるとややこしいので、ロボットが1台だけの場合を考えようと思いました。
ロボットを1台確実にゴールさせる方法があれば、その方法を使って貪欲にロボットをゴールさせれば良さそうだなあとか考えていました。
ロボットが1台しかない場合、方向案内をなるべく減らしつつ、ロボットが通るマスの数を増やせば良さそうです。

ひとまず、方向案内を減らすことだけ考えてみます。
これは曲がる回数を減らすということに等しいので、曲がる場合のコストを1、そうでない場合のコストを0とすれば、01BFSを使って最適な経路を求める事ができます。
後はロボットが通るマスの数を増やせば良くて、これは01BFSの実装をちょっと工夫すれば可能です。（このあたりは実装が面倒なので、自分が書いたコードも若干バグってる気がします...）

最終的なスコアを最大化する、すなわち、曲がる場合のコストを10、一度も通過していないマスを通過するコストを-1、それ以外のコストを0とした場合の合計コストを最小化するというアイデアも考えられますが、僕はこれを捨てました。
というのも、これはコストが負の値を取るような最短経路問題に帰着されるので、計算量が増えて面倒だし、負閉路が出てきても困るなあと思ったからです。

以上の過程を経て、ロボットを1台確実にゴールさせる方法が完成したので、後は各ロボットを順番にゴールさせるだけです。
この方法を使って全てのロボットをゴールさせられるかどうかについては、この時点では考えていませんが、とりあえず貪欲にやってみます。

まず、ロボットを1台ゴールさせて、その経路に応じて方向案内を埋めます。
次に、方向案内を埋めたフィールドで同様にロボットを1台ゴールさせます。
以上を全てのロボットについて行うことで、上手く行けば全員ゴールさせられるだろうという見込みです。

ここで、ロボットをゴールさせる順番について考える必要が出てくるのですが、とりあえず入力で与えられた順番で固定することにします。

以上を踏まえて、実装をした結果がこちらです。
Submission #8250246 - HACK TO THE FUTURE 2020予選

4965088点という非常に高い得点を獲得することができました。この得点は最終成績11位相当のスコアであり、ツカモさんのツイートをみる限りでは一般枠通過ラインの得点です。
この解法はかなりアルゴ色が強いため、マラソンマッチがあまり得意ではない人でも予選突破が可能なことが証明されたかなあと思っています。

本選ボーダーの速報値です。ちょっと年齢と枠が合わない人がいるのでさらに下がると思われますが、確実なラインは下記となってます。
新卒枠:109位
一般枠:11位
ユース枠:142位(地方枠は未算出)
— ツカモ (@tsukammo) November 2, 2019

しかし、ここまでで約2時間半が経過しており、初動にしては時間がかかりすぎているなあと反省しました。
初手はもっと素直で実装しやすい解法を試すべきなので、今後は気をつけていきましょう。

また、スコアの計算式を見る限り、ロボットをゴールさせることで得られる得点が大きいので、ロボットを全員ゴールさせることを優先するという考察の方がより自然であり、そのあたりをあまり考えなかったのも良くないなあという気持ちになりました。
ただ、上記のアイデアを実現するためにはBFSを実装する必要があり、BFSの実装はそこそこ時間がかかるので、これを経由せずに済んだのはかなりラッキーだったなあと思いました。
まあ、僕の解法もそこまで飛躍した発想ではないので、そこまで悪くはなかったかなあと思います。
今回は、解法ガチャが大成功したので、メチャクチャ運が良かったです。

3:00 使うロボットの順番を乱択 (4966980点)

先程の解法をSubmitした結果、暫定1位になれたので、とても驚きました。
しかも、先程の解法には自明な改善点がたくさんあるので、もうウキウキですｗｗｗ

暫定1位！ #HTTF pic.twitter.com/e2KSMct8Rh
— fine@競プロ (@refine_P) November 2, 2019

先程の解法では、ロボットをゴールさせる順番を固定していましたが、とりあえず順番を乱択することにしました。

その結果がこちら。
Submission #8251165 - HACK TO THE FUTURE 2020予選

これで4966980点を獲得し、得点を増やして暫定1位のままという結果になりました。
この時点で、コンテスト開始から3時間が経過しました。

この得点、最終成績4位相当のスコアなんですね、ヤバいなあ...

3:30 使うロボットの順番を山登り法で最適化 (4968361点)

ロボットをゴールさせる順番を乱択したので、次は山登り法で改善していきます。
遷移は適当に2点スワップにしておきます。

結果はこちら。
Submission #8251886 - HACK TO THE FUTURE 2020予選

これで4968361点を獲得し、得点を増やして暫定1位のままという結果になりました。
この時点で、コンテスト開始から3時間半が経過しました。

この得点で、最終成績3位相当のスコアみたいです。
最終成績2位のスコアを上回るスコアが出たのはかなり終盤だったので、1位と2位が相当強かったんだなあと思いました。

4:00 使うロボットの順番を焼きなまし法で最適化 (4968116点)

先程は山登り法を試したので、次は焼きなまし法の出番です。
パラメータを色々変えて一番良かったのがこちら。
Submission #8252337 - HACK TO THE FUTURE 2020予選

一番良くても4968116点なので、最高得点を更新することはできませんでした。
しかし、まだ順位は1位のままでした。

fineさんがリード。差が小さく見えるかもしれないけど、１位２位の差とそこから下の差を見ると、割ととんでもない差だったり。 #HTTF pic.twitter.com/DC50iMdugO
— chokudai(高橋直大)🌸🍆🍡 (@chokudai) November 2, 2019

前半戦が終了し、topはfineさん。
そろそろバテて来た人も、これから本気を出す人も、最後まで頑張って下さい！#HTTF pic.twitter.com/uDrJ74chG3
— ツカモ (@tsukammo) November 2, 2019

この時点でコンテスト開始から約4時間経過しており、自分が1位になってから約1時間半の間、順位がずっと1位のままだったので、
「普段TLとかで見ていた強い人達は一体どこへ行ってしまったのかな...？」
とか、考えていました。

考察タイム

点数が伸びなくなったので、きちんと考察（を整理）することにしました。

まず、得点やビジュアライザを見る限りでは、ロボットを全員ゴールさせることは難しくないため必須だとわかります。

また、全てのマスのうち約2割がブロックマスであり、なおかつ、それらが一様ランダムに選ばれることから、「あえて方向案内を増やして遠回りをすることでロボットが通るマスを増やし、その結果スコアが増える」といったことを実現するのはおそらく難しいだろうと考えました。
さらに、方向案内のスコアの重みが-10なのに対して、通ったマスのスコアの重みは1であるため、やはり、方向案内は可能な限り減らすのが得策だろうという結論になりました。

そして、スコアの伸びがそんなに大きくないことを考えると、通ったマスの数もできれば増やすほうがいいとわかります。

以上の考察を踏まえると、大まかな方針は今まで通りで良さそうだと結論付けることができました。

6:55 山登り法をチマチマ高速化 (4969195点)

というような考察をしていると、
「あなたの01BFS解法、制限時間内における試行回数はどれくらいですか？」
という天啓を得たので、調べることにしました。

コードテストを使うと、試行回数が80回ほどしかありませんでした。
それはそうで、僕の01BFS解法はO(MN²)でそこそこ重い計算のため、試行回数が稼げていませんでした。
そこで、焼きなまし法ではなく山登り法を使うことにして、01BFSの高速化を行うことにしました。

とりあえず、小手先の高速化として、多次元配列を1次元配列に潰すという改善を行いました。
さらに、実行時間ギリギリまで計算を回すようにコードを書き換えました。

以上を実装した結果がこちら。
Submission #8257165 - HACK TO THE FUTURE 2020予選

コードテストで調べた試行回数は330回程度で、最初の実装から約4倍の高速化に成功しました。
そして、4969195点を獲得し、得点を伸ばして暫定1位を維持しました。
この時点で、残り時間が1時間ほどとなりました。

残り１時間です。
fineさん、さらに伸ばして独走か？#HTTF pic.twitter.com/2C3KBn3Pvw
— ツカモ (@tsukammo) November 2, 2019

もう、ここまで来たら絶対に優勝したいなという気持ちでいっぱいでした。

7:18 方向案内をゴールとみなす (4969837点)

ほかに高速化できるところはないかを探すために、落ち着いて考察します。

先程の考察で、あえて方向案内を増やすことに意味がないことがわかりました。
なるべく方向案内を減らすためには、誰かが通ったルートに合流した時点でそのルートに乗っかるのが一番だとわかります。
なぜなら、01BFS解法においては、ゴールにたどり着ける経路しか考えないので、誰かが通ったルートを使えば確実にゴールできますし、さらに、合流した時点で方向案内をそれ以上設置する必要はないからです。
よく考えると、誰かが通ったルートに合流するタイミングというのは、「方向案内のマスを踏んだタイミング」に等しいことがわかるので、方向案内のマスをゴールとみなしてやると、01BFSの計算の枝刈りができます。

結局、僕の解法は、序盤で操作したロボットが作った流れに残りのロボットが乗っかっていくという仕組みで動いていたのだと気づきました。
さらに、方向案内は踏んだ時点で勝ちなので、あるロボットのために設置した方向案内が別のロボットの邪魔になることはなく、それゆえに、貪欲に1台ずつロボットをゴールさせても、全てのロボットをゴールさせることが可能なのだと理解しました。

というわけで、これらのアイデアを実装した結果がこちら。
Submission #8257955 - HACK TO THE FUTURE 2020予選

コードテストで調べた試行回数は800回程度で、最初の実装から約10倍の高速化に成功しました。
そして、4969837点を獲得し、得点を伸ばして1位の座を死守しました。
今回のコンテストでは、01BFS解法とこのアイデアが決め手になったような気がします。

追記 (2019/11/05 01:28)

確かに誰かが通ったルートを通るのは有効ですが、合流する際に（順路と逆向きの方向案内を用いて）ルートを逆走しないという条件を満たす必要があります。
確か、コンテスト中はそのあたりをあまり考えずに適当に修正して上手く動いたので、そのまま提出した記憶があります...
そのあたりをきちんと考えてソースコードを修正すると、試行回数が1000回程度になり、さらに焼きなまし法を用いると得点が4970314点と本番の最高得点を更新することができます。
Submission #8293678 - HACK TO THE FUTURE 2020予選

僕のソースコード（および解法）は全体的にバグってる可能性が高いので、あまり参考にしないことをオススメします。

7:49 焼きなまし法に変更 (4970204点)

もう残り時間が少ないので、出来ることは限られています。
どうしようかと思っていると、
「あなたの山登り解法は、制限時間を増やしたときにスコアが増えますか？」
という天啓を得たので、制限時間を30秒に増やしたときのスコアを眺めます。

スコアの伸びは小さいように見えたので、山登り法から焼きなまし法に変更することにしました。
（もはや、これくらいしか出来ることがなかったというのもありますが...）
そもそも試行回数があまり多くないので、焼きなまし法を使うのは適切でないように見えますが、 01BFS解法が優秀なので何とかなるだろうと信じることにします。

ラストスパート。パラメータを色々変えて、提出しまくります。
焼きなまし法のパラメータは、少し前に色々試したので、おおよその目星はついています。
後は全力で祈るだけです。どうか良いスコアが出ますように...。

というわけで一番良かった結果がこちら。
最終的に4970204点を獲得し、大台の497万点に到達することができました！
そして、競プロ人生で初めて、コンテストで優勝することができました！！！
Submission #8259128 - HACK TO THE FUTURE 2020予選

感想

振り返ると、自分が1位になってから5時間半の間、ずっと1位を独走し続けたんですね...
率直に言って物凄くカッコよくないですか？（僕は自分に起きた出来事だとは思えないくらいカッコいいと思います）
2位のats5515さんとの得点差はごくわずかだったので、最後まで全力で走り続けて良かったなあと思いました。

かなり運要素が強かったですが、なにはともあれ、競プロ人生初の1位なので、これからはこの実績でガンガンイキっていこうと思います。
本戦にはおそらく参加するはずなので、次は競プロ人生初の賞金獲得を狙っていこうと思います（あまり期待はしてないけど）。

HTTF2020予選、最終得点4970204で最終順位1位です！！！
競プロ人生で初めての1位！！！！！！
メチャクチャ嬉しい！！！！https://t.co/10jYveQwgQ #HTTF pic.twitter.com/LIkWQzo3vV
— fine@競プロ (@refine_P) 2019年11月2日

（このツイートに解法ツイートがぶら下がってるので、良かったら参考にしてください）

おまけ（没アイデア集）

ゴールから1回だけ01BFSの計算をしてよしなにやる

ゴールから01BFSをするやつを盛大にバグらせたのでボツ。
chokudaiさんが公式放送で言っていたツリーをよしなに構築できれば良いなあと思っていたけど難しそう。

01BFSの計算の途中経過を保存

毎回、全てのロボットについて01BFSを計算するのは無駄だなあと思っていたので、なんとかしたいなあと思っていたけど時間が足りず。

2点スワップでのロボットの選び方を工夫する

おそらくこの解法だと、序盤で操作するロボットを何にするかが重要になってくるはずなので、序盤のロボットが多めに選ばれるように乱数を調整すべきだったかなあとか思いました。

ロボットの順番で良さそうなやつを色々考える

例えば、ゴールから近い（遠い）順からゴールさせるとかは考えるべきっぽかったです。
個人的には、ロボットの距離が近いやつ同士を一つのグループとしてみなすクラスタリングをして、クラスタごとに最適化したらどうかなあとか考えていました。

2018-07-09

ICPC 2018 国内予選参加記

ICPC2018国内予選に大阪大学からチーム BFS として参加しました．大阪大学からは2チームが参加し，それぞれ4完38位（チーム BFS）と3完87位（チーム osaka_PFN）という結果になりました．全員でアジア地区予選に行けるようにチーム分けをしたのですが，アジア地区予選に行けそうなのは1チームだけという残念な結果となりました．

f:id:refine_P:20180708002143p:plain

チーム紹介

fine（自分）
sntea
Badlylucky

チーム名は，メンバーのハンドルネームの頭文字を取ってきて，いい感じに並べたら出来上がりました．
メンバーの実力は，自分とsntea君が青で，Badlylucky君が水色といった感じです．
一応，自分のレートがチームの中で一番高いのですが，sntea君の方が圧倒的に有能なので，結果的に自分は半分置物みたいな感じになってしまいました．アジア地区予選ではちゃんと活躍できるように頑張りたいです．

本番前

記録的な大雨の影響でBadlylucky君が大学に来れず，リモートでの参戦となってしまいました．
複数台のパソコンでの同時ログインはルール違反となるため，sntea君のパソコンで全てのコーディングを行い，Badlylucky君には問題の読解と考察を担当してもらうという割り振りになりました．
話し合いの結果，Badlylucky君がBの読解，sntea君がAとBの実装，自分がCの実装を担当して，後は流れでといった感じの作戦になりました．

本番

A問題は見た感じやるだけだったので，sntea君に丸投げしました．そしたら，sntea君は有能なので瞬殺してくれました．

B問題は見た感じヤバそうだったので，一抹の不安を感じつつ，自分の担当のC問題を解くことにしました．
緊張でテンパって無駄に式変形しまくったけど，よく考えれば考えるべきフロアの総数は高々sqrt(b)程度しかないことに気づいて楽勝じゃんってなりました．
sntea君がBの実装にかなり苦しんでいたので，パソコンを奪い取ってCの実装をしました．実装量はそこまで多くなかったので，あまり苦しまずにACできました．

D問題はsntea君が問題文は読んだといっていたので，自分はE問題を読むことにしました．
しかし，問題の内容が全く理解できなかったので，Badlylucky君にEの読解を投げました．
Badlylucky君が問題を読んで自分に色々教えてくれましたが，それでも理解できなかったので諦めて別の問題を解くことにしました．

他の問題を一通り見た結果，G問題がワンチャンありそうだったので，Gを解くことにしました．括弧内の式に関して，値が n になるものの個数を先に計算すれば，それ以降は括弧部分を式の計算結果の値として扱ってよいというアイデアが思いついたので，後は+と*をどう扱うかだなという気持ちになりました．
式の長さが長くなれば，計算結果の値も増えるから尺取りで何とかなるかなあという感じになったので，Bの実装に苦しむsntea君からパソコンを借りてGの実装に取り掛かりました．

Gの実装で詰まったので，sntea君にパソコンを返して，自分はD問題を読むことにしました（sntea君がDは問題文を読んだだけだと言っていたので）．
Dは見た感じ制約が小さそうなので枝刈りDFSかなという結論が出たところでDを放棄して，自分はG問題を考えていました．

そうこうしているうちに，sntea君がB問題をACしてくれたので，sntea君を褒め倒しつつ二人でD問題に挑みました．
自分は枝刈りDFSで解けそうと言ったのですが，sntea君から半分全列挙じゃないとダメだと言われてしまいました．
sntea君が説明してくれた半分全列挙解法が今ひとつ理解できなかったので，思考停止で丸投げしました（お前丸投げしてばっかだな）．そしたら，sntea君は有能なので気づいたらACしてました．

sntea君がDの実装をしている間にG問題が中々厳しいことに気づいたので（"*1"の扱いが面倒），Gを放棄して二人でE問題を解くことにしました．
自分がE問題の内容をsntea君に説明しているうちに，どうやら自分がEを誤読していた挙げ句（最終的にs=a*nになると思っていた．正しくはs=a*(n+1)），全く問題の主旨を理解していなかったことに気づきました．
Eの考察をsntea君が詰めてくれて，多分それで解けそうという感じになったので，実装をsntea君にお願いしました．
sntea君がEの実装をバグらせて辛そうにしているのを隣で見ながら祈っていると，EをACできないままコンテストが終了．
4完38位，学内1位でアジア地区予選進出圏内だったので，ひとまず安心といった感じでした．

反省

E問題を思いっきり誤読していたのが明らかにマズかったですね． Eの解法自体はそこまで難しいものではないので，自分が考察を詰めておけば5完できた気がします．

後，D問題の解法が枝刈りDFSだと主張するなら，枝刈りの仕方とかをしっかり考察しておくべきでした．
今回はたまたまACできましたが，半分全列挙は結構バグらせやすいイメージがあるので，バグったときに枝刈りDFSに方針を切り替えられるようにしておくべきでした．

それと，僕がコンテスト時間内に頑張って考察していたG問題も，他のチームが全然解いていない時点で切り捨てるべきでした．
考察自体はそこまで間違っていなかったと思いますが，明らかに実装が重いので，解かないという判断がベストだった気がします．

さいごに

記録的な大雨の影響により，中々厳しい戦いを強いられましたが，これも良い思い出になったかなと思います．（個人的に，Badlylucky君に対して通話で不定期に行われる生存確認がツボでした）

ひとまず，アジア地区予選には行けそうなので，osaka_PFNの分まで頑張れたらなと思います．

問題概要

略解

解説

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

(1)

(2)

writer解

コメント

略解

解説

prefixに関する分類

writer解

コメント

はじめに

多点BFS とは

多点BFSで解ける問題

アルゴリズム (実装)

発想

問題例

発展

おまけ（元ツイートの魚拓）

問題

解説

Writer解

問題概要

コンテスト中にやったこと

2:30 01BFS解法の実装 (4965088点)

3:00 使うロボットの順番を乱択 (4966980点)

3:30 使うロボットの順番を山登り法で最適化 (4968361点)

4:00 使うロボットの順番を焼きなまし法で最適化 (4968116点)

考察タイム

6:55 山登り法をチマチマ高速化 (4969195点)

7:18 方向案内をゴールとみなす (4969837点)

追記 (2019/11/05 01:28)

7:49 焼きなまし法に変更 (4970204点)

感想

おまけ（没アイデア集）

ゴールから1回だけ01BFSの計算をしてよしなにやる

01BFSの計算の途中経過を保存

2点スワップでのロボットの選び方を工夫する

ロボットの順番で良さそうなやつを色々考える

チーム紹介

本番前

本番

反省

さいごに

(1) $a_j \ge 0$

(2) $a_j \lt 0$