Google Code Jam 2017 Round 1A 問題と解説

https://code.google.com/codejam/contest/5304486/dashboard

A. Alphabet Cake

R*Cのマスがある。
各マスは?かA～Zで塗られている。
A～Zは最多"1つ"だけ書かれている。
残りの?のマスを全ての文字の領域が長方形になるようにA～Zを塗れ。

B. Ratatouille

（キレた）

C. Play the Dragon

自分の体力Hd攻撃力Ad, 敵の体力Hk攻撃力Akである。
自分が先攻で以下の行動ができる。

1. 攻撃 : 攻撃力分だけ相手の体力を減らす
2. バフ : 攻撃力を+Bする
3. 回復 : 体力をHdにする
4. デバグ : 相手の攻撃力を-Dする

最短何ターンで勝てるか。勝てないならIMPOSSIBLE

以下、解説

A. Alphabet Cake

int R, C;
string B[25];
void sol() {
    cin >> R >> C;
    rep(y, 0, R) cin >> B[y];

    // yoko
    rep(y, 0, R) {
        rep(x, 0, C) if (B[y][x] != '?') {
            int xx = x - 1;
            while (0 <= xx) {
                if (B[y][xx] != '?') break;
                B[y][xx] = B[y][x];
                xx--;
            }

            xx = x + 1;
            while (xx < C) {
                if (B[y][xx] != '?') break;
                B[y][xx] = B[y][x];
                xx++;
            }
        }
    }

    // tate
    rep(x, 0, C) {
        rep(y, 0, R) if (B[y][x] != '?') {
            int yy = y - 1;
            while (0 <= yy) {
                if (B[yy][x] != '?') break;
                B[yy][x] = B[y][x];
                yy--;
            }

            yy = y + 1;
            while (yy < R) {
                if (B[yy][x] != '?') break;
                B[yy][x] = B[y][x];
                yy++;
            }
        }
    }

    rep(y, 0, R) printf("%s\n", B[y].c_str());
}
//-----------------------------------------------------------------------------------
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int T; cin >> T;
    rep(t, 1, T + 1) {
        printf("Case #%d:\n", t);
        sol();
        fprintf(stderr, "Finish : %d\n", t);
    }
}

貪欲法
各行について横に適当に文字を伸ばす。
?しか無い行は?だけで残るので、そこを埋めるために各列についてまた伸ばす。

B. Ratatouille

SmallケースがWAなのでもう無理。誤読のデバッグが終わらない。
プロへの道
kmjp.hatenablog.jp
ei1333.hateblo.jp

C. Play the Dragon

typedef long long ll;
#define INF 1LL<<60
int B, D, Hd;
ll memo[101][101][101][101];
int vis[101][101][101][101];
ll rec(int hd, int Ad, int Hk, int Ak) {
    if (0 < memo[hd][Ad][Hk][Ak]) return memo[hd][Ad][Hk][Ak];
    if (vis[hd][Ad][Hk][Ak]) return INF;
    vis[hd][Ad][Hk][Ak] = 1;

    //fprintf(stderr, "[%d %d %d %d]\n", hd, Ad, Hk, Ak);

    auto &dp = memo[hd][Ad][Hk][Ak];

    ll ret = INF;

    // Can Win
    if (Hk <= Ad) ret = 1;
    else {
        // Attack
        if (Ak < hd) ret = min(ret, rec(hd - Ak, Ad, Hk - Ad, Ak) + 1);

        // Buff
        if (Ak < hd) {
            if(Ad + B <= 100) ret = min(ret, rec(hd - Ak, Ad + B, Hk, Ak) + 1);
            else ret = min(ret, 2LL);
        }

        // Cure
        if (Ak < Hd) ret = min(ret, rec(Hd - Ak, Ad, Hk, Ak) + 1);

        // Debuff
        if (max(0, Ak - D) < hd) ret = min(ret, rec(hd - max(0, Ak - D), Ad, Hk, max(0, Ak - D)) + 1);
    }

    //printf("[%d %d %d %d] = %d\n", hd, Ad, Hk, Ak, ret);

    return dp = ret;
}
ll sol() {
    int Ad, Hk, Ak;
    cin >> Hd >> Ad >> Hk >> Ak >> B >> D;

    rep(a, 0, 101) rep(b, 0, 101) rep(c, 0, 101) rep(d, 0, 101) vis[a][b][c][d] = memo[a][b][c][d] = 0;
    return rec(Hd, Ad, Hk, Ak);
}
//-----------------------------------------------------------------------------------
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int T; cin >> T;
    rep(t, 1, T + 1) {
        ll ans = sol();
        if(ans == INF) printf("Case #%d: IMPOSSIBLE\n", t);
        else printf("Case #%d: %lld\n", t, ans);
        fprintf(stderr, "Finish : %d\n", t);
    }
}

Small
メモ化再帰をする。
体力の上限が100なので、バフをして上げる攻撃力も最大100までで良い。
これで状態空間が10^8に収まって正解できる。
Large
無理でした。