競プロ参加記020 AtCoder Regular Contest 107(ARC107)

Atcoder

※今までnoteでメモしていた参加記を個人ブログで書くことにしました。(ブログネタがないため)
 001~019はnoteに書いていますので、そちらも是非見てください。
 ↓019のnote記事

競プロ参加日記019 AtCoder Beginner Contest 180|ぬるから|note
AtCoder Beginner Contest 180 - AtCoder AtCoder is a programming contest site for anyone from beginne atcoder.jp LPIC受けてたり、Kaggleでボコボコになってたり、...

2020/11/01 1:39 D問題を解説ACしたため追記しました。
2020/11/01 2:35 E問題を解説ACしたため追記しました。


はじめに

AtCoder Regular Contest 107 - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

このブログを触っていたり、JavaScriptで遊んでいたりして参加がなかなかできていませんでしたが、久々に参加しました。
A,B,Cの3完でした。500点問題解けたので及第点といった感じです。

A – Simple Math

A - Simple Math
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

3つのシグマからなるabcを求める問題。
単純にやればO(N^3)なのでしんどいです。

2つのシグマで考える

問題を簡略化して2つのシグマで考えます。

#include<bits/stdc++.h>

using namespace std;

long long mod=998244353;

int main(){
    long long a,b;
    cin>>a>>b;
    long long ans=0;
    for(int i=1;i<=a;i++){
        for(int j=1;j<=b;j++){
            cout<<i<<"*"<<j<<"="<<i*j<<endl;
            ans+=i*j;
        }
    }
    cout<<ans<<endl;
}

O(N^2)のコードですが、これにa=2,b=3を入れて出力を観察します。

2 3
1*1=1 
1*2=2
1*3=3
2*1=2
2*2=4 
2*3=6
18

1+2+3+2+4+6=18ですが、これを1~b(今回の入力の場合1,2,3)の和でくくると、
(1+2+3)(1)+(1+2+3)(2)=18となります。
ここから、2つのシグマの場合は、1~bの和と1~aの和を掛け合わせたものが答えになりそうだなと予想できます。

3つのシグマに拡張

2つのシグマの答えをabとした場合、問題文の式は
ab*c1+ab*c2+ab*c3+…ab*cmax
となります。なので、3つのシグマには先ほどの2つのシグマの答えに1~cの和を掛け合わせれば良さそうです。

最終的な解法

上記の考えを纏めると、
1~aの和*1~bの和*1~cの和
をすれば求まりそうです。
和の計算には除算が入るためmodがややこしそうですが、除算前でオーバーフローはしない制約になっているため、modの場所にさえ気をつければ問題ありません。

#include<bits/stdc++.h>

using namespace std;

long long mod=998244353;

int main(){

    long long a,b,c;
    cin>>a>>b>>c;

    long long bb=b*(b+1)/2%mod;
    long long aa=a*(a+1)/2%mod;
    long long cc=c*(c+1)/2%mod;

    cout<<(aa*bb)%mod*cc%mod<<endl;
}

B – Quadruple 

B - Quadruple
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

条件を満たす、a,b,c,dの組み合わせを考える問題。
a+b-c-d=Kを式変形し、
a+b-(c+d)=Kと考えた場合、2値の和-2値の和=Kと考えられます。

2値の和-2値の和=Kを考える

a+b=ab
c+d=cd
とすると、条件の式は
ab-cd=K
となります。これを満たす、ab,cdの組み合わせを考えます。
2<=ab,cd<=2*Nであるため、単純な全探索はO(N^2)です。
ただ、ab=K-cdと考えた場合、abが決まればcdは一意に決まることが分かります。
そのため、ab,cdの組み合わせはabを2~2*Nの間で回して、K-cdが範囲内である場合を考えればいいことが分かります。

ab,cdの組み合わせを考える

ab=pとなるような、a+bの組み合わせの個数を考えていきます。
単純にa+bの全パターンを列挙しようとすると、O(N^2)かかります。
あるaに対してb=1~Nの全パターンを考えた場合、a+1~a+Nの範囲のパターンが1個ずつ増えるはずです。
そのため、範囲に対するアルゴリズムを何か適用して高速に計算することができます。
今回、私はimos法を使って求めました。

最終的な解法

ab,cd=p(2<=p<=2*N)となるようなab,cdの組み合わせの個数を事前計算し、それを使ってab-cd=Kの組み合わせ数を求めました。

#include<bits/stdc++.h>

using namespace std;

long long mod=998244353;

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

    long long cnt[200010]={0};

    for(int i=1;i<=N;i++){
        cnt[i+1]++;
        cnt[i+N+1]--;
    }

    for(int i=2;i<=2*N;i++){
        cnt[i]+=cnt[i-1];
    }
    long long ans=0;
    for(long long i=2*N;i>=2;i--){
        long long ab=i;
        long long cd=ab-K;
        if(ab<0||ab>2*N||cd<0||cd>2*N) continue;
        ans+=cnt[ab]*cnt[cd];
    }

    cout<<ans<<endl;
}

C – Shuffle Permutation

C - Shuffle Permutation
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

この手の問題の行列の性質として、

  • 操作の順番は関係ない
    (1,3)列の交換→(1,3)行の交換 = (1,3)行の交換→(1,3)列の交換
  • 2回操作すればなかったことになる
    (1,3)列の交換→(1,3)行の交換→(1,3)列の交換 = (1,3)列の交換

みたいな事があります。
また、
(1,3)行が交換できる、(2,3)行が交換できる
が満たせる場合、1,2,3の行にある数字たちは1,2,3行のそれぞれの好きな位置に配置できます。つまり、3!(3*2*1=6)パターンどの並びも操作によって並べられるということです。

上記の行列の性質から、この問題は並び替えられるグループごとに分け、それぞれのグループの個数の階乗をかけ合わせればいいことになります。(考えが飛んだ気がしますが、書くのに疲れました> <)
グループごとに分ける実装法は何個かあると思います。
今回はそれぞれの行と列を頂点、並び替え可能を辺に持つ無向グラフを作成し、そこからBFSでグループの個数を求めました。

#include<bits/stdc++.h>

using namespace std;

long long mod=998244353;

int main(){
    int N,K;
    cin>>N>>K;

    int a[N][N];

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin>>a[i][j];
        }
    }

    vector<int> vt[N],vy[K];
    for(int x=0;x<N;x++){
        for(int y=0;y<N;y++){
            if(x==y) continue;
            bool f1=true,f2=true;;
            for(int k=0;k<N;k++){
                if(a[x][k]+a[y][k]>K) f1=false;
                if(a[k][x]+a[k][y]>K) f2=false;
            }
            if(f1) {
                vt[x].push_back(y);
                vt[y].push_back(x);
            }if(f2){
                vy[x].push_back(y);
                vy[y].push_back(x);
            }
        }
    }

    long long ans=1;
    long long ok[50]={0};
    long long mod=998244353;
    for(int i=0;i<N;i++){
        if(ok[i]==0){
            queue<int> q;
            q.push(i);
            long long c=0;
            while(!q.empty()){
                int ni=q.front();
                q.pop();
                if(ok[ni]==1) continue;
                //cout<<ni<<endl;
                ok[ni]=1;
                c++;
                for(int j=0;j<vt[ni].size();j++){
                    if(ok[vt[ni][j]]==0){
                        q.push(vt[ni][j]);
                    }
                }
            }
            //cout<<i<<","<<c<<endl;
            for(int j=1;j<=c;j++){
                ans*=j;
                ans%=mod;
            }
        }
    }
    //cout<<"--------------"<<endl;
    long long ok2[50]={0};
    for(int i=0;i<N;i++){
        if(ok2[i]==0){
            queue<int> q;
            q.push(i);
            long long c=0;
            while(!q.empty()){
                int ni=q.front();
                q.pop();
                if(ok2[ni]==1) continue;
                //cout<<ni<<endl;
                ok2[ni]=1;
                c++;
                for(int j=0;j<vy[ni].size();j++){
                    if(ok2[vy[ni][j]]==0){
                        q.push(vy[ni][j]);
                    }
                }
            }
            //cout<<i<<","<<c<<endl;
            for(int j=1;j<=c;j++){
                ans*=j;
                ans%=mod;
            }
        }
    }

    cout<<ans<<endl;
}

今回は時間がなくてゴリゴリ書きましたが、UnionFindなんかを使うとスッキリすると思います。

D – Number of Multisets

D - Number of Multisets
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

1,1/2,1/4,1/8…をN個使って総和をKにする問題。
解説を見て通しました。

1を1個以上使う場合、使わない場合を考えるとスッキリします。

1を1個以上使う場合

1を1つ取り除くことにより、
1,1/2,1/4,1/8…をN-1個使って総和をK-1にする問題。
と同値になることが分かります。

1を1個以上使わない場合

1を使わないため、
1/2,1/4,1/8,1/16…をN個使って総和をKにする問題。
と言い換えることができます。この時、総和と要素を2倍にすることで
1,1/2,1/4,1/8…をN個使って総和を2Kにする問題。
と言い換えることができ、要素が元の問題となるため同値になると言えることができます。

最終的な解法

dp[N][K]とdpテーブルを持ち、これを更新することを考えます。
上で考えた2パターンを足し合わせ、
dp[N][K]=dp[N-1][K-1]+dp[N][2*N] (dp[0][0]=1)
と更新していきます。(※0個使って0にするは、あらかじめ1通りを初期値としておく)

#include<bits/stdc++.h>

using namespace std;

int main(){
    //1を使わない N個の1/2,1/4...を使ってKにする
    //         ->*2する N個の1,1/2...を使って2Kにする
    //1を使う N-1個の1,1/2,1/4を使ってK-1にする
    //1を使うかに関係なく、 N個の1,1/2...を使って2K + N-1個の1,1/2,1/4を使ってK-1 が答え
    //dp[N][K]=dp[N][2K]+dp[N-1][K-1]といえる。

    long long mod=998244353;
    long long N,K;
    cin>>N>>K;

    long long dp[N+10][2*N+10];

    for(int i=0;i<N+10;i++){
        for(int j=0;j<2*N+10;j++){
            dp[i][j]=0;
        }
    }
    dp[0][0]=1;

    for(int i=1;i<=N;i++){
        for(int j=2*i;j>=0;j--){
            long long a=0;
            if(i>=0&&i<=N&&2*j>=0&&2*j<=2*N) a=dp[i][2*j];
            long long b=0;
            if(i-1>=0&&i-1<=N&&j-1>=0&&j-1<=2*N) b=dp[i-1][j-1];
            dp[i][j]=a+b;
            dp[i][j]%=mod;
            //cout<<dp[i][j]<<",";
        }
        //cout<<endl;
    }
    cout<<dp[N][K]<<endl;
}

E – Mex Mat

E - Mex Mat
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

a11~a1Nとa21~aN1が与えられので、mexで表を埋めた際に0,1,2が幾つになるか求める問題。
解説ACしました。

実験してみる

愚直解で、解がどうなるか観察してみます。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int N;
    cin>>N;
    int a1[N],a2[N];
    for(int i=0;i<N;i++){
        cin>>a1[i];
    }
    a2[0]=a1[0];
    for(int i=1;i<N;i++){
        cin>>a2[i];
    }

    for(int i=0;i<N;i++){
        cout<<a1[i];
    }
    cout<<endl;

    for(int i=1;i<N;i++){
        cout<<a2[i];
        for(int j=1;j<N;j++){
            int mex=0;
            if(a2[i]==0&&a1[j]==0) mex=1;
            if(a2[i]==0&&a1[j]==1) mex=2;
            if(a2[i]==0&&a1[j]==2) mex=1;
            if(a2[i]==1&&a1[j]==0) mex=2;
            if(a2[i]==1&&a1[j]==1) mex=0;
            if(a2[i]==1&&a1[j]==2) mex=0;
            if(a2[i]==2&&a1[j]==0) mex=1;
            if(a2[i]==2&&a1[j]==1) mex=0;
            if(a2[i]==2&&a1[j]==2) mex=0;
            cout<<mex;
            a2[i]=mex;
            a1[j]=mex;
        }
        cout<<endl;
    }
}
15
0 1 2 0 1 2 1 1 1 2 2 2 0 0 0
1
2
0
0
0
2
1
0
1
1
1
2
0
1
012012111222000
101201020101212
210120101010101
021012010101010
010101201010101
021010120101010
202101012010101
120210101201010
012021010120101
101202101012010
120120210101201
101012021010120
210101202101012
021010120210101
102101012021010

i,jが大きいときの数字を見てみると、同じ数字が右下に伸びていることが分かります。
この実験結果を元にコーディングしていきます。

コーディング

今回、x=10までy=10までは愚直に求め、x=11,y=11からは右下に伸びる法則を使って計算で求めるようにしました。
注意点として、答えの数字がintではオーバーフローする可能性があります。long longで答えを持つようにしましょう。

#include<bits/stdc++.h>

using namespace std;

int mex(int x,int y){
    int mexi=0;
    if(x==0&&y==0) mexi=1;
    if(x==0&&y==1) mexi=2;
    if(x==0&&y==2) mexi=1;
    if(x==1&&y==0) mexi=2;
    if(x==1&&y==1) mexi=0;
    if(x==1&&y==2) mexi=0;
    if(x==2&&y==0) mexi=1;
    if(x==2&&y==1) mexi=0;
    if(x==2&&y==2) mexi=0;
    return mexi;
}

int main(){
    int N;
    cin>>N;
    int a1[N],a2[N];
    long long c[3]={0};
    for(int i=0;i<N;i++){
        cin>>a1[i];
        c[a1[i]]++;
    }
    a2[0]=a1[0];
    for(int i=1;i<N;i++){
        cin>>a2[i];
        c[a2[i]]++;
    }

    for(int i=1;i<min(N,10);i++){
        for(int j=1;j<N;j++){
            int m=mex(a2[i],a1[j]);
            c[m]++;
            a2[i]=m;
            a1[j]=m;
        }
    }

    if(N>=10){
        for(int j=1;j<10;j++){
            for(int i=10;i<N;i++){
                int m=mex(a2[i],a1[j]);
                c[m]++;
                a2[i]=m;
                a1[j]=m;
            }
        }
        for(int i=10;i<N;i++){
            int m=mex(a2[i],a1[10]);
            c[m]+=(N-i);
            a2[i]=m;
            a1[10]=m;
        }
        for(int j=11;j<N;j++){
            int m=mex(a2[10],a1[j]);
            c[m]+=(N-j);
            a1[j]=m;
            a2[10]=m;
        }
    }
    cout<<c[0]<<" "<<c[1]<<" "<<c[2]<<endl;
}

数学問が続いた後の実験問題は中々厳しいですね…。

おわりに

書いている途中にレートが更新されましたが、パフォーマンス1325でレートは1334(-1)になりました。
一先ず、ほぼ実力通りの力を出せたということで安心しました。
明日のABCも出る予定のため、この調子で頑張りたいです。

ぬるから
ぬるから

今回の問題は数学的要素が多く、受験問題を解いているような感じでした…。
個人的にはこういう問題の方が好きですが、対策はしにくいですね…。

コメント

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