Atcoder Regular Contest_008_D_タコヤキオイシクナール

橙色の問題.箱に入れるという動作がどういうものか解釈してみましょう.

atcoder.jp

問題の説明

箱が $N$ 個存在し,箱それぞれには2つの実数 $(a, b)$ が記載されている. ある実数 $x$ を入力すると $ax+b$ となって出力される.

最初箱に記載されている数字はすべて $(1, 0)$ であり,入力される数字は $1$ である.我々は $x=1$ から $N$ 個の箱を通した後の $x$ の値を求めたい.

M個のクエリが存在し,クエリには $p$ 番目の箱を $(a, b)$ に書き換える指示が出ている.

クエリの指示を1個ずつ行い,それに応じて $N$ 個の箱に $x=1$ を通した後の $x$ の最大値と最小値を求めよ.

制約

$1 \le N \le 10^{12}$
$a, b$ は実数であり, $-1 \le a, b \le 1$
$1 \le M \le 10^{5}$

考えた事

まず,この問題の $N$ に注目したい.これは明らかに大きすぎる.この制約からわかるように $O(N)$ の計算量で問題を扱う事はできない.ここで注目したいのが $(1, 0)$ の存在である.

$x$ を $(1, 0)$ の箱に入力した場合,出力されるのは $1*x+0=x$ である.したがって, $(1, 0)$ の箱は問題の本質にはかかわらず不要である,これをまず除去しよう.こういった不要なものを除去するテクニックとして座標圧縮があげられる.

algo-logic.info

座標圧縮については上のサイトを参照して頂きたい.ざっくりいえばどれくらいの差や,具体的な位置情報を保持せず,大小関係や前後関係だけにして情報量を減らすというものである.今回の問題だと $(1, 0)$ はいらない情報なのでそこを詰める事とする.こうする事で処理しなければならない情報が高々 $M$ 個となり, $M$ の上限が $10^{5}$ である事からも分かるように扱いやすくなる.

座標圧縮のやり方も色々あるが,今回は $p$ を先に読み込んで

 vll pp = p;
    sort(ALL(pp));
    pp.erase(unique(ALL(pp)), pp.end());
    N = pp.size();
    rep(i, M) { p[i] = lower_bound(ALL(pp), p[i]) - pp.begin(); }

といった形で行った. https://qiita.com/ysk24ok/items/30ae72f4f1060b088588:qiita.com を参考にしてもらいたい.要するにsortをかけ,重複要素のポインタをuniqueで発見し,eraseをかけている.

後はlower_boundを行い,何番目に大きいかを受け取る事で大小関係を変えずに座標圧縮を達成してる.難しければsortをかけた後,mapを用いて行ってもよい.

さて,とりあえずこれで箱を高々 $M$ 個とする事ができた.しかし,これだけではこの問題を解く事は出来ない.ひとつのクエリを書き換える度に毎回毎回 $M$ 個の箱を通していては,計算量が $O(M^{2})$ となり間に合わない.¹ どうすればいいだろうか.ここでポイントとなるのは書き換えればならないデータ量の削減である.たとえばデータを1つ1つ線形構造で繋いでいる場合,1つを書き換えてしまうと他のすべてに影響を及ぼすため,すべてやり直さなければならなくなり,計算量が増えてしまう.

直感的な話題になるが,たとえば $A={1, 2, 3, 4, 5, 6, 7, 8}$ とあって,この配列を用いて何か操作を行うとする.² この時に $1$ を $16$ に書き換えた時,前半部分は書き換えが必要だが,後半に関してはあんまり書き換えがいらなく見えるだろう.この直感を活かして計算量を減らしたデータ構造がある.セグメント木だ.

セグメント木とは(完全)二分木であり,区間毎にある演算を行った時にどうなるかの結果を高速に管理するデータ構造である. zenn.dev

セグメント木は親の区間を2分割して子が持つようになっているものである.区間の最小として自分自身のみが含まれているものである事に注目すると,この木の深さは $\log N+1$ であるから,1つのデータが更新された時に書き換える箇所も $\log N+1$ 個となるため,計算量としては $O(\log N)$ で更新を行える点がポイントである.

セグメント木はその性質上,演算に対して単位元が存在するものと,結合律が成り立っている必要がある. このような集合と演算を代数学の用語でモノイドという. たとえば和の演算や積の演算は,それと実数集合上とでモノイドをなす.³ 本題に戻ろう.今回であればどの集合と演算とでモノイドとなるだろうか.集合は簡単であり実数全体である.演算はなんであろうか. ここで箱に入れるという操作に注目したい.これは実数を実数に変換するもので,操作は $x→ax+b$ であった.この操作を $f$ とする.

これに対して函数の合成を演算として $\phi(x)=f_{1}*f_{2}(x)$ とすると二項演算の単位元として $(1, 0)$ を取る事ができ,また合成関数は結合則が成り立つため,実数と演算 $\phi:\mathbb{R}×\mathbb{R}→\mathbb{R}$ からなる集合はモノイドを形成する.

という事で $(\mathbb{R^{2}},*,(1, 0))$ としたモノイドを構築する事に成功した.⁴ 後はこれを実装するだけである.今回はAtcoder Libraryにあるsegtreeを活用した.自前でセグ木を実装する技術も非常に大切であり,これを読んでいる皆様におかれましても是非とも取り組んで頂きたい.

実装する際には演算を行った場合に何が返ってくるかを指定する必要がある.実はこれはそう難しくなく, $f_{1}:x→ax+b$ , $f_{2}:x→cx+d$ となるとした時, $f_{1} * f_{2}(x)= f_{2}(ax+b)=acx+bc+d$ となるから, $(a, b)*(c, d)=(ac, bc+d)$ として返り値を出力すればいい.

単位元はさきほど説明した通り $(1, 0)$ で表現できる.以上をプログラムで表すと以下のようになる.

using P = pair<ld, ld>;
P op(P p, P q) { return {p.first * q.first, p.second * q.first + q.second}; }
P e() { return {1, 0}; }

これでセグメント木の実装は終わった.最後に $M$ 個をセグメント木で処理し,各々最大値と最小値を比較するように組み込めばACが得られる.ここまでお読みいただきありがとうございました.

プログラム

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using ld = long double;
using P = pair<ld, ld>;
using vll = vector<long long>;
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
#define ALL(n) begin(n), end(n)
template <class T>
inline T CHMAX(T& a, const T b) {
    return a = (a < b) ? b : a;
}
template <class T>
inline T CHMIN(T& a, const T b) {
    return a = (a > b) ? b : a;
}
P op(P p, P q) { return {p.first * q.first, p.second * q.first + q.second}; }
P e() { return {1, 0}; }
ll target;
bool f(ll v) { return target <= v; }
int main() {
    ll N, M;
    cin >> N >> M;
    vll p(M);
    vector<ld> a(M);
    vector<ld> b(M);
    rep(i, M) { cin >> p[i] >> a[i] >> b[i]; }
    vll pp = p;
    sort(ALL(pp));
    pp.erase(unique(ALL(pp)), pp.end());
    N = pp.size();
    rep(i, M) { p[i] = lower_bound(ALL(pp), p[i]) - pp.begin(); }
    segtree<P, op, e> seg(N);
    ld maxtako = 1.0;
    ld mintako = 1.0;
    rep(i, M) {
        seg.set(p[i], {a[i], b[i]});
        P takoyaki = seg.all_prod();
        ld tako = takoyaki.first + takoyaki.second;
        CHMAX(maxtako, tako);
        CHMIN(mintako, tako);
    }
    cout << setprecision(18) << mintako << endl;
    cout << setprecision(18) << maxtako << endl;
}

smallの想定解はこれでも間に合うため座標圧縮もかけず,純粋にクエリ毎に $(a, b)$ を書き換えて通すものである.↩
和をとるとか.↩
逆元の存在が保証されている場合,群をなす.↩
今回は函数を2次元の実数で表現できているが,本来ならばここは函数全体の集合を $\mathbb{F}$ とした方が正確かもしれない.↩

garakutagoya

興味、関心のあったこと、そして私の気持ちなどを残していきたい

Atcoder Regular Contest_008_D_タコヤキオイシクナール

問題の説明

制約

考えた事

プログラム