Google Code Jam 2022 予選最終問題解説

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を繰り返して、辺の数を数えあげて、その平均をもとに全体を推測することができます。

```Python
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になってしまいます。おそらくここで、多くの人が悩んだものと思います。

ローカルテスト結果

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156600/ff7b479a-b520-c37f-f8c3-25144d846d77.png)

提出ジャッジ結果

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156600/c2c6f29b-9ebf-469e-8f38-fd79ad10f11e.png)

# 3. コーナーケースを考えてローカルテスターを修正

本番ジャッジにおいて、ナイーブな解法でWAになるような、コーナーケースが多く含まれているものと思います。どのようなコーナーケースが考えられるでしょうか。

少し考えると、少数の根となる頂点に辺が集中しているケースが考えられます。このケースだと、ナイーブな解法では、根となる頂点（辺数が際立って多い）に遭遇する確率が少ないため、結果として、全辺数の予想が少なすぎて、WAしてしまうようです。

Python使いには嬉しいことに、ローカルテスターはPythonで提供されていますので、ローカルテスターを改造して、コーナーケースを作ってみましょう。

ローカルテスターの73行目以降を以下のように修正します。

```Python
    # 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が少し混ざるようになりました。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156600/416ff2d0-6579-3b9c-e3ee-1a8295f73c28.png)

# 4. ローカルテスターでACが出るように解答を修正

あとは、ローカルテスターでACが出るように解答を修正するだけです。

方針としては以下です。

+ 辺が集中する頂点をなるべくクエリーで捕捉できるようにする
+ 辺が集中する頂点は「外れ値」なので、未観測の頂点の辺数推定の際には除いて「標準値」を使う

実装は以下です。

```Python
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となりました。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156600/9700321e-f42f-65f8-c580-3311256c3c20.png)

それではジャッジに提出します。ドキドキ・・・。

なんと、WAになってしまいました。
どうも、外れ値をどのくらい除くかの調整が微妙なようです。ペナルティはありますが、何度でもジャッジ提出できるため、試行錯誤してみましょう。

```Python
    normal_passages = passages[:-(len(passages) // 8)]
```

とすることで、ACできました。この係数を自動で求めることも、がんばればできるかもしれません。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156600/5beacfc7-9fdb-98b7-41f8-1bfa9c68baaa.png)