yukicoder contest 70(No.110～No.112)

No.110 しましまピラミッド
No.111 あばばばば
No.112 ややこしい鶴亀算

No.110 しましまピラミッド

下の段が大きければ大きいほど上に積める可能性が高くなるため、長いブロックを貪欲に積んでいくのがベストです。
一番下の段を白か黒のどちらかにするか迷いそうですが、制約が大したことないため、2通り試して大きいほうを取るで問題ありません。

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

using namespace std;
//using namespace atcoder;

int main(){

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

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

    sort(W,W+Nw);
    sort(B,B+Nb);

    int c1=1;
    int l=W[Nw-1];
    int Widx=Nw-2;
    int Bidx=Nb-1;
    while(1){
        if(c1%2==1){
            if(Bidx<0) break;
            if(l>B[Bidx]){
                l=B[Bidx];
                c1++;
            }
            Bidx--;
        }
        else{
            if(Widx<0) break;
            if(l>W[Widx]){
                l=W[Widx];
                c1++;
            }
            Widx--;
        }
    }
    int c2=1;
    l=B[Nb-1];
    Widx=Nw-1;
    Bidx=Nb-2;
    while(1){
        if(c2%2==0){
            if(Bidx<0) break;
            if(l>B[Bidx]){
                l=B[Bidx];
                c2++;
            }
            Bidx--;
        }
        else{
            if(Widx<0) break;
            if(l>W[Widx]){
                l=W[Widx];
                c2++;
            }
            Widx--;
        }
    }

    cout<<max(c1,c2)<<endl;
}

No.111 あばばばば

No.111 あばばばば - yukicoder

競技プログラミングの練習サイト

最小の回文”aba”や”bab”があり、次に大きい回文は5文字の”ababa”や”babab”です。
実は、abababababa…という文字列の部分文字列が3+2n (0<=n)の長さであれば、必ず回文になります。
※最小3文字の回文に2文字付けていくと回文になるため。

これを効率よく数え上げればACです。
私は”2文字付けていく”を割り算で求めることにより、愚直な数え上げを高速化させました。

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

using namespace std;
//using namespace atcoder;

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

    long long ans=0;
    for(int i=3;i<=L;i++){
        long long l=L-i;
        if(l>=0){
            ans++;
            ans+=l/2;
        }
    }

    cout<<ans<<endl;
}

No.112 ややこしい鶴亀算

No.112 ややこしい鶴亀算 - yukicoder

競技プログラミングの練習サイト

それぞれの報告した数は、本来の合計-2(鶴の報告)か、本来の合計-4(亀の報告)のどちらかになるはずです。
報告した数が全て同じかそうでないかで場合分けして解きます。

報告した数が全て同じ
→全て亀なら(N-1)*4、全て鶴なら(N-1)*2になるので調べる
報告した数が全て同じじゃない
→本来の合計-2(鶴の報告)か、本来の合計-4(亀の報告)のどちらかになる。
　鶴の報告の方が、報告し忘れる自分の足の数が少ないため、報告する数が大きくなるはず。
　なので、大きい値を鶴、小さい数を亀として数えていけばよい。

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

using namespace std;
//using namespace atcoder;

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

    int a[N];
    bool same=true;
    int mx=0;
    for(int i=0;i<N;i++){
        cin>>a[i];
        if(i>=1&&a[i-1]!=a[i]) same=false;
        mx=max(mx,a[i]);
    }

    if(same){
        if(a[0]==2*(N-1)) cout<<N<<" 0"<<endl;
        else cout<<"0 "<<N<<endl;
    }
    else{
        int k=0,t=0;
        for(int i=0;i<N;i++){
            if(mx==a[i]) t++;
            else k++;
        }
        cout<<t<<" "<<k<<endl;
    }


}