AtCoder Beginner Contest #011

AtCoder ABC DP 確率

ooooで総合18th．やったぜ！

http://abc011.contest.atcoder.jp/
公式解説 http://www.slideshare.net/chokudai/abc011
解説ニコ生 http://live.nicovideo.jp/watch/lv183702185

A

C++03で提出してコンパイラエラーをもらう．ペナルティにはならないらしい．

int main(){
    int n;
    while (cin >> n){
        if (n == 12) cout << 1 << endl;
        else cout << n + 1 << endl;
    }
}

B

#include<cctype>が便利．Rubyにはcapitalizeというまんまそれなメソッドがあるが本番ではC++脳が先に回った

int main(){
    string s;
    cin >> s;
    s[0] = toupper(s[0]);
    rep(i, s.size())if (i){
        s[i] = tolower(s[i]);
    }
    cout << s << endl;
}

puts gets.chomp.capitalize

C

問題にかかれているのとは逆に0から初めて足し算してもよい． 0から始めて1,2,3を足していき、NG数を踏まずにi回以内の足し算でjを作るための足し算の最小回数をdp[i][j]とおく．

dp[i][]の更新に必要なのはdp[i-1][]だけなので，下のソースコードではdp[i+1]をnext，dp[i]をcurとおいている． i=0～350，j=1～3で，cnt[i + j] = min(cnt[i + j], cnt[i] + 1)の漸化式でcur[n]までの最短手数を求め，最終的にcur[n]が100以下になるか判定する．

貪欲でも解けるらしい．

typedef vector<int> vi;
typedef vector<bool> vb;
int main(){
    int n;
    while (cin >> n){
        vi cnt(400, inf);
        vb ng(400);
        rep(i, 3){
            int x; cin >> x;
            ng[x] = true;
        }
        bool ok;
        if (ng[0]) ok = false;
        else {
            cnt[0] = 0;
            rep(i, 350){
                if (cnt[i] == inf) continue;
                loop(j, 1, 4){
                    if (!ng[i + j]){
                        cnt[i + j] = min(cnt[i + j], cnt[i] + 1);
                    }
                }
            }
            if (cnt[n] <= 100) ok = true;
            else ok = false;
        }

        if (ok) cout << "YES";
        else cout << "NO";
        cout << endl;
    }
}

D

まずxもyもDで割れない時は答えはNOで，割れるときはx,y,Dを全てDで割り，D=1で考える． 漸化式を立てて普通にDPだが，DPテーブルの大きさをWHとしたとき，O(NH*W)だと微妙な定数倍高速化をしないと通らない．

  • doubleの誤差を考え，答えの許容誤差の10^-9に影響しないような値は切る
  • 同様に誤差を考えてDPテーブルを縮める
  • ループ展開する

で通った．個人的にはあまり好きではないけど，こういうテクニックを使わせる点で教育的なのかなと思った．

→これは想定解法ではないらしく、公式解説にもっと賢い方法があります．

int main(){
    int n, d, x, y;
    while (cin >> n >> d >> x >> y){
        double p;
        if (x%d == 0 && y%d == 0){

            const int w = 350;
            const int h = 350;

            x /= d; y /= d;
            x += w / 2; y += h / 2;

            if (!in(x, y, w, h)) p = 0;
            else {

                vvd cur(h, vd(w, 0));
                cur[h / 2][w / 2] = 1;

                int const dx[] = { 1, 0, 0, -1 };
                int const dy[] = { 0, 1, -1, 0 };

                rep(i, n){
                    vvd next(h, vd(w, 0));
                    rep(y, h)rep(x, w){
                        // ループ展開(dx[],dy[]をループで回るとTLE)
                        int nx, ny;
                        nx = x + 0;
                        ny = y + 1;
                        if (!in(nx, ny, w, h) || cur[y][x] < 1e-10) goto aaa;
                        next[ny][nx] += cur[y][x] / 4;

                    aaa:;

                        nx = x + 0;
                        ny = y + -1;
                        if (!in(nx, ny, w, h) || cur[y][x] < 1e-10) goto bbb;
                        next[ny][nx] += cur[y][x] / 4;

                    bbb:;

                        nx = x + 1;
                        ny = y + 0;
                        if (!in(nx, ny, w, h) || cur[y][x] < 1e-10) goto ccc;
                        next[ny][nx] += cur[y][x] / 4;

                    ccc:;

                        nx = x + -1;
                        ny = y + 0;
                        if (!in(nx, ny, w, h) || cur[y][x] < 1e-10) continue;
                        next[ny][nx] += cur[y][x] / 4;
                    }
                    swap(next, cur);
                }
                p = cur[x][y];
            }
        }
        else {
            p = 0;
        }

        cout << fixed << setprecision(30) << p << endl;
    }
}