はむへい’s diary

ねむいです。

CODE THANKS FESTIVAL 2017(Parallel) H - Union Sets 並行二分探索での解法

はじめに

この記事は東京高専プロコンゼミ① Advent Calendar 2019の6日目の記事です。
ちょっと前から、精進で問題を解いたら記事にするというのをしていて、そのままアドベントカレンダーの記事も兼ねてしまおうみたいな魂胆です。
うちの部には非競プロerもいるので、いつもより丁寧に書きたいですが、あまり厳密な理解をしていなかったり、厳密な文章を書くのになれていなかったりで、おきもちを説明する感じになってしまいました。

問題URL

H - Union Sets

解法

並行二分探索をします。

並行二分探索は、二分探索する区間が同じなクエリ達の判定をまとめられるとき、それをまとめてしまうテク(?)のことをいうっぽいです。

問題の解き方を見るのが早い気がするので、解いてみます。

まず、クエリごとに問題を解いてみることを考えます。二分探索をすることを考えると 、

「k番目までの操作を行ったときにx, yが同じ集合かどうか？」というようなことを考えて、kについて二分探索を行えば良いです。

判定にはk番目までの操作をUnionFindで再現すると、O(N log N) で行うことができます。

なので、1つのクエリについてO(N log N log M)で問題が解けます。(UnionFindで前からやるだけで二分探索がいらなくなりますが、ここでは考えないことにします)
この二分探索をQ個のクエリにそれぞれ行ってしまうと、もちろん間に合いません。

ここで、二分探索の判定部分に着目します。k番目までの操作をUnionFindで再現した場合、「x, yが同じ集合に属するか？ 」という質問以外にも、任意の要素のペアについて同じ集合に属するか判定することができます。

この判定はまとめられそうです。

Q個のクエリをまとめてみます。以下のようにします。

  1. はじめに、すべてのクエリは1つの集合で、その集合には探索する区間[0, M)が紐付いているとします。
  2. UnionFindを用いて操作を前からシュミレートします。その途中で、条件を満たすようなクエリの集合について適宜以下のような操作を行います。
  3. 2でk番目までの操作が終わったとき、そのkが区間の中央になるような集合について考えます。その集合の要素であるクエリそれぞれについて判定をして、その結果で集合を2つに分割します。分割後のクエリの集合には判定の結果ごとに、二分探索と同じように新しい探索区間が紐付けられます。(片方は[r, k)、もう片方は[k, l)みたいな具合に)
  4. クエリ達の持つ探索区間が十分に小さくなるまでクエリの集合たちに対して2~3の分割を繰り返します。

セグメント木の図みたいなものを思い浮かべてみるとクエリ分割のおきもちはわかりやすいです。

このようにすると、クエリを分割するために行うシュミレートの回数はlog M回程度です。クエリを分割するシュミレートの計算量は、O(N log N + Q)になります。
なので、全体の計算量はO((N log N + Q)log M)になり、解けました。

Q個のクエリをまとめる部分が、並行二分探索と呼ばれているものみたいです。

参考にしたもの

https://youtu.be/NQhd1Ifkxtk これのD問題の解説がとてもわかりやすいです

ACしたコード

最後まで併合されないようなクエリについては二分探索の前に弾いています。

atcoder.jp

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

using ll = long long;

class UnionFind {
public:
    vector<int> data;
    UnionFind(int size) : data(size, -1) { }
    bool connect(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
        data[x] += data[y]; data[y] = x;
        }
        return x != y;
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};

void solve(long long N, long long M, std::vector<long long> a, std::vector<long long> b, long long Q, std::vector<long long> x, std::vector<long long> y){
    vector<pair<pair<ll, ll>, int>> Querys;
    for(int i = 0;i < Q;i++){
        Querys.push_back(make_pair(make_pair(x[i], y[i]), i));
    }
    vector<int> ans(Q);
    UnionFind check(N + 1);
    for(int i = 0;i < M;i++)check.connect(a[i], b[i]);
    queue<pair<pair<int, int>, vector<pair<pair<ll, ll>, int>>>> range;
    range.push(make_pair(make_pair(0, M), vector<pair<pair<ll, ll>, int>>()));
    for(int i = 0;i < Q;i++){ //併合されないクエリは弾いておく
        auto p = Querys[i];
        if(check.same(p.first.first, p.first.second))range.front().second.push_back(p);
        else ans[i] = -1; 
    }
    while (!range.empty())
    {
        if(range.front().second.size() == 0){ //全部のクエリが併合されないようなケース  
            range.pop();
            break;
        }
        UnionFind Uni(N + 1);
        queue<pair<pair<int, int>, vector<pair<pair<ll, ll>, int>>>> next_range;
        for(int k = 0;k < M;k++){
            while(!range.empty()){
                if(k == (range.front().first.first + range.front().first.second) / 2){
                    pair<pair<int, int>, vector<pair<pair<ll, ll>, int>>> range_front = range.front();
                    range.pop();
                    vector<pair<pair<ll, ll>, int>> ok;
                    vector<pair<pair<ll, ll>, int>> ng;
                    for(auto q : range_front.second){
                        if(Uni.same(q.first.first, q.first.second)){
                            ok.push_back(q);
                        }else{
                            ng.push_back(q);
                        }
                    }
                    
                    //クエリの分割
                    if(ok.size() != 0)next_range.push(make_pair(make_pair(range_front.first.first, (range_front.first.first + range_front.first.second)/2), ok));
                    if(ng.size() != 0)next_range.push(make_pair(make_pair((range_front.first.first + range_front.first.second)/2, range_front.first.second), ng));
                }else{
                    break;
                }
            }
            Uni.connect(a[k], b[k]);
        }
        while(!next_range.empty()){
            auto q = next_range.front();
            next_range.pop();
            if(q.first.second - q.first.first <= 1){
                for(auto qq : q.second){
                    ans[qq.second] = q.first.second;
                }
            }else{
                range.push(q);
            }
        }
    }
    for(int i = 0;i < ans.size();i++){
        cout<<ans[i]<<endl;
    }
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    std::vector<long long> a(M);
    std::vector<long long> b(M);
    for(int i = 0 ; i < M ; i++){
        scanf("%lld",&a[i]);
        scanf("%lld",&b[i]);
    }
    long long Q;
    scanf("%lld",&Q);
    std::vector<long long> x(Q);
    std::vector<long long> y(Q);
    for(int i = 0 ; i < Q ; i++){
        scanf("%lld",&x[i]);
        scanf("%lld",&y[i]);
    }
    solve(N, M, std::move(a), std::move(b), Q, std::move(x), std::move(y));
    return 0;
}

AtCoder Grand Contest 003 C - BBuBBBlesort!

問題URL

C - BBuBBBlesort!

解法

まず、数列の要素は互いに相異なるので、要素を小さい順から1 \sim Nと置き換えても問題ありません。
そうすると、この問題は、与えられた操作を行って、左から1 \sim Nと並び替える問題と考えることができます。

操作2が何を行っているかを考えてみます。
「数列の連続する 3つの要素を選び、その3つの順番を反転する。」
とありますが、3つのうち、2つめの要素(つまり真ん中の要素)は、順番を反転させても変わらないので、1つ目と3つ目の要素の反転を行っていると見ることができます。
そして、操作2は何度行っても全体のスコアに影響を及ぼさないことから、数列のうち偶数(奇数)番目の要素同士は互いを好きに並び替えてよいことがわかります。

操作1が何を行っているかを考えてみます。
「数列の連続する2つの要素を選び、その2つの順番を反転する。」
とあります、これはつまり、数列の要素の中で隣あう偶数番目と奇数番目の要素のスワップが行えることを示しています。

つまり、並び替える前の数列の要素の偶奇がその要素を左からのインデックス(1 \sim N)の偶奇と等しくないときにのみ操作1を行えばよいです、そのような要素の数をcntとしておきます。
並び替える前の要素が偶数で、その要素を左からのインデックス(1\sim N)が奇数というような要素がある場合、必ず同じ数だけ、並び替える前の要素が奇数で、その要素を左からのインデックスの(1~N)が偶数というような要素が存在します。操作1を1回行うと、それぞれ一つづつ偶奇を反転させることができるので、cntを2で割ったものが答えです。

ACしたコード

atcoder.jp

#include <bits/stdc++.h>

using namespace std;
using ll = long long;


int main()
{
    int N;cin >> N;
    vector<int> v;
    map<int, int> mp;
    for(int i = 0;i < N;i++){
        int b;cin >> b;
        v.push_back(b);
        mp[b] = i;
    }
    int cnt = 0;
    for(auto a : mp){
        v[a.second] = cnt;
        cnt++;
    }
    int ans = 0;
    //for(int i = 0;i < v.size();i++)cout<<v[i]<<endl;
    for(int i = 0;i < N;i++){
        if((v.at(i) % 2) != (i % 2))ans++;
     }
    cout<<ans/2<<endl;
}

AtCoder Regular Contest 054 B - ムーアの法則

問題URL

B - ムーアの法則

解説

まず、計算を終了するまでにかかる時間を、計算を開始するまで待つに時間xの関数f(x)として定義することを考えてみます。
計算を終了するまでにかかる時間は、計算を開始するまでに待つ時間 + タカハシマン関数を計算するのにかかる時間
と2つの時間の和で表せます。
xと問題文中に登場するPを用いて、この時間を表してみます。
まず、左側の項の「計算を開始するまでに待つ時間」は先程の定義よりxです。
次に、「タカハシマン関数を計算するのにかかる時間」ですが、少しも待たないときの「タカハシマン関数を計算するのにかかる時間」がPで、そこから計算する速さが2^{x / 1.5}倍になっていきます。
つまり、x年後の「タカハシマン関数を計算するのにかかる時間」はP / (2^{x / 1.5})と表すことができます。
よって、f(x)は、f(x) = x + P / (2^{x / 1.5})のように定義できます。
この関数は下に凸なので、一番小さな値を三分探索することにより、答えを得ることが出来ます。

ACしたコード

atcoder.jp

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main(){
    long double P;cin >> P;
    long double x = 0;
    long double y = 1e18;
    auto calc = [&](long double i){
        return i + P / pow(2, i / 1.5);
    };
    while(y - x > 1e-6){
        long double x_ = x + (y - x)/3;
        long double y_ = x + (y - x)/3*2;
        //cout<<x_ <<" "<<y_<<" "<<calc(x_)<<" "<<calc(y_)<<endl;
        if(calc(x_) > calc(y_)){
            x = x_;
        }else{
            y = y_;
        }
    }
    cout<<setprecision(20)<<calc(x)<<endl;
}

AtCoder Regular Contest 052 B - 円錐

問題URL

B - 円錐

解法

Q個のクエリについて、すべての円錐がどの程度区間に入っているか調べることができます。
ある円錐がある区間にどの程度入っているか求める方法を考えてみます。
区間の左端をA、右端をBとします。
また、円錐の底面のx座標をx、高さをh、底面の半径をrとします。 また、円錐の体積をSとします。
まずはじめに、B \leqq x または x + h \leqq Aであるようなものは、区間の中に円錐が入っていないので、区間と円錐が共有する体積は0です。 また、A \leqq x, x+h \leqq Bのように円錐を丸々覆ってしまうような区間の場合は区間と円錐が共有する体積はSです。

次に、 x \lt A, A \lt x + h \leqq Bのように、円錐の先の方だけ区間に含まれる場合について注目します。この場合、区間に含まれる図形は、元の円錐と相似であり、その相似比は 、 元の円錐 : 区間に含まれる円錐 = h : x + h - Aです。体積比は相似比の3乗の比なので、先の方だけ含まれる円錐については、その体積は、 S * (x + h - A)^{3} / h^{3}になります。

次に、[tex;A \leqq x \lt B, B \lt x + h]のように、円錐の先の方だけ区間に含まれない場合について注目します。この場合、区間からはみ出る図形は、元の円錐と相似であり、その相似比は、 元の円錐 : 区間からはみ出る円錐 = h : x + h - Bです。体積比は相似比の3乗の比になるので、はみ出た部分の体積はS * (x + h - B)^{3} / h^{3} です。
元の円錐からはみ出た区間を引けばよいので、区間と共有する体積は S - S * (x + h - B)^{3} / h^{3} です。

最後に、x \lt A,B \lt x + h のように、区間を覆うような円錐の場合を考えます。
これは、円錐の中でAより体積を求め、そこからBより大きいはみ出た部分を引くことで得られます。
今まで求めてきた場合分けと同じように求めると、共有する体積は S * (x + h - A)^{3} / h^{3} - S * (x + h - B)^{3} / h^{3}となります。

以上をで全てのケースを列挙できているので、それぞれ計算して総和を出せば解けます。計算量はO(NQ)です。

ACしたコード

atcoder.jp

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

long double pi = 3.14159265359;

int main()
{
    int N,Q;cin >> N >> Q;
    vector<pair<pair<int, int>, pair<int, double>>> v;
    for(int i = 0;i < N;i++){
        int x,r,h;cin >> x >> r >> h;
        v.push_back(make_pair(make_pair(x, r), make_pair(h, pi * r * r * h * 1 / 3)));
    }
    for(int q = 0;q < Q;q++){
        long double ans = 0;
        int A,B;cin >> A >> B;
        for(int i = 0;i < N;i++){
            int x = v.at(i).first.first;
            int r = v.at(i).first.second;
            int h = v.at(i).second.first;
            double vo = v.at(i).second.second;
            if(A <= x && x + h <= B){
                ans += vo;
            }else
            if(x < A && A <= x + h && x + h <= B){
                ans += vo * pow(1.0*(x + h - A) / h, 3);
            }else
            if(A <= x && x < B && B < x + h){
                ans += vo - vo * pow(1.0*(x + h - B)/ h, 3);
            }else
            if(x <= A && B <= x + h){
                ans += vo * pow(1.0*(x + h - A) / h, 3) - vo * pow(1.0*(x + h - B) / h, 3);
            }
        }
        cout<<setprecision(20)<<ans<<endl;
    }
}

AtCoder Beginner Contest 067 D - Fennec VS. Snuke

問題URL

D - Fennec VS. Snuke

解法

与えられるグラフは木なので、頂点1から頂点Nまでの経路は一通りです。
お互いにその経路上に自分の陣地を伸ばしていき、その後互いが塗ることのできる頂点に色を塗っていくことが互いにとって最適な戦略です。
まだその経路上の頂点が全て塗られてないうちに経路上の頂点以外を塗ってしまうと、相手が到達できる範囲を広げてしまうことになるからです。
これを幅優先探索を用いてシュミレーションすれば、答えを得ることができます。 計算量はO(N)です。

ACしたコード

atcoder.jp

#include <bits/stdc++.h>

using namespace std;

int main(){
    int N;cin >> N;
    vector<vector<int>> E(N);
    for(int i = 0;i < N - 1;i++){
        int a,b;cin >> a>> b;
        a--,b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }
    vector<int> flag(N, -1);
    flag.front() = 0;
    flag.back() = 1;
    queue<int> que;
    que.push(0);
    que.push(N-1);
    while(!que.empty()){
        int q = que.front();
        que.pop();
        for(auto a : E[q]){
            if(flag[a] == -1){
                flag[a] = flag[q];
                que.push(a);
            }
        }
    }
    int F = 0,S = 0;
    for(auto a : flag){
        if(a == 0)F++;
        else S++;
        //cout<<a<<endl;
    }

    if(S < F){
        cout<<"Fennec"<<endl;
    }else{
        cout<<"Snuke"<<endl;
    }
}

AtCoder Beginner Contest 006 C - スフィンクスのなぞなぞ

問題URL

C - スフィンクスのなぞなぞ

解法

大人か老人か赤ちゃんのうちの一つを固定してしまえば、普通の鶴亀算になります。 N \leqq 10^{5}であるので、10^{5}回程度の計算で答えを得ることができます。

ACしたコード

atcoder.jp

#include <bits/stdc++.h>

using namespace std;

int main(){
    int N,M;cin >> N >> M;
    for(int i = 0;i <= N;i++){
        if(i * 2 > M){
            break;
        }
        int remainAsi = M - 2 * i;
        int remainHito = N - i;
        if(remainAsi >= remainHito * 3 && remainHito - (remainAsi - remainHito * 3) >= 0){
            cout<<i<<" "<<remainHito - (remainAsi - remainHito * 3)<<" "<<(remainAsi - remainHito * 3)<<endl;;
            return 0;
        }
    }
    cout<<-1<<" "<<-1<<" "<<-1<<endl;
}

AtCoder Beginner Contest 080 D - Recording

問題URL

D - Recording

解法

1 \leqq C \leqq 30とCの種類がとても少ないので、これを利用することにします。
ある時間のテレビの利用状況は、32bit整数を一つ用いて、i番目のbitが立っていたらチェンネルiを録画するというように表現できます。
ここで、ある時間に、録画したいチャンネルを新たに加えることを考えます。
それは、ある時間の既に録画予定のチャンネルを表す整数をX、新たに録画したいチャンネルをiとして、bit演算を用いて、
X \mid (1 << i) と表せます。
これは、ある時間のあるチャンネルを録画するクエリが複数来ることがないので、 X + (1 << i)と加算の形で表してしまって問題ないです。
この操作を区間(s_i , t_i)について行います。
この操作は加算の形で表せるので、予め 0 で初期化した長さ10^{5}の数列に対し、クエリごとに区間(s_i, t_i)に1 << c_iを加算します。
すべてのクエリを処理したあとに、数列の各要素について、立っているbitの数の中で最も多いものがこの問題の答えです。
区間加算にimos法を用いることによって、10^{5}回程度の計算で答えを得ることができます。

ACしたコード

区間加算に遅延評価セグメントツリーを用いています。

atcoder.jp

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

class SegmentTreeRSQ {
private:
    int n;
    vector<LL> node, lazy;

public:
    void init(vector<LL> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.resize(2*n-1, 0);

        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];
    }

    void eval(int k, int l, int r) {
        if(lazy[k] != 0) {
            node[k] += lazy[k];
            if(r - l > 1) {
                lazy[2*k+1] += lazy[k] / 2;
                lazy[2*k+2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
    }

    void add(int a, int b, LL x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }
        else {
            add(a, b, x, 2*k+1, l, (l+r)/2);
            add(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = node[2*k+1] + node[2*k+2];
        }
    }

   LL getsum(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
        LL vl = getsum(a, b, 2*k+1, l, (l+r)/2);
        LL vr = getsum(a, b, 2*k+2, (l+r)/2, r);
        return vl + vr;
    }
};

int main(){
    int N,C;cin >> N >> C;
    SegmentTreeRSQ Seg;
    Seg.init(vector<LL>(1e5+1));
    for(int i = 0;i < N;i++){
        int s,t;cin >>s >> t;
        s--,t--;
        int c;cin >> c;
        Seg.add(s, t+1, (1 << c));
    }
    int ans = 0;
    for(int i = 0;i < 1e5+10;i++){
        ans = max((int)bitset<60>(Seg.getsum(i, i+1)).count(), ans);
    }
    cout<<ans<<endl;
}