Google Code Jam2018 Round1A

GCJ Round1Aが今日の10時~12時半にあったので出ました 1500位まで通過で,788位だったので通過できました やったぜ。

 ・Waffle Choppers

R×Cのグリッドがあり,各マスは空かチョコチップがあるかのいずれか.このグリッドを線に沿って水平方向にH回,垂直方向にV回カットする.このとき(H+1)×(V+1)個の小グリッドにわかれるが,各グリッドに含まれるチョコチップの数は全て等しくなければならない.このような分割が出来るか判定せよ.という問題.

まずグリッド全体のチョコチップの数が(H+1)×(V+1)で割りきれなかったら明らかに無理.そうでないときは,あらかじめ各行・列にあるチョコチップの数を数えておくとどこでカットするべきかがわかる.水平方向・垂直方向についてそれぞれ求め,分割したあとちゃんと等しくなっているか調べればOK.

ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
const LL MOD = 1000000007LL;
char grid[100][101];
int row[100];
int column[100];
int main() {
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; t++) {
        int R, C;
        scanf("%d %d", &R, &C);
        int H, V;
        scanf("%d %d", &H, &V);
        for (int i = 0; i < R; i++) scanf("%s", grid[i]);
        int sum = 0;
        for (int i = 0; i < R; i++) {
            row[i] = 0;
            for (int j = 0; j < C; j++) if (grid[i][j] == '@') row[i]++;
            sum += row[i];
        }
        for (int i = 0; i < C; i++) {
            column[i] = 0;
            for (int j = 0; j < R; j++) if (grid[j][i] == '@') column[i]++;
        }
        if (sum % ((H+1)*(V+1)) != 0) {
            printf("Case #%d: IMPOSSIBLE\n", t);
            continue;
        }
        bool ok = 1;
        vector<int> h, v;
        h.push_back(-1);
        v.push_back(-1);
        int tmp = 0;
        for (int i = 0; i < R; i++) {
            tmp += row[i];
            if (tmp > sum / (H+1)) {
                ok = 0;
                break;
            }
            else if (tmp == sum / (H+1)) {
                tmp = 0;
                h.push_back(i);
            }
        }
        tmp = 0;
        for (int i = 0; i < C; i++) {
            tmp += column[i];
            if (tmp > sum / (V + 1)) {
                ok = 0;
                break;
            }
            else if (tmp == sum / (V + 1)) {
                tmp = 0;
                v.push_back(i);
            }
        }
        for (int i = 1; i < h.size(); i++) {
            for (int j = 1; j < v.size(); j++) {
                int cnt = 0;
                for (int k = h[i - 1] + 1; k <= h[i]; k++) {
                    for (int l = v[j - 1] + 1; l <= v[j]; l++) {
                        if (grid[k][l] == '@') cnt++;
                    }
                }
                if (cnt != sum / ((H + 1)*(V + 1))) {
                    ok = 0;
                    break;
                }
            }
            if (!ok) break;
        }
        if (ok) {
            printf("Case #%d: POSSIBLE\n", t);
        }
        else {
            printf("Case #%d: IMPOSSIBLE\n", t);
        }
    }
}

・BitParty

B個のものを買いたい.C個のレジがあり,i番目のレジでは最大M[i]個までのものを購入でき,会計にかかる時間は購入するものの数をNとしてS[i]×N+P[i]である.R個のロボットにB個のものを上手く分配して,会計が終わるまでの時間を最小化せよ,という問題(ただし購入するものがないロボットはレジにはいかず,どの2つのロボットも異なるレジを使う).

時間tまでに会計を終えられるか,という判定問題をかんがえるとにぶたんが出来そう.かけられる時間の上限が決まると各レジに何個までのものをもっていけるかがわかり,それはt≧P[i]のときmin((t-P[i])/S[i],M)個,t<P[i]のとき0個である.あとはその多い方からmin(R,C)個のレジを選んだときB個以上のものをもっていけるならOK,ダメならNGと判定ができる.

ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
const LL MOD = 1000000007LL;
LL M[1000], S[1000], P[1000];
int main() {
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; t++) {
        LL R, B, C;
        scanf("%lld %lld %lld", &R, &B, &C);
        for (int i = 0; i < C; i++) {
            scanf("%lld %lld %lld", &M[i], &S[i], &P[i]);
        }
        LL l = 0, r = 1LL << 60;
        while ((r - l) > 1) {
            LL m = (l + r) / 2;
            vector<int> v;
            for (int i = 0; i < C; i++) {
                if (P[i] >= m) continue;
                v.push_back(min((m - P[i]) / S[i], M[i]));
            }
            sort(v.begin(), v.end());
            LL sum = 0;
            for (int i = 0; i < min(R,(LL)v.size()); i++) {
                sum += v[v.size() - i - 1];
            }
            if (sum >= B) r = m;
            else l = m;
        }
        printf("Case #%d: %lld\n", t, r);
    }
}

・Edgy Baking

N個のクッキーがあり,i番目のクッキーは大きさW[i]×H[i]の長方形である.各クッキーについて,中心を通る直線に沿って2つに分割するか,そのままにするかが選べる(分割したあとに出来たクッキーをさらに分割することはできない).全クッキーの周の長さの和をP以下でPに最も近い値にしたい.この長さを求めよ.という問題.

Small(全クッキーの形状が同じ場合)しかとけなかった.元々の周の長さをLとする.あるクッキーを中心を通る直線できったときのきり口の長さはmin(H,W)以上sqrt(H^2+W^2)以下の任意の実数をとれることがわかる.周の長さはきり口の長さの2倍だけ増える.min(H,W)×2の和がP-Lをこえないようにいくつかのクッキーを選ぶと,各クッキーについてまだ周の長さを(sqrt(H^2+W^2)-min(H,W))×2だけ増やせる余地がある.この値が大きければ大きいほどよい.ということまではコンテスト中にわかった.冷静にかんがえるとmin(H,W)の和は整数なので"dp[i]=min(H,W)の和がiとなるよう選んだときの周の長さを増やせる余地の最大値"みたいなDPをすることが出来そう.