AtCoder Beginner Contest 125(ABC125) 解説

ABC

A – Biscuit Generator

A - Biscuit Generator
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp

T+0.5秒後ですが、ビスケットが生産される間隔が整数倍なためT秒まで(Tを含む)と考えてOKです。
そのため、TをAで割った数が生産回数になり、それにBを掛けた数がビスケットの数になります。

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

using namespace std;
using namespace atcoder;

signed main(){
    int A,B,T;
    cin>>A>>B>>T;
    
    cout<<T/A*B<<endl;
}

B – Resale

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

幾つ選んでもいいため、価値-コストが正であるような宝石を選べば選ぶほどX-Yは大きくなるはずです。

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

using namespace std;
using namespace atcoder;

signed main(){
    int N;
    int V[20],C[20];
    
    cin>>N;
    
    for(int i=0;i<N;i++){
        cin>>V[i];
    }
    for(int i=0;i<N;i++){
        cin>>C[i];
    }
    
    int ans=0;
    for(int i=0;i<N;i++){
        if(V[i]-C[i]>=0) ans+=V[i]-C[i];
    }
    
    cout<<ans<<endl;
}

C – GCD on Blackboard

C - GCD on Blackboard
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp

一つ自由に書き換えて良いということは、残りのN-1個で作るgcdにできるということです。
私の方針としては、各Aを素因数分解し、素因数の数を比較することで、その数を消したときに共通の素因数がいくつできるか求め、そこから最大のgcdを計算しました。

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

using namespace std;
using namespace atcoder;

int main(){
    vector<int> pri;
    int hurui[31624]={0};
    for(int i=2;i<31624;i++){
        if(hurui[i]==0){
            pri.push_back(i);
            //cout<<i<<endl;
            for(int j=i;j<31624;j+=i){
                hurui[j]=1;
            }
        }
    }

    int N;
    cin>>N;
    int A[N];
    int ans[N];
    for(int i=0;i<N;i++){
        cin>>A[i];
        ans[i]=1;
    }

    int all=1;
    for(int i=0;i<pri.size();){
        int c=0;
        int no=-1;
        int on=0;
        for(int j=0;j<N;j++){
            if(A[j]%pri[i]==0){
                c++;
                A[j]/=pri[i];
            }
            else no=j;
            if(A[j]==1) on++;
        }
        if(c==N) all*=pri[i];
        else if(c==N-1) ans[no]*=pri[i];
        else i++;
        if(on>=2) break;
    }

    int k=0;
    for(int i=0;i<N;i++){
        int tmp=A[i];
        if(k==3) break;
        if(A[i]!=1){
            int c=0;
            int no=-1;
            for(int j=0;j<N;j++){
                if(A[j]%tmp==0){
                    c++;
                    A[j]/=tmp;
                }
                else no=j;
            }
            if(c==N) all*=tmp;
            else if(c==N-1) ans[no]*=tmp;
            k++;
        }
    }

    int mx=1;
    for(int i=0;i<N;i++){
        mx=max(mx,ans[i]);
    }

    cout<<mx*all<<endl;
}

1045msとC++でこの速度なので、想定外っぽい回答です。
ちなみに想定解は凄く賢く、左右のgcdの累積を取ることで最大を計算していました。

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

using namespace std;
using namespace atcoder;

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

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

    int gcd1[N];
    int gcd2[N];

    gcd1[0]=A[0];
    for(int i=1;i<N;i++){
        gcd1[i]=gcd(A[i],gcd1[i-1]);
    }

    gcd2[N-1]=A[N-1];
    for(int i=N-2;i>=0;i--){
        gcd2[i]=gcd(A[i],gcd2[i+1]);
    }

    int mx=1;
    for(int i=0;i<N;i++){
        if(i==0) mx=max(mx,gcd2[1]);
        else if(i==N-1) mx=max(mx,gcd1[N-2]);
        else mx=max(mx,gcd(gcd1[i-1],gcd2[i+1]));
    }

    cout<<mx<<endl;
}

ちなみに、この問題9月にセグ木の練習として解いていました。セグ木にgcdをのっけて、一点更新しながら区間のgcdを計算していました。少し大げさですね。

#include<bits/stdc++.h>
 
using namespace std;
 
//0-index
vector<int> seqv;
int seqv_n;
int gcd(int a,int b){
    if(a<b) return gcd(b,a);
    if(b==0) return a;
    return gcd(b,a%b);
}
 
void seg_debug(){
    cout<<"---------seg_debug------n="<<seqv_n<<endl;
    int k=1;
    for(int i=0;i<(seqv_n+1)*2-1;i++){
        if(k==i) {
            cout<<endl;
            k=k*2+1;
        }
        cout<<seqv[i]<<" ";
    }
    cout<<endl<<"------------------------------"<<endl;
}
 
void seg_init(int N,int a){
    seqv.clear();
    int n=1;
    while(n<N) n*=2;
    seqv_n=n-1;
    n*=2;
    n=n-1;
    for(int i=0;i<n;i++){
        seqv.push_back(a);
    }
}
 
void seg_update(int n,int a){
    int k=n+seqv_n;
    seqv[k]=a;
    while(k>0){
        k=(k-1)/2;
        if(seqv[k*2+1]==INT_MAX) seqv[k]=seqv[k*2+2];
        else if(seqv[k*2+2]==INT_MAX) seqv[k]=seqv[k*2+1];
        else seqv[k]=gcd(seqv[k*2+1],seqv[k*2+2]);
    }
}
 
 
int seg_find(int x,int y){
    struct segF{
        static int segfind(int x,int y,int k,int l,int r){
            //cout<<x<<","<<y<<","<<k<<","<<l<<","<<r<<endl;
            if(r<x||l>y) return INT_MAX;
            if(l>=x&&r<=y) return seqv[k];
            else{
                int segl=segfind(x,y,k*2+1,l,(l+r)/2);
                int segr=segfind(x,y,k*2+2,(l+r)/2+1,r);
                if(segl==INT_MAX) return segr;
                if(segr==INT_MAX) return segl;
                return gcd(segl,segr);
            }
        }
    };
    return segF::segfind(x,y,0,0,seqv_n);
}
 
int main(){
    int n;
    cin>>n;
    seg_init(n,INT_MAX);
    for(int i=0;i<n;i++){
        int A;
        cin>>A;
        seg_update(i,A);
    }
 
    int ans=seg_find(0,n-1);
    for(int i=0;i<n;i++){
        int a=seg_find(i,i);
        seg_update(i,INT_MAX);
        ans=max(ans,seg_find(0,n-1));
        seg_update(i,a);
    }
    cout<<ans<<endl;
}

解いたときの話は、noteの方にまとめています。

セグメント木を育てる 1｜ぬるから
ぬるからです。 青になるために、セグメント木(SegmentTree)なるものの習得が必須だと感じました。 少し勉強したり、ライブラリとして作ったので纏めてみます。 ・例題 AOJ:Range Minimum Query (RMQ) セグメ...
note.com

D – Flipping Signs

D - Flipping Signs
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp

左に反転処理を行う場合

+ + -> - -
+ - -> - +
- + -> + -
- - -> + +

となります。上から、以下のことが言えます。

  • 操作前と操作後で+と-の数は変わらない
  • -の位置は左右に好きなだけ移動でき、二つ繋げたら消せる

つまり、マイナスを2個ずつ好きなように消すことができるという訳です。
なので、この問題は以下のように解くことができます。

  • マイナスが偶数個の場合、全部消せるので絶対値の合計が答え
  • マイナスが奇数個の場合、1つ以外全部消せるので絶対値の最小以外の総和から絶対値の最小を引いた数が答え
  • ただし、0がある場合は0にマイナスを送り込めるので、必ずマイナスを全て消せる
#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

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

    long long A[N];
    int ms=0;
    int ze=0;
    for(int i=0;i<N;i++){
        cin>>A[i];
        if(A[i]<0) ms++;
        if(A[i]==0) ze++;
        A[i]=abs(A[i]);
    }
    if(ze>0) ms=0;

    sort(A,A+N);
    long long ans=0;
    for(int i=1;i<N;i++){
        ans+=A[i];
    }

    if(ms%2==0) ans+=A[0];
    else ans-=A[0];

    cout<<ans<<endl;

}

サンプルにない0入力の場合が厄介ですね。

コメント

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