Google Code Jam Qualification Round 2021

Google Code Jamはちょっと変わった問題があって面白い。全問解いて396位。

他は、まあ公式解説そのままだけど、最後の問題でほぼ100%正解できるのは自慢なので読んでほしい。

Reversort

選択ソートで、A[i]とA[j]をスワップする代わりに、A[i..j]を反転させることにしたと。なんでそんなことをするの？　で、案の定コストが掛かる。A[i..j]の反転にはj-i+1。そのコストの合計を求めよという問題。A[i..i]の反転（？）でもコストが1かかる。ただし、最後のA[N]は処理しない。というのがちょっと変則的。制約はN<=10なので、素直に実装するだけ。

A.py

T = int(input())
for t in range(T):
  N = int(input())
  L = list(map(int, input().split()))
  ans = 0
  for i in range(N-1):
    j = i
    for k in range(i+1, N):
      if L[k]<L[j]:
        j = k
    L[i:j+1] = L[i:j+1][::-1]
    ans += j-i+1
  print("Case #%d: %d"%(t+1, ans))

Moons and Umbrellas

CJ?CC?のような文字列が与えられ、?をCかJに書き換える。CJが出現するとXのコストが、JCが出現するとYのコストが掛かる。コストの合計の最小値は？　1個前の文字ごとにコストを覚えておいてのDP。

最後のHidden Verdict以外はコストが正。正でも負でもやることは変わらないと思ったけど、公式解説を見たら、Visible Verdictは初手?を全部消してCJとJCを数えるだけだった。なるほど。

B.py

T = int(input())
for t in range(T):
  X, Y, S = input().split()
  X = int(X)
  Y = int(Y)
  oo = 1000000
  C = [oo]*len(S)
  J = [oo]*len(S)
  if S[0]!="J":
    C[0] = 0
  if S[0]!="C":
    J[0] = 0
  for i in range(1, len(S)):
    if S[i]!="J":
      C[i] = min(C[i-1], J[i-1]+Y)
    if S[i]!="C":
      J[i] = min(J[i-1], C[i-1]+X)
  print("Case #%d: %d"%(t+1, min(C[-1], J[-1])))

Reversort Engineering

1問目とは逆に、コストが与えられてそのコストになるような文字列を返せという問題。後ろから順番に処理していけば、末尾から2番目では1か2のコストを選べる、末尾から3番目では1から3のコストを選べる……ということで、コストがN-1以上、2+3+...+N以下ならば達成可能。

C.py

T = int(input())
for t in range(T):
  N, C = map(int, input().split())
  C -= N-1
  if 0<=C<=(N-1)*N//2:
    A = list(range(1, N+1))
    for i in range(N-2, -1, -1):
      c = min(N-1-i, C)
      C -= c
      A[i:i+c+1] = A[i:i+c+1][::-1]
    ans = " ".join(map(str, A))
  else:
    ans = "IMPOSSIBLE"
  print("Case #%d: %s"%(t+1, ans))

Median Sort

インタラクティブ問題。配列の要素を3個指定すると、そのうちどれが中央値かを返してくる。それを使って、配列をソートしろという問題。ただし、この条件では昇順か降順かは知りようがないので、どちらでも良い。難しいテストセットほど使える問い合わせ回数が減る。

情報量の概念が重要である。最後のテストセットでは、N=50で、テストケース1個あたりの問い合わせ回数が170回。長さ50の配列は反転したものを同一視して、$\frac{N!}{2}\fallingdotseq 1.52\times 10^{64}$個ある。一方、$2^{170}\fallingdotseq 1.5\times 10^{51}$。つまり、1回の問い合わせでYES/NOの1bitの情報しか使わないようなアルゴリズムでは無理ということ。中央値の問い合わせでは3通りの答えが返ってくる。これをフルに活用できるならば$\frac{\log(N!/2)}{\log(3)}\fallingdotseq 135$回の問い合わせで足りるということ。けっこうカツカツ。

ある要素aとbについてa<bであることが分かっているならば、要素cを一緒に問い合わせることで、c<a、a<c<b、b<cのいずれであるかが分かる。これを使ってクイックソートの3分割版をする。

分割したものを単純にソートしてしまうと、外側と昇順・降順が揃わなくなってしまうので、例えばa超過b未満の部分をソートするときにはaを渡すようにした。これだとa未満の部分にaを渡すときに、素直に実装すると別処理になってしまって面倒。aを渡してソート結果を反転することで実装量を減らした。

D.py

import sys

T, N, Q = map(int, input().split())

def query(*args):
  print(*args)
  sys.stdout.flush()
  return int(input())

def f(l, V):
  if len(V)<=1:
    return V
  a = query(l, V[0], V[1])
  if a==V[0]:
    b = V[1]
  else:
    b = V[0]
  X, Y, Z = [], [], []
  for v in V[2:]:
    m = query(a, b, v)
    if m==a:
      X += [v]
    elif m==v:
      Y += [v]
    elif m==b:
      Z += [v]
  return f(a, X)[::-1] + [a] + f(a, Y) + [b] + f(b, Z)

for t in range(T):
  a = query(1, 2, 3)
  b = a%3+1
  X, Y, Z = [(a+1)%3+1], [], []
  for i in range(4, N+1):
    m = query(a, b, i)
    if m==a:
      X += [i]
    elif m==i:
      Y += [i]
    elif m==b:
      Z += [i]
  ans = f(a, X)[::-1] + [a] + f(a, Y) + [b] + f(b, Z)
  assert query(*ans)==1

Cheating Detection

プレイヤー100人と問題10,000問があって、それぞれに強さが決まっている。プレイヤーと問題の強さの差分に応じた確率で正解、不正解が決まる。プレイヤーの中には1人チーターがいて、そいつは1/2の確率で必ず正解する。「チーターは誰？」という問題。面白いのが、50個のテストケースのうちP%に正解すれば正解となること。難しいほうのテストケースではP=86。つまり、43個のテストケースに正解すれば良い。

「難しい問題に正解しているやつがチーターでしょ？」とか、「チーターは正解数のわりには簡単な問題も不正解になるはず」とかで80%くらいではいけたものの、微妙に足りなかった。

難しい問題にも程度があり、とても難しい問題に正解しているほうが、ちょっと難しい問題に正解しているよりも、チーターっぽさが高いはず。簡単な問題も同様。この辺の話は情報量っぽい。ということで、情報量を求めてみた。要は、チーターは正解／不正解が不自然になる。不自然な結果というのは情報量が多いということ。

各プレイヤーに対して、問題の強さは一様ランダムなので、プレイヤーの正答率から強さを推測できる。問題の強さも同様。強さが推測できれば、あるプレイヤーがある問題に正解する確率が分かる。確率が分かれば、正解／不正解でどれだけの情報量が得られたかも計算できる。プレイヤーごとに、正答率を横軸に、問題1問あたりの情報量を縦軸にプロットするとこうなる。

あからさまに怪しいやつがいますねぇ。

まあ、これはわかりやすい例で、チーターはたいてい正解率が高く、正解率が高いと分かりづらいのだけど。サンプル入力だとこんな感じ。右端がチーター。

ということで、この上に凸の曲線部分を除いてやる。この曲線はエントロピー関数である。そして一番値が高い人がチーター。

公式解説の締めは、

Using this latest technique can get a solution above 90% accuracy.

だけど、ランダムに生成した1000ケースで全問正解できた

E.cpp

# include <iostream>
# include <vector>
# include <string>
# include <cmath>
using namespace std;

double f(double x)
{
    return 1/(1+exp(-x));
}

double F(double x)
{
    return -log(1-f(x));
}

double skill(double p)
{
    double l = -3.;
    double r = 3.;
    for (int i=0; i<100; i++)
    {
        double m = (l+r)*.5;
        //  (1/6)∫[-3<=x<=3](f(m-x))
        //  = (1/6)(-F(m-x)[-3<=x<=3])
        //  = (1/6)(-F(m-3)+F(m+3))
        ((-F(m-3)+F(m+3))/6<p ? l : r) = m;
    }
    return l;
}

int main()
{
    int T;
    cin>>T;
    int P;
    cin>>P;

    for (int t=1; t<=T; t++)
    {
        vector<vector<int>> A(100, vector<int>(10000));
        for (int i=0; i<100; i++)
        {
            string s;
            cin>>s;
            for (int j=0; j<10000; j++)
                A[i][j] = s[j]-'0';
        }

        vector<double> S(100);
        for (int i=0; i<100; i++)
        {
            int s = 0;
            for (int j=0; j<10000; j++)
                s += A[i][j];
            S[i] = skill(s/10000.);
        }

        vector<double> Q(10000);
        for (int i=0; i<10000; i++)
        {
            int s = 0;
            for (int j=0; j<100; j++)
                s += A[j][i];
            Q[i] = -skill(s/100.);
        }

        vector<double> X(100);
        for (int i=0; i<100; i++)
        {
            for (int j=0; j<10000; j++)
                if (A[i][j]==0)
                    X[i] += -log(1-f(S[i]-Q[j]));
                else
                    X[i] += -log(f(S[i]-Q[j]));
            int s = 0;
            for (int j=0; j<10000; j++)
                s += A[i][j];
            double p = s/10000.;
            X[i] = X[i]/10000 - (-p*log(p)-(1-p)*log(1-p));
        }

        int ans = 0;
        for (int i=1; i<100; i++)
            if (X[i]>X[ans])
                ans = i;
        ans++;

        cout<<"Case #"<<t<<": "<<ans<<endl;
    }
}