読者です 読者をやめる 読者になる 読者になる

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

hamayanhamayan's blog

Google Code Jam Qualification Round 2017 問題と解説

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

問題

A. Oversized Pancake Flipper

+と-から成る文字列Sがある。
連続する丁度K個の文字をひっくり返して全て+にする。
最小何回ひっくり返すと全て+になるか。
不可能ならIMPOSSIBLE

B. Tidy Numbers

N以下で最大のtidyな数を答えよ。
tidyな数 : 各桁毎で見ると狭義単調増加列である数

C. Bathroom Stalls

x=0, x=N+1に仕切りがしてある。
以下のルールでK個の仕切りを追加する。

  • 左右の仕切りへの距離Ls,Rsのmin(Ls,Rs)が最大となるx座標に置く
  • 複数個候補があるならば、その中でmax(Ls,Rs)が最大となるx座標に置く
  • それでも、複数個候補がある場合は最も左に置く

K個目の仕切りを置いた時の、左右の距離の最大と最小を答えよ。

D. Fashion Show

N*NのグリッドにM個の'+','x','o'が置いてある。
'+'と'x'は1ポイント、'o'は2ポイント入る。
ポイントを最大化するが、以下のルールを守る必要がある。

  • 左右上下の任意の二組のうち、どちらか1つが'+'
  • 対角線上の任意の二組のうち、どちらか1つが'x'

以下の操作を行ってルールを守りつつポイントを最大化せよ。

  • '+'と'x'を'o'にする
  • 空の所に任意の記号を追加する


以下、解説





















A. Oversized Pancake Flipper

string S; int K;
int sol() {
    int N = S.length();
    int ans = 0;
    rep(i, 0, N - K + 1) if (S[i] == '-') {
        rep(j, 0, K) {
            if (S[i + j] == '-') S[i + j] = '+';
            else S[i + j] = '-';
        }
        ans++;
    }
    rep(i, 0, N) if (S[i] == '-') return -1;
    return ans;
}
//-----------------------------------------------------------------------------------
int main() {
    int T; cin >> T;
    rep(t, 1, T + 1) {
        cin >> S >> K;
        int ans = sol();
        if(ans < 0) printf("Case #%d: IMPOSSIBLE\n", t);
        else printf("Case #%d: %d\n", t, ans);
    }
}

貪欲法で解く。
先頭から順に-ならば反転させていく。
最後に全て+か判定してダメならIMPOSSIBLEとすれば良い。

B. Tidy Numbers

#define rrep(i,a,b) for(int i=a;i>=b;i--)
string S;
string sol() {
    int N = S.length();
    rrep(i, N - 2, 0) if (S[i] > S[i + 1]) {
        if (S[i] == '1' && i == 0) {
            rep(j, 0, N) S[j] = '9';
            return S.substr(1);
        }

        S[i]--;
        rep(j, i + 1, N) S[j] = '9';
    }
    return S;
}
//-----------------------------------------------------------------------------------
int main() {
    int T; cin >> T;
    rep(t, 1, T + 1) {
        cin >> S;
        printf("Case #%d: %s\n", t, sol().c_str());
    }
}

桁DPをする…と見せかけて貪欲法。
下の位から狭義単調増加してないかを判別する。
もしtidyに反するならば、上の位をデクリメントして、それ以降の桁を全て9で埋める。
これを上まで繰り返していけば答えが得られる。
証明できないし、微妙に正しくないような気もするけど、通る。

C. Bathroom Stalls

typedef long long ll;
ll N, K;
pair<ll, ll> sol() {
    priority_queue<ll> que;
    map<ll, ll> cnt;
    
    que.push(N);
    cnt[N] = 1;
    ll pre = N + 1;
    while (!que.empty()) {
        ll q = que.top(); que.pop();
        if (pre <= q) continue;

        ll a = (q - 1) / 2;
        ll b = q - 1 - a;
        if (cnt[q] < K) {
            cnt[a] += cnt[q];
            cnt[b] += cnt[q];
            K -= cnt[q];
            cnt[q] = 0;
            que.push(a);
            que.push(b);
        } else {
            cnt[a] += K;
            cnt[b] += K;
            cnt[q] -= K;
            return { max(a,b), min(a,b) };
        }

        pre = q;
    }
    return { 0,0 };
}
//-----------------------------------------------------------------------------------
int main() {
    int T; cin >> T;
    rep(t, 1, T + 1) {
        cin >> N >> K;
        auto ans = sol();
        printf("Case #%d: %lld %lld\n", t, ans.first, ans.second);
    }
}

ダイクストラっぽいBFSをする。
条件より、仕切りが入るのは空白区間の最も長い所から埋まっていくので、それをシミュレーションしていく。
空白区間は約半分になるので、空白区間の状態集合はそんなに大きくないと想像でき、BFSが使える。
cnt[i] := 長さiの空白区間の個数
として、個数を数えながら、丁度K個目となるものを探していく。
あればそれを答えるだけ。

D. Fashion Show

int N, M;
char A[10101];
int B[10101], C[10101];
//-----------------------------------------------------------------------------------
string board[101], init[101];
void makeBoard(string *ptr) {
    rep(y, 0, N) {
        ptr[y] = "";
        rep(x, 0, N) ptr[y] += ".";
    }
    rep(i, 0, M) ptr[B[i] - 1][C[i] - 1] = A[i];
}
void debugPrint() {
    cout << endl;
    rep(y, 0, N) cout << board[y] << endl;
}
//-----------------------------------------------------------------------------------
int ngx[101], ngy[101];
void solveX() {
    rep(y, 0, N) ngy[y] = 0;
    rep(x, 0, N) ngx[x] = 0;
    rep(y, 0, N) rep(x, 0, N) if (board[y][x] == 'x' || board[y][x] == 'o') ngx[x] = ngy[y] = 1;

    rep(y, 0, N) rep(x, 0, N) if (board[y][x] == '.' || board[y][x] == '+') {
        if (ngx[x]) continue;
        if (ngy[y]) continue;

        if (board[y][x] == '.') board[y][x] = 'x';
        else board[y][x] = 'o';
        ngx[x] = ngy[y] = 1;
    }
}
//-----------------------------------------------------------------------------------
void solvePlusSmall() {
    rep(x, 0, N) {
        if (board[0][x] == '.') board[0][x] = '+';
        else if (board[0][x] == 'x') board[0][x] = 'o';
    }

    rep(x, 1, N - 1) {
        if (board[N - 1][x] == '.') board[N - 1][x] = '+';
        else if (board[N - 1][x] == 'x') board[N - 1][x] = 'o';
    }
}
void solvePlusLarge() {
    // todo
}
//-----------------------------------------------------------------------------------
void sol() {
    makeBoard(init);
    makeBoard(board);

    //debugPrint();

    solveX();

    //debugPrint();

    //solvePlusSmall();
    solvePlusLarge();

    //debugPrint();

    int point = 0;
    rep(y, 0, N) rep(x, 0, N) {
        if (board[y][x] == 'o') point += 2;
        else if (board[y][x] == '+') point++;
        else if (board[y][x] == 'x') point++;
    }

    int cnt = 0;
    rep(y, 0, N) rep(x, 0, N) if (init[y][x] != board[y][x]) cnt++;

    printf("%d %d\n", point, cnt);

    rep(y, 0, N) rep(x, 0, N) if (init[y][x] != board[y][x]) {
        printf("%c %d %d\n", board[y][x], y + 1, x + 1);
    }
}
//-----------------------------------------------------------------------------------
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int T; cin >> T;
    rep(t, 1, T + 1) {
        cin >> N >> M;
        rep(i, 0, M) cin >> A[i] >> B[i] >> C[i];
        printf("Case #%d: ", t);
        sol();
    }
}

https://code.google.com/codejam/contest/3264486/dashboard#s=a&a=3
この解説の和訳的な解説。あとsatanicさんの解説がくっそ分かりやすい。
satanic0258.hatenablog.com
まず、問題を分割する。

+..
+.o
x..
こういう盤面をoが+とxの重なり合いだと考え
... +..
..x +.+
x.. ...
このように分割し、それぞれを別々に最適に解いて
.x. +..
..x +.+
x.. +..
その結果を合成して答えとする
+x.
+.o
o..

はーという感じ。

まず、xの配置だが、これはおけるなら置くを繰り返して貪欲にやっていけば良い(solveX関数)

+の配置では、SmallとLargeで方針が違う。
Small解(solvePlusSmall関数)
盤面の配列をB[y][x]とすると、B[0][0]~B[0][N-1]とB[N-1][1]~B[N-1][N-2]に+を置く。
すると最適な配置となる。
理由としては、今回の配置は右上がりの斜めと左上がりの斜めをどの+で繋ぐかという二部最大マッチング問題として考えることができ、上の方法の配置だと2(N-1)個配置ができ、これは最大マッチングになっていることが容易に分かる。

Large解(solvePlusLarge関数)
二部最大マッチングを解くのもいいが、最適な貪欲解が存在する。
この部分はsatanicさんのブログを見るのが分かりやすく、恐らく本家の解説もこれと同じ貪欲だと思う。
tanakhさんの貪欲もそう?

プロのツイート。すげぇわ