競プロ参加記027 AtCoder Regular Contest 110(ARC110) ~鹿島建設プログラミングコンテスト2020~

Atcoder

はじめに

鹿島建設プログラミングコンテスト2020(AtCoder Regular Contest 110) – AtCoder

出張や新作ゲームの発売があり、競プロが少しできていませんでしたが、コンテストには何とか参加しました。
結果はA,B,Cの三完でした。

A – Redundant Redundancy

A – Redundant Redundancy (atcoder.jp)

2~Nを掛けた値は、2~Nの約数を持っているため2~Nで割り切ることができます。
さらに、この2~Nを掛けた値に1を加えることで、2~Nで割った際に余りを1にすることができます。(N%k=0のとき、(N+1)%k=1になります)
これでOKとしたいのですが、Nの制約が最大30で、出力の許容範囲が10^13以下です。2~Nを単純に掛けると越えてしまします。

ここで、最小公倍数を使います。最小公倍数とは、ある集合Aの値全て割り切れるものの中で最小の値です。
最小公倍数を求めて、そこに1加えることで題意の数が求まります。

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

using namespace std;
//using namespace atcoder;

long long gdb(long long a,long long b){
    if(a<b) return gdb(b,a);
    if(b==0) return a;
    return gdb(b,a%b);
}
int main(){
   long long N;
   cin>>N;

   long long ans=2;
   for(long long i=3;i<=N;i++){
       ans=ans*i/gdb(ans,i);
   }
   cout<<ans+1<<endl;
}

最小公倍数は最大公約数(gdb)を用いて計算します。
2つの値を掛けて、共通の素因数をgdbで割ることで消している感じです。

B – Many 110

B – Many 110 (atcoder.jp)

Tが1101101….か1011011011….か0110110110…である場合、部分文字列が存在します。それ以外の場合は存在しません。
それぞれの場合でいくつ含まれるか考えてみます(考えやすくするためS=110110110とします)。

110

110の場合、Sには3つ含まれています。
110110と1つ110が増えた場合、Sの最後の110が含まれなくなるため2つになります。
このように、110の繰り返しが1増えるごとに、Sの部分文字列の数が1減っていきそうです。
また、繰り返しが途中の場合(1101など)も、Sの最後の部分が対応できなくなるため1つ減ってしまいます。よってS=110110110の場合

3-((N/3)-1)-(N%3!=0)

となりそうです。

101

110の場合と考え方は同じですが、101と最小の場合でも110110110には2つしか含まれません。
101101と繰り返しが増えるごとに、最後が対応できなくなり1つ減っていくのは同様です。
また、1011や10110といった途中でも101の場合は最後が対応できます。
よって、S=110110110の場合、

3-(N/3);

`となりそうです。

011

101の場合と同じですが、途中の場合が違います。
0110と1つ途中の場合は最後が対応できますが、01101と2つ途中の場合は対応できません。
よって、S=110110110の場合、

-(N/3)-(N%3==2)

となりそうです。

結果

Tから3つのどのパターンかに場合分けし、それぞれの場合で計算すればOKです。

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

using namespace std;
//using namespace atcoder;

int main(){
    int N;
    string T;
    cin>>N;
    cin>>T;

    bool f1=true;
    for(int i=0;i<N;i++){
        if(i%3==0&&T[i]!='1') f1=false;
        if(i%3==1&&T[i]!='1') f1=false;
        if(i%3==2&&T[i]!='0') f1=false;
    }
    bool f2=true;
    for(int i=0;i<N;i++){
        if(i%3==0&&T[i]!='1') f2=false;
        if(i%3==1&&T[i]!='0') f2=false;
        if(i%3==2&&T[i]!='1') f2=false;
    }
    bool f3=true;
    for(int i=0;i<N;i++){
        if(i%3==0&&T[i]!='0') f3=false;
        if(i%3==1&&T[i]!='1') f3=false;
        if(i%3==2&&T[i]!='1') f3=false;
    }
    long long ans=0;
    if(f1){
        ans+=10000000000ll-((N/3)-1)-(N%3!=0);
    }
    if(f2){
        ans+=10000000000ll-(N/3);
    }
    if(f3){
        ans+=10000000000ll-(N/3)-(N%3==2);
    }

    cout<<ans<<endl;
}

(入力例に101のパターンしかなく、意地悪だなぁと思いました。1発ACできて良かったですが、ハマると大変そうです。)

C – Exoswap

C – Exoswap (atcoder.jp)

1回しか交換できないため、2 4 1 5 3のように1が3番目にある場合、操作2→操作1と2回操作し1を端にする必要があります。先に操作1をして2を確定させようとしたりすると、1の経路がなくなるため悪手です。
…と、このように端から決めていくようなパターンがあるかを見ていくのが最適だと言えます。(今回の操作の場合、1を端に送る手順が1通りしかないため、端から決めて出来なさそうなら、どうやってもできないといえる)

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

using namespace std;
//using namespace atcoder;

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

    set<int> s;
    int ans[N],ansc=0;
    for(int i=0;i<N;i++){
        //cout<<"==="<<P[i]<<endl;
        if(P[i]!=i+1){
            int idx;
           // cout<<"---"<<i<<endl;
            for(idx=i+1;idx<N;idx++){
                if(P[idx]==i+1) break;
            }
            if(idx==N){
                cout<<"-1"<<endl;
                return 0;
            }
            for(int j=idx;j>=i+1;j--){
                if(s.find(j)!=s.end()){
                    cout<<"-1"<<endl;
                    return 0;
                }
                //cout<<j<<endl;
                s.insert(j);
                ans[ansc++]=j;
                swap(P[j],P[j-1]);
            }
        }
    }

    for(int i=0;i<N;i++){
        if(P[i]!=i+1){
            cout<<"-1"<<endl;
            return 0;
        }
    }
    if(ansc!=N-1){
        cout<<"-1"<<endl;
        return 0;
    }
    for(int i=0;i<ansc;i++){
        cout<<ans[i]<<endl;
    }
}

太字で書かれていますが、”ちょうど1回ずつ”という制約があります。なので、1 2 3 4みたいに、元々昇順になっているような数列は-1になります。(これのせいで2WAしたx x)

おわりに

過去最高パフォーマンス(1917)が出ました!
この調子で青に突入していきたいですね:)

コメント

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