Google Code Jam 2019 - Qualification Round

4/6(土)08:00 - 4/7(日)11:00
Qualに限って相談OKなので、有志4人で集まって電源wifi完備なカラオケルームを借りて参加*1

全員予選通過ライン（30点）は超えられたので目的は果たせたかと

会場でD-smallまで解いて（提出は帰宅後）
その後D-largeも解いて終了。

終了後ジャッジでLargeも全て通って100点満点

次はRound 1でお会いしましょう。

【参考資料】当日のセットリスト（誰がどれを歌ったかは秘匿）
docs.google.com

A - Foregone Solution (6 + 10 + 1)

• Largeがとか言ってるので
• 数値としてではなく文字列として読み込んで、桁ごとにAとBに分解する感じで構築
• k=4の桁は3+1、それ以外はk+0で
• （必ず4が一度は含まれるので小さい方も0になることはない）

→AC(s1,s2; L)

void solve(string& s){
    int L = s.size();
    stringstream ss1, ss2;
    bool stand = false;
    rep(i,L){
        int n = s[i] - '0', a = n, b = 0;
        if (a == 4) { a = 3; b = 1; }
        ss1 << a;
        if (b) stand = true;
        if (stand) {
            ss2 << b;
        }
    }
    if (!stand) ss2 << 0;
    cout << ss1.str() << " " << ss2.str() << endl;
}

int main() {
    int N; cin >> N;
    rep1(z,N) {
        string s; cin >> s;
        printf("Case #%d: ", z);
        solve(s);
    }
    return 0;
}

B - You Can Go Your Own Way (5 + 9 + 10)

• EをSに、SをEに置換すれば対角線＼でフリップした感じに出来るのでは
• ある点にたどり着く方法はいくつもあるが、手数は一定なので鏡像が同じ道をたどることはありえない

→AC(s1,s2; L)

void solve(int N, string& s) {
    int L = s.size();
    rep(i,L){
        switch (s[i]) {
            case 'S': putchar('E'); break;
            case 'E': putchar('S'); break;
            default: break;
        }
    }
    putchar('\n');
}

int main() {
    int T; cin >> T;
    rep1(z,T){
        int N; cin >> N;
        string s; cin >> s;
        printf("Case #%d: ", z);
        solve(N, s);
    }
    return 0;
}

C - Cryptopangrams (10 + 15)

• 高々100個の数を総当たりでgcd
  • big integerを使いたいのでpythonで
• 共通の素数を持っていればgcd≠1になるので、それを利用して2つの素数の積に分解できる
  • 出現する素数（26個あるはず）を昇順に並べ替え、小さい方からそれぞれA〜Zとする
• 暗号文は2つの素数のペアのリストになるので、
  • 最初のペアのどちらを左端にしたら辻褄が合うか（両方やってみる）
• で文字列を再構築

→AC(s; L)

# -*- encoding: utf-8 -*-
import sys
from fractions import gcd  # python<=3.4

def sub(pairs, start):
    L = len(pairs)
    ans = [start]
    for a, b in pairs:
        if a == start:
            next = b
        elif b == start:
            next = a
        else:
            return None
        ans.append(next)
        start = next
    return ans

def solve(N,L,s):
    assert L == len(s)
    tmp = set()
    for i in range(L-1):
        for j in range(i+1, L):
            if s[i] == s[j]:
                continue
            g = gcd(s[i], s[j])
            if g == 1:
                continue
            a = s[i] / g
            b = s[j] / g
            tmp.add(g)
            if a > 1:
                tmp.add(a)
            if b > 1:
                tmp.add(b)

    primes = sorted(list(tmp))

    dct = { n: chr(0x41+i) for i,n in enumerate(primes) }

    pairs = []
    for n in s:
        for p in primes:
            if n % p == 0:
                q = n / p
                pairs.append((p,q))
                break
            else:
                continue
    assert len(s) == len(pairs)
    m0 = sub(pairs, pairs[0][0])
    m1 = sub(pairs, pairs[0][1])
    msg = m0 or m1
    return ''.join([dct[p] for p in msg])

T = int(raw_input())
for i in range(T):
    N, L = map(int, raw_input().rstrip().split())
    s = map(long, raw_input().rstrip().split())
    print 'Case #%d: %s' % (1+i, solve(N,L,s))

D - Dat bae (14 + 20)

F=10の場合

• 10回使って、子機それぞれが0〜1023を示すようにする
• 10回の返答を0〜1023の数に変換し、出現しなかった数を答える

とりあえずF=5のときは嘘解答を投げるようにして
→AC(s; L)

vi solve10(int N, int B, int F) {
    assert(F >= 10);

    int R = N - B;
    vi alive(R, 0);
    for (int i=0; i<10; ++i) {
        rep(p,N) {
            // m[p] = (p & b) ? 1 : 0;
            int bit = (p >> i) & 1;
            putchar('0' + bit);
        }
        putchar('\n');
        fflush(stdout);

        string res; cin >> res;
        assert(res.size() == R);
        rep(j,R) {
            alive[j] |= ((res[j] - '0') << i);
        }
    }
    set<int> alive_set(ALL(alive));
    vi ans;
    rep(i,N) {
        if (!found(alive_set, i)) ans.pb(i);
    }
    return move(ans);
}

vi solve5(int N, int B, int F) {
    // uso
    rep(i,F){
        rep(p,N){
            putchar('0');
        }
        putchar('\n');
        fflush(stdout);

        string res; cin >> res;
        assert(res.size() == R);
    }

    vi ans(B);
    rep(i,B) ans[i] = i;
    return move(ans);
}

int main() {
    int T; cin >> T;
    rep(z,T){
        int N,B,F; cin >> N >> B >> F;
        vi ans;
        if (F >= 10) {
            ans = solve10(N,B,F);
        } else {
            ans = solve5(N,B,F);
        }
        assert(ans.size() == B);
        rep(i,B) {
            printf("%d%c", ans[i], (i==B-1)?'\n':' ');
            fflush(stdout);
        }
        int verdict; cin >> verdict;
        if (verdict == -1) break;
    }
    return 0;
}

帰宅後

F=5の場合

• 5回使って、子機それぞれが0〜31を示すようにする（というか0〜31しか作れない）
  • 0 1 2 3 ... 29 30 31 0 1 2 3 ... 29 30 31 0 1 2 3 ... のようになる
• 5回の返答を0〜31の数に変換し、出現しなかった数を答える

→先日のyukicoderエイプリルフールコンテストのF問題「怪文書」の方式

• • 出現しない個数は高々15個なので、どこが欠けてるか知ることができそう

→AC(s1)

vi solve5(int N, int B, int F) {
    assert(F >= 5);

    int R = N - B;
    vi alive(R, 0);
    for (int i=0; i<5; ++i) {
        rep(p,N) {
            int pid = p % 32;
            int bit = (pid >> i) & 1;
            putchar('0' + bit);
        }
        putchar('\n');
        fflush(stdout);

        string res; cin >> res;
        assert(res.size() == R);
        rep(j,R) {
            alive[j] |= ((res[j] - '0') << i);
        }
    }

    int ofs = 0;
    rep1(i,R-1) {
        alive[i] += ofs;
        if (alive[i] < alive[i-1]) {
            ofs += 32;
            alive[i] += 32;
        }
    }

    set<int> alive_set(ALL(alive));
    vi ans;
    rep(i,N) {
        if (!found(alive_set, i)) ans.pb(i);
    }

    return move(ans);
}

int main() {
    int T; cin >> T;
    rep(z,T){
        int N,B,F; cin >> N >> B >> F;

        vi ans = solve5(N,B,F);
        assert(ans.size() == B);
        rep(i,B) {
            printf("%d%c", ans[i], (i==B-1)?'\n':' ');
            fflush(stdout);
        }
        int verdict; cin >> verdict;
        if (verdict == -1) break;
    }
    return 0;
}

F=4でも行けるという話ですね

*1:1AC→1曲歌ったら次の問題に進める