競プロ参加記033 AtCoder Beginner Contest 190 (ABC190)

Atcoder

はじめに

AtCoder Beginner Contest 190 – AtCoder

A～Eの5完でした。
Fもコンテスト終了して10分で通せたので、実質6完です。
6完です！！！

A – Very Very Primitive Game

A – Very Very Primitive Game (atcoder.jp)

難しい！
分岐で書けそうですが、考えるのが面倒なのとバグが怖いので愚直にシミュレーションしました。

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

int main(){
    int A,B,C;
    cin>>A>>B>>C;

    while(1){
        if(C==0){
            if(A==0){
                cout<<"Aoki"<<endl;
                return 0;
            }
            A--;
        }
        else{
            if(B==0){
                cout<<"Takahashi"<<endl;
                return 0;
            }
            B--;
        }
        C=1-C;
    }
}

後から考えましたが、Takahashiくんから始まると考えAoki君の飴に補正した後に大小比較すれば良さそうです。

#include<bits/stdc++.h>
//#include<atcoder/all>

using namespace std;
//using namespace atcoder;

int main(){
    int A,B,C;
    cin>>A>>B>>C;

    B-=C;
    if(B!=-1&&A<=B) cout<<"Aoki"<<endl;
    else cout<<"Takahashi"<<endl;
}

C=1のとき、Takahashiくんから考えたいためにAokiくんの飴を1減らしてターンを進めます。

B – Magic 3

B – Magic 3 (atcoder.jp)

書いてる通りの実装をすればOKです。

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

int main(){
    int N,S,D;
    cin>>N>>S>>D;

    bool f=false;

    for(int i=0;i<N;i++){
       int X,Y;
       cin>>X>>Y;
       if(!(S<=X||D>=Y)) f=true;
    }

    if(f) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

C – Bowls and Dishes

C – Bowls and Dishes (atcoder.jp)

Kが小さく、K人の操作が2通りしかありません。
なので2^Kパターンの全操作の組み合わせが試せそうです。
所謂bit全探索というやつをします。

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

int main(){
    int N,M;
    cin>>N>>M;
    int A[M],B[M];
    for(int i=0;i<M;i++){
        cin>>A[i]>>B[i];
    }

    int K;
    cin>>K;
    int C[K],D[K];
    for(int i=0;i<K;i++){
        cin>>C[i]>>D[i];
    }

    int ans=0;
    for(int i=0;i<1<<K;i++){
        int ball[102]={0};
        int ii=i;
        for(int j=0;j<K;j++){
            if(ii%2==0) ball[C[j]]=1;
            else ball[D[j]]=1;
            ii>>=1;
        }
        int c=0;
        for(int j=0;j<M;j++){
            if(ball[A[j]]&&ball[B[j]]) c++;
        }
        ans=max(ans,c);
    }
    cout<<ans<<endl;
}

D – Staircase Sequences

D – Staircase Sequences (atcoder.jp)

難しかったです。
初項a、項数b、等差1の等差数列を考えると、

a+(a+1)+(a+2)+...+(a+b)=N
ab+(1+2+...b)=N

となります。この式をaの式と考えます。(bの方がややこしいので、bを固定して減らしたい)

a=(N-(1+2+...b))/b

aは整数のため、N-(1+2+…b)がbの倍数であればそれに対応する公差数列が存在することになります。

次にaがマイナスの時の答えを考えると、Nは正の整数であるため

a=-3の場合、
-3,-2,-1,0,1,2,3...
→-aまで伸ばさないと、合計が正にならない。
　また、-aまで伸ばすと合計が0になる。

なので、a<0の場合は-a+1から伸ばして答えがあるか？と同値であると言えます。

上記、考えを整理して

  • b=1から開始して、(N-(1+2+…b))/bが整数になれば答えを2増やす (aから伸ばすパターンと、-(a-1)から伸ばすパターン)
  • N-(1+2+…b)が0以下になるなら探索を打ち切る (マイナスのパターンはカウント済みのため)

1+2+…bを累積和で計算すると、N=10^12であっても高速に計算できそうです。

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

int main(){
    long long N;

    cin>>N;
    long long ans=0;
    long long bs=0;
    for(long long b=1;b<1000000000;b++){
        long long n=N-bs;
        if(n<=0) break;
        if(n%b==0) ans++;
        bs+=b;
    }
    cout<<ans*2<<endl;
}

//a+0+a+1+a+2+...a+b
//ab+(0+1+2+...b)=N
//a=(N-bsum)/b

E – Magical Ornament

E – Magical Ornament (atcoder.jp)

魔法石を頂点、隣り合わせにできる組を辺とした時に”K個の頂点を巡る最短経路”を解く問題と言い換えられそうです。
ただ、単純にやると(2^K)*Nの状態数が必要なのでMLEやTLEしてしまいます。

“K個の頂点を巡る最短経路”を知りたいので、K個の頂点以外の頂点は必要ありません。
正確には、K個の頂点間の距離さえ知っていれば、他の頂点は必要ありません。
そのため、

  • K個の頂点間の距離を求める
  • K個の頂点で作ったグラフで、全頂点を巡る最短経路の問題を解く

とすることで解くことができます。

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

int main(){
    int N,M;
    cin>>N>>M;
    vector<int> v[N+1];
    for(int i=0;i<M;i++){
        int A,B;
        cin>>A>>B;
        v[A].push_back(B);
        v[B].push_back(A);
    }

    int K;
    cin>>K;
    int C[K];
    for(int i=0;i<K;i++){
        cin>>C[i];
    }

    if(K==1){
        cout<<"1"<<endl;
        return 0;
    }
    vector<pair<int,int>> v2[K];

    for(int i=0;i<K;i++){
        queue<int> q;
        q.push(C[i]);
        int dis[N+1];
        for(int j=0;j<N+1;j++) dis[j]=-1;
        dis[C[i]]=0;
        while(!q.empty()){
            int n=q.front();
            q.pop();
            for(int j=0;j<v[n].size();j++){
                int t=v[n][j];
                if(dis[t]==-1||dis[t]>dis[n]+1){
                    dis[t]=dis[n]+1;
                    q.push(t);
                }
            }
        }
        for(int j=0;j<K;j++){
            if(i==j) continue;
            //cout<<C[i]<<","<<C[j]<<","<<dis[C[j]]<<endl;
            if(dis[C[j]]==-1){
                cout<<"-1"<<endl;
                return 0;
            }
            v2[i].push_back(make_pair(j,dis[C[j]]));
        }
    }



    int out=INT_MAX;

    for(int s=0;s<K;s++){
        queue<pair<int,int>> q;
        q.push(make_pair(s,1<<s));
        int ans[1<<K][K];
        for(int i=0;i<(1<<K);i++){
            for(int j=0;j<K;j++){
                ans[i][j]=-1;
            }
        }
        ans[1<<s][s]=1;
        while(!q.empty()){
            int n=q.front().first;
            int kk=q.front().second;
            //cout<<n<<","<<kk<<","<<ans[kk][n]<<endl;
            q.pop();
            for(int i=0;i<v2[n].size();i++){
                int t=v2[n][i].first;
                int c=v2[n][i].second;
                int mask=1<<t;
                if((kk&mask)!=0) continue;
                int kk2=kk|mask;
                if(ans[kk2][t]==-1||ans[kk2][t]>ans[kk][n]+c){
                    ans[kk2][t]=ans[kk][n]+c;
                    q.push(make_pair(t,kk2));
                }
            }
        }


        for(int i=0;i<K;i++){
            if(ans[(1<<K)-1][i]<=0) continue;
            //cout<<s<<" "<<ans[(1<<K)-1][i]<<endl;
            out=min(out,ans[(1<<K)-1][i]);
        }
    }

    cout<<out<<endl;

}

この解答、1926msとギリギリでした。
BFSの書き方がまずいっぽく

                if(ans[kk2][t]==-1||ans[kk2][t]>ans[kk][n]+c){ 
                    ans[kk2][t]=ans[kk][n]+c; 
                    q.push(make_pair(t,kk2)); 
                }

この書き方だと、更新の度にqueueに(t,kk2)が大量にpushされ木が大きくなってしまします。

                 if(ans[kk2][t]==-1||ans[kk2][t]>ans[kk][n]+c){
                     if(ans[kk2][t]==-1) q.push(make_pair(t,kk2));
                     ans[kk2][t]=ans[kk][n]+c;
                 }

として、初回更新以外はqueueに入れないようにします。
この改善だけで933msとグッと早くなります。

F – Shift and Inversions

F – Shift and Inversions (atcoder.jp)

転倒数と聞いて、思い浮かぶのはNlogNの解法です。
ただ、この問題はN回転倒数を求めないといけないのでO(N*(NlogN))必要です。

入力例1にあるようにkが1増えると、a0が末端に回ります。
数列Aは0～N-1の並び替えの数列であるため、転倒数は

  • a1～aN-1には、a0より小さい数がa0個ある。
    そのため、転倒数はa0小さくなる。
  • a1～aN-1には、a0より大きい数がN-a0-1個ある
    そのため、転倒数はN-a0-1大きくなる。

そのため、k=0のときの転倒数をNlogNで求め、その後はa0,a1,a2…の値を見ながら転倒数を増減させればOKです。

#include<bits/stdc++.h>
//#include<atcoder/all>

using namespace std;
//using namespace atcoder;

//https://atcoder.jp/contests/chokudai_S001/submissions/19812584
struct BIT {
    BIT(long long n) : s(n + 1), n(n) {}
    long long sum(long long k) {
        long long r = 0;
        for (; k > 0; k -= k & -k) r += s[k];
        return r;
    }
    void add(long long i, long long v) {
        for (long long k = i + 1; k <= n; k += k & -k) s[k] += v;
    }
    vector<long long> s;
    long long n;
};

int main(){
    long long N;
    cin>>N;

    BIT b(N);
    long long A[N];
    for(long long i=0;i<N;i++){
        cin>>A[i];
    }

    long long ans=0;
    for(long long i=0;i<N;i++){
        ans += i-b.sum(A[i]);
        b.add(A[i],1);
    }

    cout<<ans<<endl;

    for(long long i=0;i<N-1;i++){
        long long minus=A[i];
        long long plus=N-1-A[i];
        //cout<<ans<<","<<plus<<","<<minus<<endl;
        ans=ans-minus+plus;
        cout<<ans<<endl;
    }
}

提出 #19812584 – Chokudai SpeedRun 001 (atcoder.jp)

フェニック木はこちらのdef_repinさんの提出コードをお借りしました。

おわりに(雑談)

EZ2ON REBOOT : R on Steam
EZ2ON REBOOT : R – The latest entry in the beloved rhythm-action franchise is now released on Steam! Revisit the huge co...
store.steampowered.com

EZ2ON REBOOT : Rという韓国の音ゲーが2月にSteamでアーリーアクセスとなります。
私がPUSHしているDJMAXと関わりのある作品で、今から楽しみです。

社内コンですが、機械学習のコンペも始まってgoogle colabに負担をかける仕事も始まったので2月は色々やることが増えてきそうです。
暇を見つけてABC埋めも本格的に再開したいですね＞＜

コメント

タイトルとURLをコピーしました