AtCoder Regular Contest 053 反省会

競技プログラミング

　A問題とB問題だけ通せて200点の177位でした。今回を除いて直近2回のAtCoder主催コンテストで順位が189、158なので、まぁこれくらいの位置が今の実力なんだろうとわかってきました。まだ10回ちょっとしか参加してないし、根本的に経験が足りてないなぁと思う次第です。

以下各問振り返り

A問題『ドミノ色塗り』

消費時間 2分26秒 何故か最初にansを0で初期化し、別々に足すという無駄な工程を経ています。思考の順番がそのまま現れていますね。

#include <bits/stdc++.h>

int main()
{
    int h,w;
    scanf("%d %d",&h,&w);
    int ans=0;
    ans+=(w-1)*h;
    ans+=(h-1)*w;
    printf("%d\n",ans);
}

B問題『回文分割』

消費時間 24分33秒 回文に分けるときには中央に来る文字(center)とその両側に足していく文字(add)を分けて考えるべきだと気づくまでに結構時間がかかってしまいました。一度WA出してから修正したので、答える部分の場合分けがprintしてreturnだったりansに正答を代入だったりでぐちゃぐちゃになってしまいました。

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;

int main()
{
    string s;
    cin>>s;
    int n=s.size();
    int center=0,add=0;
    int c[26]={0};
    REP(i,n){
        c[s[i]-'a']++;
    }
    REP(i,26){
        if(c[i]%2==0){
            add+=c[i]/2;
        }else{
            center++;
            c[i]--;
            add+=c[i]/2;
        }
    }


    //printf("add=%d center=%d\n",add,center);
    int ans;

    if(add==0){
        printf("1\n");
        return 0;
    }else if(center==0){
        printf("%d\n",n);
        return 0;
    }else{
        if(add/center==0) {
            ans=1;
        }else{
            ans=1+2*(add/center);
        }
    }
    printf("%d\n",ans);
}

C問題『魔法使い高橋君』

消費時間 1時間3分1秒 最初は全探索→簡略化の流れでいくのかなと思っていろいろ考えていたのですが、そもそも全探索もn!とか大変なことになるのではと気づき、二分探索でできないかなと考えました。最大気温がX℃以下であるかどうかをうまく判定できていないのでその時点でどうしようもないですね。
結局、2つの要素を持つ配列を片方の要素について技術的にソートできないのが足を引っ張っています。と、思ったのですが、上手くベクトルに入れていけば良かったのですね。

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;
int n;
long long int sum=0;
long long temp=0;
vector<int> a, b, c, flag;

long long int ok=1000000000,ng=-99999999999999,mid=0;

bool isOK(int x){
    if(sum>x) return false;
    
    int rest=n;
    int frest=n;
    int div=1;
    while(div){
        REP(i,n){
            if(flag[i]==1){
                continue;
            }else{
                if(c[i]<=0 && a[i]+temp<=x){
                    temp+=c[i];
                    flag[i]=1;
                    rest--;
                }
            }
        }
        if(rest==0) return true;
        div = frest - rest;
        frest = rest;
    }
    return false;
}

long long int solve(int x){
    while(ok-ng>1){
        printf("ok=%lld ng=%lld x=%d\n",ok,ng,x);
        printf("isOK=%d\n",isOK(x));
        if(isOK(x)){
            ok=x;
            mid=(ok+ng)/2;
        }else{
            ng=x;
            mid=(ok+ng)/2;
        }
    }
    return ok;
}

int main()
{
    scanf("%d",&n);
    REP(i,n){
        int ain,bin,cin;
        scanf("%d %d",&ain, &bin);
        a.push_back(ain);
        b.push_back(bin);
        c.push_back(ain-bin);
        sum+=c[i];
        flag.push_back(0);
    }
    printf("sum=%lld\n",sum);
    int ans=solve(mid);
    printf("%d\n",ans);

}

D問題『2つの山札』

問題文すら読んでませんし解説をみる感じだとまだ全然わかりそうにないです……。