概要
こんにちは。Shunと申します。
先日参加したGoogle Code Jam 2019 Round2ですが、残念ながら1193位で惜しくも敗退となってしまいました…
1問目でdouble型の誤差のせいでWEを出し続け1時間取られ、ようやくそれに気づき分数を実装してsmallを突破したらプログラムの些細なミスでlargeはRuntime Errorだったという有様。時間を取られたせいで3問目のsmallも解けず。
1問目のlargeか3問目のsmallどっちか解けていれば1000位以内は確実だっただけに悔しいです。
マジでTシャツ欲しかったです…悔しいです。来年こそはTシャツを目指します。
今回完答できた2問目「Pottery Lottery」はGCJ特有のInteractive問題で、ゲームの最適戦略を求める問題です。普通の競技プログラミング問題とはかなり毛色の違う問題ですが、個人的にはとても楽しめましたので、解説したいと思います。
問題
原文
The Pottery Palace is going to run a lottery featuring some valuable vases by the artist Cody-Jamal. The lottery works as follows:
100 people get to play in the lottery. Each player has a unique number between 1 and 100, and is given a single token with that number.
There are 20 empty clay vases on a table, numbered 1 through 20. The vases have narrow openings that are large enough to accept a token, but small enough that players cannot look inside to see the contents.
On the i-th day of the lottery, the player with token number i chooses a vase and puts their token in that vase. Since the vases are all identical (apart from their labels), every player will choose one uniformly at random and independently of all other players' choices.
On day 100, after player number 100 has inserted their token, the organizers shake the vases to determine how many tokens are inside each one. If there is exactly one vase that has fewer tokens than any other vase, then that one is the "winning vase". The organizers then pour out all of the tokens in that vase, and every player whose number is written on one of those poured-out tokens wins a vase! If multiple vases have the same minimal amount of tokens, nobody wins anything.
You have been hired to test the security of the lottery, and you will participate in some trial runs. The company will always assign you the number 100 — that is, you replace player 100.
You have found some ways to tamper with the lottery at night, but security is tight, so you can only do so much! Specifically, after each of the first 99 days of the lottery, you may do exactly one of the following:
・ forge a token with the player number of your choice (between 1 and 100, inclusive), and add it to a vase of your choice. You are a very good forger: if there is a winning vase, any forged tokens in that vase will cause the players with those numbers to win (with one exception; see below).
・ use a special camera to see the numbers on all of the tokens in one vase of your choice
You may perform different actions on different nights, and you may choose dynamically: you do not need to decide on all of your actions in advance.
On the 100th day, it is your turn to insert your token into a vase of your choice (you do not need to choose uniformly at random). You cannot perform any other actions on that day.
You know that if there is a winning vase with more than one token for the same player, it will be obvious that cheating has occurred and nobody will win. However, it does not matter if other vases contain more than one token for the same player because the organizers never see those tokens.
Your goal is to be a winner in at least 90% of the test cases.
意訳
100人の参加者と、20個の花瓶で100日間かけてゲームを行う。
参加者には1～100の番号が割り振られ、n日目にn番目の参加者はn番の書かれた札を好きな花瓶に入れる。
これを100日目まで繰り返し、札の数が最小の花瓶の中の札を確認し、その番号の参加者全員が勝者となる。
ただし、札の数が（同率で）最小の花瓶が2つ以上ある場合、全員が敗者となる。
また、後述するチート行為により、札の数が最小の花瓶の中に、同じ番号の札（偽造札）が重複していた場合も、全員が敗者になる。
100番目の参加者であるあなたはチート行為が使用でき、1～99日目の夜に以下の行動のうちいずれかを実行できる。
- 1～100の中の好きな番号の札を偽造し、好きな花瓶に入れる。
- 20個の花瓶のうちどれか1つの花瓶の中身を覗き、札の数と番号を確認する。
100日目の行動は「100番の札を好きな花瓶に入れる」で固定である。
勝率が90%以上の（用意されたテストケース250個に対し225回以上勝てる）戦略を求めよ。
制約
T = 250.
Time limit (for the entire test set): 40 seconds.
Memory limit: 1GB.
解答
この問題は複数の正解があります。ここで紹介するのはあくまで一つの戦略となります。Googleの模範戦略は98%近いwin rateを出すそうですが、私の戦略はもっと低いです。ネットを見る限りこれ以外にもさまざまな戦略がありそうです。
Googleの解説にもあるように、この問題では最初に以下2つの「基本戦略」に気付けるかどうかがカギになります。
- すべての花瓶に100番の札を1枚ずついれれば、「最小の花瓶が2つ以上存在する」場合にならない限り確実に勝てる。
- ある1つの花瓶を勝たせるために、それ以外の花瓶に均等に偽造札を配分する。
少しシミュレーションしてみれば分かるのですが、上記2つの基本戦略は勝率50%程度となり、解答にはなりません。
1の戦略が失敗する理由は「札の数が最小の花瓶が2つ以上存在する」可能性が50%近く存在するためです。
2の戦略が失敗する理由は「札の偏りのせいで勝たせたい花瓶が勝ってくれない」可能性が50%近く存在するためです。
また、上記2戦略は「花瓶を覗く」行動を使用していないため、「花瓶を覗く」行動を生かした戦略を考えれば良いのではという推測が立てられます。
ということで、上記2つの「ハイブリッド戦略」を用います。
具体的には以下のような戦略となります。
- 1～20日目：100番の札を全ての花瓶に1枚ずつ入れる。
- 21～x-1日目：何もしない。
- x日目～x+19日目：20個の花瓶の中身を覗き、数を覚えておく。
- x+20日目～99日目：覗いた20個の花瓶のうち札の数が最小のものを「勝たせたい花瓶」とする（同率の場合は後で覗いた花瓶とする。なぜなら、先に覗いた花瓶は途中で札の数が増えている可能性が高いため。）99日目まで使って、勝たせたい花瓶以外の花瓶について、「札の数の最小値」を最大にするように偽造札を割り振る。
- 100日目：勝たせたい花瓶以外の任意の花瓶に100番の札をいれる。（勝たせたい花瓶に入れてしまうと、札1枚分不利なので、別の花瓶に入れる。）
上記の方法でテストコードを組んで最適なxの値をシミュレーションで求めました。結果x=65が勝率最大となり、91%程度でした。
21～x-1日目のパスが明らかに無駄なので、ここでGoogleの戦略である「勝たせたい花瓶を5個に絞る」ように札を入れればもっと勝率は上がる気がします。
ちなみに、Google模範戦略も私と別の形の「ハイブリッド戦略」になっています。
どちらの解答も、「勝たせたい花瓶」を作るために投じる札の数を減らしてでも、「同率で札の数が最小になりそうな花瓶」を的確に潰せるようにした方が勝てる、という考えに基づいています。
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;
public class Solution {
private static FastScanner sc = new FastScanner();
private static boolean DEBUG_FLG = false;
public static void main(String[] args) {
int T = sc.nextInt();
for(int t=1; t<=T; t++) {
int winneridx = -1;
double[] scope = new double[20];
int scopeDay = 65;
while(true) {
int d = sc.nextInt();
if(d == -1) {
//return;
}
if(d == 100) {
int idx = winneridx + 2;
if(idx == 21) idx = 1;
System.out.println(idx + " 100");
System.out.flush();
break;
}
if(d <= 20) {
System.out.println(d + " 100");
System.out.flush();
} else if(d > 20 && d < scopeDay) {
System.out.println("1 0");
System.out.flush();
int tokennum = sc.nextInt();
for(int i=0; i<tokennum; i++) {
int tmp = sc.nextInt();
}
} else if(d >= scopeDay && d < scopeDay + 20) {
System.out.println((d - scopeDay + 1) + " 0");
System.out.flush();
int tokennum = sc.nextInt();
for(int i=0; i<tokennum; i++) {
int tmp = sc.nextInt();
}
scope[d - scopeDay] = tokennum + ((double)(19 - (d - scopeDay)) / (double)20);
}
if(d == scopeDay + 20) {
double min = 1000;
for(int i=0; i<20; i++) {
if(scope[i] < min) {
min = scope[i];
winneridx = i;
}
}
}
if(d >= scopeDay + 20) {
double min = 1000;
int idx = 0;
for(int i=0; i<20; i++) {
if(i == winneridx) continue;
if(scope[i] < min) {
min = scope[i];
idx = i;
}
}
scope[idx]++;
System.out.println((idx+1) + " " + d);
System.out.flush();
}
}
}
}
static void debug(long... args) {
if(!DEBUG_FLG) return;
boolean flg = false;
for(long s : args) {
if(flg) System.out.print(" ");
flg = true;
System.out.print(s);
}
System.out.println();
}
static class FastScanner {
private final InputStream in = System.in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
private boolean hasNextByte() {
if(ptr < buflen) {
return true;
} else {
ptr = 0;
try {
buflen = in.read(buffer);
} catch(IOException e) {
e.printStackTrace();
}
if(buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
public boolean hasNext() { skipUnprintable(); return hasNextByte();}
public String next() {
if (!hasNext()) throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while(isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public long nextLong() {
return Long.parseLong(next());
}
public int nextInt(){
return Integer.parseInt(next());
}
public double nextDouble(){
return Double.parseDouble(next());
}
}
}
そのうち、データサイエンティストになるに向けての勉強方針とか語りたいです。
Atcoder、ABCが~2000までレート対象になったのはうれしいんですが、いかんせんジャッジサーバ重すぎる・・・とりあえず全完はできましたので余裕があれば解説上げます。