はまやんはまやんはまやん

hamayanhamayan's blog

Google Code Jam Round 2 2017 問題と解説

https://code.google.com/codejam/contest/5314486/dashboard#s=p0

A. Fresh Chocolate

Nグループあり、それぞれG[i]人いる。
1パックにP個のチョコが入っている。
あるグループにチョコを上げる時はパックを開けてチョコを1人に1つ渡す。
もし、チョコが余った場合は次のグループに渡すのに使うが、その場合は新鮮でないチョコが次のグループの一部(または全部)にいってしまう。
適切な順でNグループにチョコを渡すことで、最大何グループが全員新鮮なチョコを受け取れるか。

B. Roller Coaster Scheduling

N行1列のコースター、C人の人間、M枚のチケットがある。
i番目のチケットにはB[i]さんが前からP[i]番目の席に座れると書いてある。
コースター運営者は"プロモート"を上手く行い、使うコースターの数を最小化した上で、プロモート回数も最小化したい。
以下のルールが満たされる必要がある。

  • 同じコースターに同一人物は複数人乗れない
  • 同じコースターの同じ席に複数人乗れない
  • プロモートをすると、あるチケットのP[i]をより小さい数に変更できる

C. Beaming With Joy

R行C列の盤面があり、以下の構成要素から成る。

  • / : /となってる反射板(ビームを反射する)
  • \ : \となってる反射板(ビームを反射する)
  • - : 左右にビームを発射する発射機
  • | : 上下にビームを発射する発射機
  • # : 壁(ビームが止まる)
  • . : 何もない

2種類の発射機は回転させることで-を|に、|を-に変えることができる。
発射機を適切に回転させて、以下のルールを全て満たすようにできるか。
できれば、回転後の盤面も答えよ。

  • 全ての何もない所にビームが来ている
  • 発射機にビームが当たってはいけない

D. Shoot the Turrets

未読

以下、解説


















A. Fresh Chocolate

int N, P, G[101];
int cnt[4];
//---------------------------------------------------------------------------------------------------
int dp[201][201][201];
int dodp() {
    rep(a, 0, cnt[1] + 1) rep(b, 0, cnt[2] + 1) rep(c, 0, cnt[3] + 1) dp[a][b][c] = 0;

    rep(a, 0, cnt[1] + 1) rep(b, 0, cnt[2] + 1) rep(c, 0, cnt[3] + 1) {
        int sm = a + b * 2 + c * 3;

        int d = dp[a][b][c];
        if (sm % P == 0) d++;

        dp[a+1][b][c] = max(dp[a+1][b][c], d);
        dp[a][b+1][c] = max(dp[a][b+1][c], d);
        dp[a][b][c+1] = max(dp[a][b][c+1], d);
    }

    return dp[cnt[1]][cnt[2]][cnt[3]];
}
//---------------------------------------------------------------------------------------------------
void sol() {
    cin >> N >> P;
    rep(i, 0, N) cin >> G[i];

    rep(i, 0, P) cnt[i] = 0;
    rep(i, 0, N) cnt[G[i] % P]++;

    int ans = cnt[0];

    if (P == 2) ans += (cnt[1] + 1) / 2;
    else if (P == 3) {
        int mi = min(cnt[1], cnt[2]);
        cnt[1] -= mi;
        cnt[2] -= mi;
        ans += mi;

        ans += (cnt[1] + 2) / 3;
        ans += (cnt[2] + 2) / 3;
    } else if (P == 4) {
        ans += dodp();
    }

    printf("%d\n", ans);
}|

まず、「cnt[i] = G[j] % P == iであるjの個数」としてこれを計算しておく。
全ての場合においてcnt[0]では全員とりあえず新鮮なチョコを貰えるので、これを答えに足しておく。

small解法
貪欲解で解ける。
P==2の時は、cnt[1]は奇数で2グループに1つ新鮮なチョコが得られるので、ceil(cnt[1]/2)も足す
P==3の時は、cnt[1]とcnt[2]を丁度1つずつ使うことで丁度Pが作れるので、なるだけこのペアを作る。
作れなくなったら、cnt[1]だけで、cnt[2]だけでPを作るようにして、計算する。

large解法
P == 4の時は、DPで解く(貪欲解で解いて死んだ)。
dp[a][b][c] := cnt[1]をa個、cnt[2]をb個、cnt[3]をc個使うときの新鮮なチョコを食べられるグループの最大
を計算していく。
dp[a][b][c]からdp[a+1][b][c],dp[a][b+1][c],dp[a][b][c+1]への遷移を考えていくのだが、食べる前の状況を考えてみると、(a+2b+3c) % P == 0であれば、次食べるグループは新鮮なチョコが食べられるのでインクリメントする。
これで更新してcnt[0]と合わせると答え。

B. Roller Coaster Scheduling

small解法
フローで解けるみたいです
large解法
貪欲法で解ける。JAPLJさんの解法を解読した。

int N, C, M, P[1010], B[1010];
int S[1010], K[1010];
//---------------------------------------------------------------------------------------------------
int ceil(int a, int b) { return (a + b - 1) / b; }
void solve() {
    cin >> N >> C >> M;
    rep(i, 0, M) cin >> P[i] >> B[i];
    rep(i, 0, 1010) S[i] = K[i] = 0;

    rep(i, 0, M) {
        S[P[i]]++;
        K[B[i]]++;
    }

    // 1
    int ans1 = *max_element(K, K + C + 1);

    // 2
    int sm = 0;
    rep(i, 1, N + 1) {
        sm += S[i];
        ans1 = max(ans1, ceil(sm, i));
    }

    // 3
    int ans2 = 0;
    rep(i, 1, N + 1) ans2 += max(0, S[i] - ans1);

    printf("%d %d\n", ans1, ans2);
}

1. 同じコースターに同じ人は乗れないので、ある人の乗る回数の最大値分は必要
(こうすることで同じ人が同じカートに乗ってはいけないという条件は無視できる)
2. [1,i]列目のチケット数の総数をsmとすると、各コースターのi列目まで埋めていくと考えると、ceil(sm/i)コースター必要なので、これで最大値を更新していく
3. これで必要なコースター数が分かったので、座る席をずらさないといけないのは、各席についてコースター数を上回ったときなので、これを足していく
この貪欲で答えが出せる

C. Beaming With Joy

smallとlargeで解法が全然違う(と思う)
small解法

#define rrep(i,a,b) for(int i = a;i>=b;i--)
int H, W;
string B[60];
vector<int> v;
//---------------------------------------------------------------------------------------------------
int C[60][60], ans[10101];
int chk() {
    rep(y, 0, H) rep(x, 0, W) if (B[y][x] == '.') if (C[y][x] == 0) return false;
    return true;
}
//---------------------------------------------------------------------------------------------------
bool dfs(int cu) {
    if (cu == v.size()) {
        return chk();
    }

    int x = v[cu] % W;
    int y = v[cu] / W;

    // 囲まれている
    if (B[y - 1][x] == '#' && B[y + 1][x] == '#' && B[y][x - 1] == '#' && B[y][x + 1] == '#') return dfs(cu + 1);

    // '-'
    bool ok = true;
    rep(xx, x + 1, W) {
        if (B[y][xx] == '#') break;
        if (B[y][xx] == 'X') {
            ok = false;
            break;
        }
    }
    rrep(xx, x - 1, 0) {
        if (B[y][xx] == '#') break;
        if (B[y][xx] == 'X') {
            ok = false;
            break;
        }
    }
    if (ok) {
        rep(xx, x + 1, W) {
            if (B[y][xx] == '#') break;
            C[y][xx]++;
        }
        rrep(xx, x - 1, 0) {
            if (B[y][xx] == '#') break;
            C[y][xx]++;
        }

        ans[cu] = 0;
        bool a = dfs(cu + 1);
        if (a) return true;

        rep(xx, x + 1, W) {
            if (B[y][xx] == '#') break;
            C[y][xx]--;
        }
        rrep(xx, x - 1, 0) {
            if (B[y][xx] == '#') break;
            C[y][xx]--;
        }
    }

    // '|'
    ok = true;
    rep(yy, y + 1, H) {
        if (B[yy][x] == '#') break;
        if (B[yy][x] == 'X') {
            ok = false;
            break;
        }
    }
    rrep(yy, y - 1, 0) {
        if (B[yy][x] == '#') break;
        if (B[yy][x] == 'X') {
            ok = false;
            break;
        }
    }
    if (ok) {
        rep(yy, y + 1, H) {
            if (B[yy][x] == '#') break;
            C[yy][x]++;
        }
        rrep(yy, y - 1, 0) {
            if (B[yy][x] == '#') break;
            C[yy][x]++;
        }

        ans[cu] = 1;
        bool a = dfs(cu + 1);
        if (a) return true;

        rep(yy, y + 1, H) {
            if (B[yy][x] == '#') break;
            C[yy][x]--;
        }
        rrep(yy, y - 1, 0) {
            if (B[yy][x] == '#') break;
            C[yy][x]--;
        }
    }

    return false;
}
//---------------------------------------------------------------------------------------------------
void sol() {
    cin >> H >> W;
    rep(y, 1, H + 1) cin >> B[y];

    rep(y, 1, H + 1) B[y] = "#" + B[y] + "#";
    W += 2; H += 2;
    B[0] = ""; B[H - 1] = "";
    rep(x, 0, W) B[0] += "#", B[H - 1] += "#";

    v.clear();
    rep(y, 0, H) rep(x, 0, W) if (B[y][x] == '|' || B[y][x] == '-') B[y][x] = 'X';
    rep(y, 0, H) rep(x, 0, W) if (B[y][x] == 'X') v.push_back(y * W + x);

    rep(y, 0, H) rep(x, 0, W) C[y][x] = 0;
    
    if (!dfs(0)) {
        printf("IMPOSSIBLE\n");
        return;
    }

    printf("POSSIBLE\n");
    rep(i, 0, v.size()) {
        int x = v[i] % W;
        int y = v[i] / W;
        if (ans[i] == 0) B[y][x] = '-';
        else B[y][x] = '|';
    }
    rep(y, 1, H - 1) {
        string s = B[y].substr(1, W - 2);
        printf("%s\n", s.c_str());
    }
}

無駄に長いのだが、やってることは単純で、全ての発射機を-にするか|にするかの2択で全探索している。
全ての何もない所にビームが当たるかは「C[y][x] := (x,y)にビームが当たっている回数」を使って判定する。
そのままこれをやると、終わらないので、ちょっとした枝刈りが必要で、上下左右が壁で囲まれている場合はどちらでもいいので、1択で決め打ちすると、なぜかすぐ終わる。

large解法
2-SATを使う
hamayanhamayan.hatenablog.jp
確かになぁという感じ。
実装したらLargeが落ちてデバッグ無理!

D. Shoot the Turrets

プロは費用最小流とか言ってました。