Google Code Jam（GCJ） 2022 予選参加約3万人中224位（Japan28位）になりましたので、記念に記事を書きました。
世界で394人しか解けなかった！ 最終問題（Twisty Little Passages）の解説をします。しかしながら、最後でパラメータを試行錯誤しているため、解法として合っているかどうかは謎です。
1. 問題概要
連結とは限らないが単独頂点は存在しないグラフ構造において、以下のクエリーをK=8000回まで行うことで、全体の辺数を推定する、インタラクティブ問題です。GCJではインタラクティブ問題の出題が多いようです。
クエリー
- T 数字: 指定した数字の頂点に瞬間移動（Teleport）する。頂点番号と隣接辺数が返る。
- W: ランダムに選定された辺を経由して隣接頂点に移動（Walk）する。頂点番号と隣接辺数が返る。
- E 数字: 最後のクエリーとして辺数の推定値(Estimate)を解答する。テストケースを終了する。
推定値はかなりの幅の誤差を許容するとともに、全体のケースの9割以上を正解することでACとなりますので、マラソン問題のように概算ができればよいはずです。
なお、テストケースは最初に与えられたT回出題されます。このスタイルもGCJ特有です。
2. ナイーブな解法（ローカルテストAC、提出WA）
ナイーブには、クエリー限界までランダムにTransportを繰り返して、辺の数を数えあげて、その平均をもとに全体を推測することができます。
import random
T = int(input())
for t in range(T):
N, K = map(int, input().split())
K = min(N, K)
seen = [False] * N
passages = []
def input_and_record():
R, P = map(int, input().split())
if not seen[R - 1]: # 新たな頂点の場合だけカウント
seen[R - 1] = True
passages.append(P)
input_and_record()
order = [i for i in range(N)]
random.shuffle(order)
for k in range(K):
print(f'T {order[k] + 1}', flush=True)
input_and_record()
ans = sum(passages) * N // (len(passages) * 2)
print(f'E {ans}', flush=True)
しかし、この解法だと、ローカルテストは100ケース全てACするものの、提出するとWAになってしまいます。おそらくここで、多くの人が悩んだものと思います。
ローカルテスト結果
提出ジャッジ結果
3. コーナーケースを考えてローカルテスターを修正
本番ジャッジにおいて、ナイーブな解法でWAになるような、コーナーケースが多く含まれているものと思います。どのようなコーナーケースが考えられるでしょうか。
少し考えると、少数の根となる頂点に辺が集中しているケースが考えられます。このケースだと、ナイーブな解法では、根となる頂点（辺数が際立って多い）に遭遇する確率が少ないため、結果として、全辺数の予想が少なすぎて、WAしてしまうようです。
Python使いには嬉しいことに、ローカルテスターはPythonで提供されていますので、ローカルテスターを改造して、コーナーケースを作ってみましょう。
ローカルテスターの73行目以降を以下のように修正します。
# Construct a graph in adj.
adj = [[] for _ in range(N)]
correct_total_edges = 0
order = [i for i in range(N)]
random.shuffle(order)
# ここからを新規に追加
if case_number < NUM_CASES * 4 // 5: # 全ケースの8割をコーナーケースにする
num_root = case_number // 5 + 1 # 辺が集中する根の数
for root in range(num_root):
for leaf in range(num_root + root * (N - num_root) // num_root,
num_root + (root + 1) * (N - num_root) // num_root):
import sys
v1 = order[root]
v2 = order[leaf]
adj[v1].append(v2)
adj[v2].append(v1)
correct_total_edges += 1
for i in range(N):
assert len(adj[i]) > 0
else:
# ここからは元のコードのままインデントを変更
for i in range(0, N, 2):
v1 = order[i]
v2 = order[i+1]
adj[v1].append(v2)
adj[v2].append(v1)
correct_total_edges += 1
# ここからは元のコードのまま（ゆらぎ要素を加える）
add = random.randint(0, 4*N)
add = random.randint(0, add)
これでローカルテストをしてみると、期待通り、WAが少し混ざるようになりました。
4. ローカルテスターでACが出るように解答を修正
あとは、ローカルテスターでACが出るように解答を修正するだけです。
方針としては以下です。
- 辺が集中する頂点をなるべくクエリーで捕捉できるようにする
- 辺が集中する頂点は「外れ値」なので、未観測の頂点の辺数推定の際には除いて「標準値」を使う
実装は以下です。
import random
T = int(input())
for t in range(T):
N, K = map(int, input().split())
K = min(N, K)
seen = [False] * N
passages = []
def input_and_record():
R, P = map(int, input().split())
if not seen[R - 1]: # 新たな頂点の場合だけカウント
seen[R - 1] = True
passages.append(P)
input_and_record()
order = [i for i in range(N)]
random.shuffle(order)
# ここから変更
for k in range(K // 2):
print(f'T {order[k] + 1}', flush=True)
input_and_record()
print('W', flush=True) # Walkを使うことで辺が集中する頂点への到達性を高める
input_and_record()
passages.sort()
normal_passages = passages[:-(len(passages) // 5)] # 外れ値を除いた「標準点」
# (観測した頂点の辺数合計 + 未観測の頂点は標準点の辺数平均をもとに推定) // 2 が推定値
ans = (sum(passages) + (N - len(passages)) * sum(normal_passages) // len(normal_passages)) // 2
# ここまで変更
print(f'E {ans}', flush=True)
見事、修正したテストツールで、全ケースACとなりました。
それではジャッジに提出します。ドキドキ・・・。
なんと、WAになってしまいました。
どうも、外れ値をどのくらい除くかの調整が微妙なようです。ペナルティはありますが、何度でもジャッジ提出できるため、試行錯誤してみましょう。
normal_passages = passages[:-(len(passages) // 8)]
とすることで、ACできました。この係数を自動で求めることも、がんばればできるかもしれません。
