「Google Code Jam 2021」の Qualification Round に参加しました。「Code Jam」は、Googleが主催する世界的なコーディングコンテストで、Qualification Round は最初の予選です。今年は日本時間の3月26日22時〜28日午前4時にわたり開催され、出題5問から合計30点以上を獲得することで次のラウンドに進出できます。

競プロに挑戦するのは久々でしたが、今回無事に31点を獲得できました。本記事では、解法をまとめます。

f:id:upura:20210328023425j:plain Code Jam - Google’s Coding Competitions

Reversort (7点)

1問目は、データ構造とアルゴリズムで頻出の「ソート」が題材でした。制約の数字も大きくないので、問題文の指示に従って愚直に実装すれば通ります。

T = int(input())
case_id = 0
for test_case in range(T):
    cost = 0
    case_id += 1
    N = int(input())
    L = list(map(int, input().split()))
    for i in range(N - 1):
        min_j = L[i]
        min_j_idx = i
        for j in range(i + 1, N):
            if min_j > L[j]:
                min_j = min(min_j, L[j])
                min_j_idx = j
        cost += (min_j_idx - i + 1)
        L[i: min_j_idx + 1] = L[i: min_j_idx + 1][::-1]
    print(f'Case #{case_id}:', cost)

Moons and Umbrellas (5 + 11 + 1点)

2問目は、文字列に関する話題でした。問題文を読んで、?をどう処理するかを考えるのが肝になります。?が何個連続するのか、?が両端にあるのかなどのパターンを挙げていきながら考えていきました。コストX, Yが0以上の場合には、?が何個連続しようがCもしくはJを連続させることで、部分文字列のコストがXかYに帰着します。

Pythonの場合は文字列の正規表現を用いて次のように実装できます。

import re


T = int(input())
S = [list(input().split()) for i in range(T)]

case_id = 0
for test_case in range(T):
    x, y, s = S[case_id]
    x = int(x)
    y = int(y)
    cost = 0
    cost += (len(re.findall(r'C\?*J', s)) * x)
    cost += (len(re.findall(r'J\?*C', s)) * y)
    case_id += 1
    print(f'Case #{case_id}:', cost)

Reversort Engineering (7 + 11点)

第1問の応用問題です。問題文の制約を見ると、7点のテストケースは総当たりで通せそうです。この時点で24点を積み上げていたため、まずは確実に7点を取りに行きました。

import itertools


def calc_cost(L):
    cost = 0
    for i in range(N - 1):
        min_j = L[i]
        min_j_idx = i
        for j in range(i + 1, N):
            if min_j > L[j]:
                min_j = min(min_j, L[j])
                min_j_idx = j
        cost += (min_j_idx - i + 1)
        L[i: min_j_idx + 1] = L[i: min_j_idx + 1][::-1]
    return cost


def check_list(N, C):
    for candidate in list(itertools.permutations([i + 1 for i in range(N)])):
        candidate_list = list(candidate)
        cost = calc_cost(candidate_list)
        if cost == C:
            ans = [str(c) for c in list(candidate)]
            return ' '.join(ans)
    return 'IMPOSSIBLE'


T = int(input())
case_id = 0
for test_case in range(T):
    case_id += 1
    N, C = list(map(int, input().split()))
    ans = check_list(N, C)
    print(f'Case #{case_id}:', ans)