問題 / 公式解説: https://codingcompetitions.withgoogle.com/codejam/round/0000000000051706/0000000000122837

問題概要

"X-day ring" ( $ 1 \leq X \leq 6 $ ) というものがある．X-day ring は X 日ごとにもう 1 つの X-day ring を生成する．例えば 0 日目に 3-day ring が 1 つあったら，3 日目，6 日目の 3-day ring の数はそれぞれ 2 つ，4 つになる．

0日目に存在する 1-day ring, 2-day ring, ..., 6-day ring の数を $ R_1, R_2, \cdots, R_6 $ (ただし $ 1 \leq i \leq 6, 0 \leq R_i \leq 100 $ )を求めよ．ただし，そのために以下の質問を W 回 (Visible では $ W = 6$, Hidden では $ W = 2$) まで行うことができる．

入力: D ( $ 1 \leq D \leq 500 $ )

出力: D 日目に存在する ring の数の総計を $ 2^{63} $ で割ったあまり

解法概要

Hidden の場合，$ W = 2$ なので1回の質問で 6 種類中 3 種類の ring の個数を特定することを考えてみる．

ring の増え方に着目すると，D 日目の i-day ring の個数は $ R_i \times 2^\frac{D}{i} $ の形で表すことができる．また，$ R_i $ の最大値は 10 進数で 100，つまり7bit の値 (1100100) であることから，$ \frac{D}{i-1} - \frac{D}{i} \geq 7 $ となるような D を入力すれば，返ってきた値の $ \frac{D}{i} $ bit 目から 7bit ぶんのみを取り出した値が $ R_i $ である．

63bit を超えた値は $ 2^{63} $ で割ったあまりには影響しないが $ R_i $ を特定する計算には使えなくなってしまうことと， $ \frac{D}{i-1} - \frac{D}{i} \geq 7 $ という条件に注意しながら，$ 1 \leq i \leq 3 $ の $ R_i $ を特定するための質問(私のソースコードでは $ D = 50 $) と $ 4 \leq i \leq 6 $ の $ R_i $ を特定するための質問 (私のソースコードでは $ D = 220 $) の $ R_i $ を特定するための質問を 1 回ずつすれば，2回の質問で全ての種類の ring の個数を特定することができる．

ただし $ R_3 $ を求める時だけ注意が必要である． $ D = 50 $ のとき，

$ i = 1 $ なら $ \frac{D}{i} = 50 $

$ i = 2 $ なら $ \frac{D}{i} = 25 $

$ i = 3 $ なら $ \frac{D}{i} = 16 $

$ i = 4 $ なら $ \frac{D}{i} = 12 $

$ i = 5 $ なら $ \frac{D}{i} = 10 $

$ i = 6 $ なら $ \frac{D}{i} = 8 $

となっている．つまり，ただ 7bit ぶんマスクするだけでは $ R_3 $ を求めることはできない．例えば 16bit 目には $ i = 3, 4, 5 $ のときの $ R_i $ の情報が混ざってしまっているためである．そのため，$ R_3 $ を求める際には，D日目の ring の個数もともとの値から$ R_4 $ のぶんと $ R_5 $ のぶんを引いておく必要がある．

ソースコード

#include <iostream>
#include <vector>

using namespace std;

typedef unsigned long long ull;

const int Q1 = 220;
const int Q2 = 50;

int T, W;

void solve() {
    vector<ull> rings(6, 0);
    ull ret, mask = (1uLL << 7) - 1uLL;
    cout << Q1 << endl;
    cin >> ret;
    for(int i=3;i<6;++i) {
        rings[i] = (ret >> (Q1/(i+1))) & mask;
    }

    cout << Q2 << endl;
    cin >> ret;
    for(int i=0;i<2;++i) {
        rings[i] = (ret >> (Q2/(i+1))) & mask;
    }
    rings[2] = ((ret - (rings[3] << (Q2/4)) - (rings[4] << (Q2/5))) >> (Q2/3)) & mask;

    for(int i=0;i<5;++i) cout << rings[i] << " ";
    cout << rings[5] << endl;
    cin >> ret;
    if(ret == -1) exit(0);
}

int main() {
    cin >> T >> W;
    for(int t=0;t<T;++t) {
        solve();
    }
    
    return 0;
}

所感

$ R_3 $ 以外は比較的すぐわかったけど $ R_3 $ の求め方に気づくまでかなり時間を要してしまった．

NoiminのNoise

Google Code Jam 2019 Round 1B Draupnir

問題概要

解法概要

ソースコード

所感