Help us understand the problem. What is going on with this article?

ACL Contest 1 復習

今回の成績

スクリーンショット 2020-09-21 13.50.13.png

今回の感想

A問題が解けなくて焦ってしまいましたが、最近よく見る形の問題なので素早く通せるようになりたいです。

B問題は自分は知らないタイプの問題でした。考察はできていたにもかかわらず、自信が持てないのと実装を面倒と感じてしまい、コンテスト中に通せませんでした。非常にもったいないので、自信を持てるように考察力をあげるのと、正当性があるなら自分の方針を押し通す力をつけたいです。

A問題

(以下では、計算量がわかりやすいようにUnionFindの連結を定数時間すnるものとしています。)

移動できる街同士をつないで素集合系を求め、それぞれの街の含まれる集合のサイズを求めることを考えます。また、この条件としては$x$座標と$y$座標が共に小さいか共に大きいかのいずれかを考えますが、共に小さい方のみを考えれば良いです($\because$逆の関係なので)。また、$x$座標と$y$座標を同時に考えるのは難しいので、$y$座標の降順に処理して残りの$x$座標の大小を考えます。(✳︎1)

ここで、$y$座標の大きい点から見ていく際に、残りの点の$x$座標を昇順で保持するset構造$set$_$checky$を持っておきます。これにより、$i$番目の点$(x_i,y_i)$を見た時は$set$_$checky$に含まれる中で$x_i$未満であるものを$lower$_$bound$により探してお互いをつなげれば良いです。しかし、これを任意の街に対して行うと全体の計算量が$O(N^2)$なので間に合いません。

したがって、ここではつなげる点を省略することを考えます。つまり、$x_i$未満の街で$i$番目の街とすでに連結している街がある場合、$i$番目より前の街がその街と連結していることを示し、この時それよりも$x$座標の小さい点はすでに連結していることがわかります。よって、同じ集合に含まれている場合は$x$座標がそれ未満の街をチェックせずにbreakすればよく、sameの判定が高々$n$回でuniteも高々$n-1$回なので、全体の計算量は$O(n \log{n})$で十分高速に計算することができます。

また、$set$_$checky$からの削除を行うために$y$座標に対応する$x$座標を保存する配列checkx、つなげる際に入力のインデックスに合わせてつなぎたいので、$x$座標に対応するインデックスを保存する配列indを用意して実装しなければなりません。

(✳︎1)…このように二次元座標などの二変数の場合に片方は順番に考えて片方はデータ構造で処理するのは頻出パターンです。また、データ構造としては最大最小や大小比較の時にはsetまたはmultisetを使うことが多いです。

A.cc
//デバッグ用オプション:-fsanitize=undefined,address

//コンパイラ最適化
#pragma GCC optimize("Ofast")

//インクルードなど
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//マクロ
//forループ
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
//FORAは範囲for文(使いにくかったら消す)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

//以下、素集合と木は同じものを表す
class UnionFind {
public:
    vector<ll> parent; //parent[i]はiの親
    vector<ll> siz; //素集合のサイズを表す配列(1で初期化)
    map<ll,vector<ll>> group;//素集合ごとに管理する連想配列(keyはそれぞれの素集合の親、valueはその素集合の要素の配列)

    //コンストラクタ
    UnionFind(ll n):parent(n),siz(n,1){ 
        //全ての要素の根が自身であるとして初期化
        for(ll i=0;i<n;i++){parent[i]=i;}
    }

    //データxの属する木の根を取得(経路圧縮も行う)
    ll root(ll x){
        if(parent[x]==x) return x;
        return parent[x]=root(parent[x]);//代入式の値は代入した変数の値なので、経路圧縮できる
    }

    //xとyの木を併合
    void unite(ll x,ll y){
        ll rx=root(x);//xの根
        ll ry=root(y);//yの根
        if(rx==ry) return;//同じ木にある時
        //小さい集合を大きい集合へと併合(ry→rxへ併合)
        if(siz[rx]<siz[ry]) swap(rx,ry);
        siz[rx]+=siz[ry];
        parent[ry]=rx;//xとyが同じ木にない時はyの根ryをxの根rxにつける
    }

    //xとyが属する木が同じかを判定
    bool same(ll x,ll y){
        ll rx=root(x);
        ll ry=root(y);
        return rx==ry;
    }

    //xの素集合のサイズを取得
    ll size(ll x){
        return siz[root(x)];
    }

    //素集合をそれぞれグループ化
    void grouping(ll n){
        //経路圧縮を先に行う
        REP(i,n)root(i);
        //mapで管理する(デフォルト構築を利用)
        REP(i,n)group[parent[i]].PB(i);
    }
};

signed main(){
    //入力の高速化用のコード
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;cin>>n;
    vector<ll> ind(n,0);
    vector<ll> checky(n,0);
    vector<ll> checkx(n,0);
    UnionFind uf(n);
    REP(i,n){
        ll x,y;cin>>x>>y;
        checky[x-1]=y-1;
        checkx[y-1]=x-1;
        ind[x-1]=i;
    }
    //checkyの中からそれより小さいものを探す(探す順番は値の順番)
    //checkyの値でsetを作っておいてその中で探す(終わったら削除)
    //値の順番なので、それ以降の省略ができる
    set<ll> set_checky;
    REP(i,n)set_checky.insert(i);
    REPD(i,n){
        //yの大きいところから探す(見つかったらbreak)
        //setないはxの順番
        auto j=set_checky.lower_bound(checkx[i]);
        if(j==set_checky.begin()){
            set_checky.erase(checkx[i]);
            continue;
        }
        //cout<<2<<endl;
        j--;
        while(true){
            //cout<<4<<endl;
            if(uf.same(ind[checkx[i]],ind[*j])){
                //cout<<4<<endl;
                if(ind[checkx[i]]!=ind[*j])break;
            }else{
                uf.unite(ind[checkx[i]],ind[*j]);
            }
            if(j==set_checky.begin())break;
            j--;
            //cout<<1<<endl;
        }
        set_checky.erase(checkx[i]);
    }
    uf.grouping(n);
    REP(i,n){
        cout<<uf.size(i)<<endl;
    }
}

B問題

見かけや焦りや未知のアルゴリズムへの恐さなどに押しつぶされましたが、そこまで難しくはないと思います。コンテスト中に解いてこの言葉を吐きたかったです。

まず、$1+2+…+k=\frac{k(k+1)}{2}$が$n$の倍数であり、分数が扱いにくいので$(k+1)k$が$2n$の倍数です。この時、$k+1$と$k$の掛け算が$2n$の倍数なので、それぞれは$2n$の約数の倍数になります。また、ここで制約より$2n$は高々$2 \times 10^{15}$なので約数の全列挙が可能です。従って、$a \times b =2n$として、$k+1$を$a$の倍数,$k$を$b$の倍数とします。この時、$x,y$を正の整数とすれば$k+1=ax,k=by,ax-by=1$が成り立ちます。よって、一次不定方程式さえ解ければ約数$a,b$において最小となる$k$を求められます

ここで、一次不定方程式は拡張ユークリッドの互除法で特殊解を求めた後に一般解を求めることで解くことができます(✳︎1)。また、特殊解は$O(\log{min(a,b)})$で求められますが、約数を列挙しても計算回数の$\sqrt{2n}$よりもずっと少ないことは明らかなので、それぞれの約数に対して一次不定方程式を解いても十分に間に合います(✳︎1)。また、ユークリッドの互除法により求めた特殊解を$x_0,y_0$とすると$a \times x_0 -b \times y_0=1$となるので、$m$を整数として一般解は$x=x_0+b \times m,y=y_0+a \times m$となります(✳︎1)。よって、$m$を大きくした時に$x,y$はいずれも大きくなります。ここで、$x,y$は正かつ最小のものを求めたいので、特殊解が負である場合や正で大きい場合はうまく調節する必要があります。この調節は$m$を何回足すかを考えればよく、ceil関数やfloor関数を駆使して考えることで簡単に求めることができます。また、ここでの計算の計算量は$O(1)$です。

以上より、二つの約数が得られたときの最小の$k$を求めることができ、任意の約数について行った中で最小の$k$を求めれば良いです。また、$n=1$のときはバグらせやすい(自分も一回WAを出した)ので、注意が必要です。

(✳︎1)…ここまでの議論はできていたのですが、計算量解析の雑さや数学から離れていたことによる感覚の鈍さで諦めてしまいました。

(✳︎2)…特殊解の求め方についてはこの記事を参考にしてください。

(✳︎3)…一般解の導出などについてはこの記事を参考にしてください。

B.cc
//デバッグ用オプション:-fsanitize=undefined,address

//コンパイラ最適化
#pragma GCC optimize("Ofast")

//インクルードなど
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//マクロ
//forループ
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
//FORAは範囲for文(使いにくかったら消す)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
ll extGCD(ll a, ll b, ll &x, ll &y) {
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll d=extGCD(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

ll myceil(ll a,ll b){
    return (a+(b-1))/b;
}

ll make_divisors(ll n){
    vector<ll> divisors;//約数を格納する配列
    ll ret=max(n/2-1,1LL);
    FOR(i,1,sqrt(n)){
        if(n%i==0){
            divisors.PB(i);
            if(i!=n/i){
                divisors.PB(n/i);
            }
        }
    }
    FORA(i,divisors){
        ll x0,y0,a,b;a=i;b=n/i;
        if(extGCD(a,-b,x0,y0)!=1)continue;
        if(x0>=0 and y0>=0){
            ll m=min(ll(x0/b),ll(y0/a));
            if(x0-b*m==0 or y0-a*m==0)m--;
            ll x,y;x=a*(x0-b*m);y=b*(y0-a*m);
            ret=min(ret,y);
        }else if(x0<0 and y0<0){
            ll m=max(myceil(-x0,b),myceil(-y0,a));
            if(x0+b*m==0 or y0+a*m==0)m++;
            ll x,y;x=a*(x0+b*m);y=b*(y0+a*m);
            ret=min(ret,y);
        }else if(x0<0){
            ll m=myceil(-x0,b);
            if(x0+b*m==0)m++;
            ll x,y;x=a*(x0+b*m);y=b*(y0+a*m);
            ret=min(ret,y);
        }else{
            ll m=myceil(-y0,a);
            if(y0+a*m==0)m++;
            ll x,y;x=a*(x0+b*m);y=b*(y0+a*m);
            ret=min(ret,y);
        }
    }
    return ret;
}
signed main(){
    ll n;cin>>n;
    cout<<make_divisors(2*n)<<endl;
}

拡張ユークリッドの互除法のライブラリ

けんちょんさんのコードを写しただけです。より良いものがあったら教えてください。

eea.cc
//aとbの最大公約数を返す(a,bが負の場合は絶対値をとる)
//ax+by=gcd(a, b)を満たす特殊解x0,y0を格納する
ll extGCD(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll d=extGCD(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

C問題以降

今回は解きません。

DaikiSuyama
PythonとC++で競技プログラミングをしています(highest:AtCoder:1413,Codeforces:1672)。 機械学習も少し勉強しています。 FXや株の自動売買、音楽の自動生成に興味があります。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away