AtCoder Regular Contest 054 反省会

A,B問題を通して200点の158位でした。安定の100位台後半です。今回はC問題を通せると30位に入れるような難易度だったようで、現実的に100位以内を目指すにはA,B問題を素早く解けるかどうかという勝負になっていたようです。

以下各問振り返り

A問題『動く歩道』

消費時間 9分55秒
　SからDへ時計回りで向かう時間（rightのイメージでransと置いた）と、反時計回りで向かう時間（leftからlans）の小さい方を取ればいいと考えました。SとDの大小関係で場合分けするのは綺麗な解法ではないのかもしれませんが、安全ではある気がします。
　サンプルを通してみたらYよりXが大きい場合を考えていなかったことに気づいたので、慌てて追加したせいでさらに汚い感じになっています。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int l,x,y,s,d;
    float ans,rans,lans;
    scanf("%d %d %d %d %d",&l,&x,&y,&s,&d);
    if(s<=d){
        rans=(float)(d-s)/(x+y);
        lans=(float)(l-d+s)/(y-x);
    }else{
        rans=(float)(l-s+d)/(x+y);
        lans=(float)(s-d)/(y-x);
    }
    if(y<x){
        ans=rans;
    }else{
        ans=min(rans,lans);
    }
    printf("%f\n",ans);
}

B問題『ムーアの法則』

消費時間 53分40秒
　最初は紙の上で微分してしまってあっさり求めようとしましたが、指数関数の微分を思い出せず失敗。その流れで探索をしようという発想になったので、自然と微分した値（の正負だけを見た）での2分探索となりました。解説放送では元の関数での3分探索をしていたので、微分のステップで誤差が出るのが怖いことを考えるとそっちのほうが安全なのかもしれません。
　答えるべきなのはf(x)なのに最初xを求めていて「合わないな〜」とずっと悩んでしまいました。さらには最後答えは合っていたのに、悩んだ過程でprintfで確認していた部分をコメントアウトし忘れていて3回WA出してしまいました。これがなければ130位台くらいには入れていたみたいなので残念です。

#include <bits/stdc++.h>
using namespace std;

double p;

double f(double x){
    double ans = x + p/pow(2.0,x/1.5);
    //printf("f(%lf)=%lf\n",x,ans);
    return ans;
}

double d(double x){
    double h = 0.00001;
    double ans = f(x+h)-f(x);
    //printf("d(%lf)=%lf\n",x,ans);
    return ans;
}

double solve(){
    double minus = 0, plus = 99999999999, mid, di;
    for(int i=0; i<100000; i++){
        mid = (minus + plus) / 2;
        di = d(mid);
        if(di>0){
            plus = mid;
        }else if(di<0){
            minus = mid;
        }else{
            return f(mid);
        }
        //printf("i=%d,mid=%lf\n",i,mid);
    }
    return f(mid);
}


int main()
{
    scanf("%lf",&p);
    double ans = solve();
    printf("%.10lf\n",ans);
}

C問題『鯛焼き』

　さらっと見た感じ、全く解法が思い浮かばず、時間も残り20分くらいしかなかったのでD問題の部分点があればそっちを取りに行くほうがいいのではないかと考えてC問題を解ききるのは諦めました。

D問題『バブルソート』

　部分点あって一瞬喜んだんですが、50点ということは簡単なやつではなさそうだということで解けないんだろうなという気はしました。そもそも圧縮した数列を戻す操作を理解するのに15分くらいかかって、そこで時間切れになりました。