「Google Code Jam 2021」の Qualification Round に参加しました。「Code Jam」は、Googleが主催する世界的なコーディングコンテストで、Qualification Round は最初の予選です。今年は日本時間の3月26日22時〜28日午前4時にわたり開催され、出題5問から合計30点以上を獲得することで次のラウンドに進出できます。
競プロに挑戦するのは久々でしたが、今回無事に31点を獲得できました。本記事では、解法をまとめます。
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)
おわりに
本記事では「Google Code Jam 2021」の Qualification Round の解法をまとめました。
