Google Code Jam 2021 Qualification Round

Google Code Jam 2021 Qualification Round の各問題で部分点を取って予選通過する方法を解説する。これだけで37点取れるので、予選通過に必要な30点を越え、Round 1A に進める。

Reversort

長さ $n$ の配列 $L$ が与えられたときに、各 $i=1,\ldots, n - 1$ に対して $L _ {j}$ が最小となるような $ j $ を見つけて $L$ の $i$ から $j$ 番目までをひっくり返すという操作を繰り返すことで、$L$ をソートできる。ひっくり返すときにその長さ分のコストがかかると考えて、与えられた配列をソートするのにかかるコストを求める。

愚直にソートした。

提出(7点)

def reversort(lst):
    n = len(lst)
    cnt = 0
    for i in range(n - 1):
        j = min(range(i, n), key=lambda j: lst[j])
        cnt += j - i + 1
        lst[i : j + 1] = lst[i : j + 1][::-1]
    return cnt


t = int(input())
for i in range(t):
    input()
    (*lst,) = map(int, input().split())
    cnt = reversort(lst)
    print(f"Case #{i+1}: {cnt}")

Moons and Umbrellas

C,J,? からなる文字列が与えられる。? には C か J のどちらかを入れてよいが、文字列の中に登場する "CJ" と "JC" にはそれぞれ $X,\ Y$ のコストがかかるとき、コストの合計の最小値を求める。

すべての?の部分にCとJのどちらを入れるかでbit全探索した。

提出(5点)

def cost(a):
    global x
    global y
    cnt01, cnt10 = 0, 0
    for i in range(len(a) - 1):
        if a[i] == 0 and a[i + 1] == 1:
            cnt01 += 1
        if a[i] == 1 and a[i + 1] == 0:
            cnt10 += 1
    return cnt01 * x + cnt10 * y


def full_search(a):
    idx = []
    for i, c in enumerate(a):
        if a[i] == -1:
            idx.append(i)
    n = len(idx)
    min_cost = 10 ** 20
    for s in range(1 << n):
        b = a[:]
        for i in range(n):
            if (1 << i) & s:
                b[idx[i]] = 1
            else:
                b[idx[i]] = 0
        min_cost = min(min_cost, cost(b))
    return min_cost


for case in range(int(input())):
    x, y, string = input().split()
    x, y = int(x), int(y)
    a = []
    for c in string:
        if c == "C":
            a.append(0)
        if c == "J":
            a.append(1)
        if c == "?":
            a.append(-1)
    ans = full_search(a)
    print(f"Case #{case+1}: {ans}")

Reversort Engineering

さっきのReversortの問題で、長さ $n$ でコスト $c$ がかかる配列を $1$ つ構築し、なければ IMPOSSIBLE と答える。

長さ $n$ の順列を全探索した。

提出 (7点)

from itertools import permutations


def reversort_cost(a):
    n = len(a)
    cost = 0
    for i in range(n - 1):
        j = min(range(i, n), key=lambda j: a[j])
        cost += j - i + 1
        a[i : j + 1] = a[i : j + 1][::-1]
    return cost


def full_search(n, c):
    for a in permutations(range(1, n + 1)):
        if reversort_cost(list(a)) == c:
            return " ".join([str(x) for x in a])
    return "IMPOSSIBLE"


for case in range(int(input())):
    n, c = map(int, input().split())
    ans = full_search(n, c)
    print(f"Case #{case+1}: {ans}")

Median Sort

いわゆるインタラクティブ問題。中身のわからない配列の長さだけ与えられる。こちら側からは好きなインデックスを3つ選んで質問すると、そのうちのどれが中央値になるかを教えてくれる。最終的にソートされたインデックスを答える。

すべての組合せを質問して、愚直にソートした。

提出(7点)

from itertools import combinations

t, n, q = map(int, input().split())
for _ in range(t):
    ans = list(range(1, n + 1))
    for i, j, k in combinations(range(n), 3):
        print(ans[i], ans[j], ans[k], flush=True)
        res = int(input())
        if res == ans[i]:
            ans[i], ans[j] = ans[j], ans[i]
        if res == ans[k]:
            ans[j], ans[k] = ans[k], ans[j]
    print(*ans, flush=True)
    res = int(input())
    if res == -1:
        exit()

Cheating Detection

100人のプレイヤーが10000個の問題を解き、その正解不正解の結果が与えられる。100人のうち、1人だけ1/2の確率で不正をし、その問題に必ず正解できるとき、誰が不正をしたかを特定する。

正解数に対して難問(正解率が1/2以下だった問題)を解けた割合が一番多かった者を不正者と決めつけた。

提出(11点)

m = 10000
n = 100
t = int(input())
p = int(input())
for case in range(t):
    x = []
    for _ in range(n):
        x.append([int(c) for c in input()])
    cnt = [0] * m
    for i in range(n):
        for j in range(m):
            if x[i][j]:
                cnt[j] += 1
    total = [0] * n
    difficult = [0] * n
    for i in range(n):
        for j in range(m):
            if x[i][j]:
                total[i] += 1
                if cnt[j] < n // 2:
                    difficult[i] += 1
    ans = max(range(n), key=lambda i: difficult[i] / total[i])
    print(f"Case #{case+1}: {ans+1}")