問題

Dashboard - Qualification Round 2016 - Google Code Jam

問題概要

gold(G)のタイルとlead(L)のタイルが一直線上に並んだものがある．それはフラクタル構造を持っており，次のような規則を満たしている：

2つのパラメータによってフラクタルは決定づけられる．長さ $K$ のoriginal sequenceと，その複雑さ $C$ である．複雑さ1のものをoriginal sequenceとして，複雑さ $X+1$ のsequenceは複雑さ $X$ のsequenceを基にして再帰的に構成される．sequenceを線形に見ていき:

Lの位置はoriginal sequenceに置換
Gの位置は $K$ 個のGに置換

を繰り返していく(問題文の図を参照)．

いま，このフラクタルを発見したが，汚れていてそれぞれのタイルがgoldなのかleadなのか分からないが， $K$ と $C$ の値についてはわかっている．そして今，タイルを $S$ 枚磨いて，そのタイルがどちらであるかを調べることが出来る．この時，original sequenceがいかなるものであったとしても，そのフラクタル内にgoldが1つでも入っているかどうかが分かるようなタイルの磨き方はあるだろうか？

ある場合には $S$ 枚以下のタイルの磨くべき位置を，そのような方法がない場合にはIMPOSSIBLEと答えよ．

$1 \le K \le 100$
$1 \le C \le 100$
$1 \le K^C \le 10^{18}$

アイデア

smallに関しては $S=K$ なので，はじめから $K$ 枚を調べればもしoriginalの1枚目がLだったなら，original sequence全体を確認できることになるのでそこでGがあるかないかが判定できる．GならGがあるとわかるので問題ない．

問題はlargeである．今回は調べられるタイルの枚数が $1 \le S \le K$ となっている．まず，少なくとも1つはフラクタル内にGが含まれるならば，original sequence内にGが少なくとも1つあるということは対偶(original sequence内が全てLなら，フラクタル内は全てLになる)を考えれば明らか．

original sequenceを $O$ と固定し，複雑さ $i$ のフラクタルを $A_i$ と表すことにしよう．もちろん $A_1 = O$ ．そして， $A_i$ と $A_{i+1}$ の関係について考えよう． $A_i$ の左から $p$ 番目の位置に対して，そこが $L$ ならば $A_{i+1}$ の左から $(p-1)K+d (1 \le d \le K)$ 番目の位置と $O$ の左から $d$ 番目の位置が一致することを表す．また，そこが $G$ ならば $A_{i+1}$ の左から $(p-1)K+d$ 番目の位置は全て $G$ になる．これは定義どおりなので明らかだ．

ここから推論すると，逆に $A_{i+1}$ の左から $(p-1)K+d$ 番目が $L$ であるというのは，「 $A_i$ の左から $p$ 番目が $L$ であり，かつ $O$ の左から $d$ 番目が $L$ である」という時のみに起こることだということになる．これをさらに掘り下げると， $A_i$ のある位置に関して $L$ であるというのは， $O$ の全ての位置の中である特定の部分集合がすべて $L$ になっているということに帰結する．

例えば $K=3$ のとき， $A_3$ の8番目は $A_2$ の3番目から派生する位置で，更にそこは $A_1=O$ の1番目から派生する位置である．ということは $A_3$ の8番目が $L$ であるには，この派生前の位置も $L$ でないといけない，更にこれらは全て $O$ のいずれかの位置に対応しているので，結局順番に見ていくと $A_3$ の8番目が $L$ であるには $O$ の2,3,1番目がそれぞれ $L$ でないといけないことが分かる(つまり全部)．この結果から， $K=3,C=3$ の時には左から8番目を調べることによって全体に少なくとも1つ $G$ があるかないかを調べることが可能になる．

これを一般化してみる．ますは $A_1 = O$ の $p_1$ 文字目からスタートすることにしよう．そして，その文字から生成されるもののうち，左から $p_2$ 番目の子孫を選ぶことにしよう(これは $A_2$ 上の話)．そして，その位置から生成されるもののうち，左から $p_3$ 番目の子孫を選ぶことにしよう．と，これを続けていき， $A_C$ 内において前段階で生成された子孫のうち左から $p_C$ 番目の子孫を選ぶことにしよう．こうして選ばれた $A_C$ 内のとある1文字を調べることによって $O$ 内の $p_1 , p_2 , ... , p_C$ 番目に少なくとも1つは $G$ が含まれているかどうかを判定することが可能になる．つまり，それぞれの $p_i$ が被らないようにうまく選ぶことによって，1箇所を調べることによって $O$ 内の $C$ 箇所をチェックすることが可能であるということになる． $O$ 内を全て調べるには， $O$ の長さは $K$ であるから， $S * C \lt K$ のときは調べることが不可能，よってIMPOSSIBLEということになる．逆にそうでない時は調べ尽くすことが可能である．調べる可能なエリア $S$ 個に対して，1つ目の場所で $O$ の $1, 2, ... ,C$ 文字目をチェックできる位置，2つ目の場所で $C+1, ... , 2C$ 文字目をチェックできる位置， $m( \le S)$ 個目の場所で $(m-1)C+1, ... , K-1, K, K, ... ,K$ 文字目をチェックできる位置を選べば良い．

さて，ここで確認しておくと $A_i$ において $p$ 文字目の子孫となるものは $A_{I+1}$ 内において左から $(p-1)K+d (1 \le d \le K)$ 文字目という形で表わされるのであった．あとはこれを実装して，調べるべき位置 $m$ 個を出力してあげれば良い．

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int main()
{
    int T;
    cin >>T;
    rep(t,T)
    {
        ll k,c,s;
        cin >>k >>c >>s;

        printf("Case #%d:",t+1);

        if(s*c<k) printf(" IMPOSSIBLE\n");
        else
        {
            vector<ll> ans;

            for(ll i=1; i<=k; i+=c)
            {
                ll p=i;
                rep(j,c-1) p=(p-1)*k+min(i+j+1,k);
                ans.pb(p);
            }

            for(const auto &x:ans) cout << " " << x;
            cout << endl;
        }
    }
    return 0;
}

コードに落とすととてつもなくシンプル...

裏紙

ほぼ競プロ、たまに日記

GCJ 2016 Qual Round D - Fractiles

問題

問題概要

アイデア

実装(C++)