mayoko’s diary

プロコンとかいろいろ。

GCJ Qualification Round 2016 Problem D. Fractiles

問題

Dashboard - Qualification Round 2016 - Google Code Jam

'G', 'L' のみで構成された長さ K の文字列 original を C 回操作する。
文字列 s を操作するときは,

  • 'G' -> K 個の 'G' が連なったものに変換
  • 'L' -> original に変換

と操作する(なので C 回操作すると K^C 文字の文字列になる)。

今, C 回操作した後の文字列のある地点 s[index] を最高 S 回だけ調べることが出来る。最初の文字列がどのような文字列であっても, original に少なくともひとつの 'G' があったかを判定できるか。
判定できる場合は, 調べるべき index のリストを返す。

解法

実は一回の調査で original の C 個の文字を調べることが出来ます。

というのは,

  • i*K^(C-1) -> i 番目の文字がわかる
  • a*K^(C-1) + j*K^(C-2) -> j 番目の文字がわかる(a は任意の整数)

...

となっているので, 例えば 0, 1, 2, ..., C-1 文字目がそれぞれどうなっているのかを調べたければ,
0*K^(C-1) + 1*K^(C-2) + 2*K^(C-3) + ... + (C-1)*1 番目の index を調べれば良いです。

イメージとしては, K 分木で,

  • 頂点が 'G' -> それ以下の頂点は全部 'G'
  • 頂点が 'L' -> 下に original が続く

というのを考えるとわかりやすいかもしれません。

void solve(int K, int C, int S) {
    if (C*S < K) {
        cout << "IMPOSSIBLE" << endl;
        return;
    }
    vector<ll> ans;
    for (int i = 0; i < K; i += C) {
        ll t = 0;
        for (int j = 0; j < C; j++) {
            if (i+j >= K) break;
            t = t*K+(i+j);
        }
        ans.push_back(t+1);
    }
    int sz = ans.size();
    for (int i = 0; i < sz; i++) {
        cout << ans[i];
        if (i < sz-1) cout << " ";
    }
    cout << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        int K, C, S;
        cin >> K >> C >> S;
        cout << "Case #" << t << ": " ;
        solve(K, C, S);
    }
    return 0;
}