読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

GCJ 2016 Qual Round D - Fractiles

問題

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なのか分からないが,KCの値についてはわかっている.そして今,タイルを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_iA_{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 = Op_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つ目の場所でO1, 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;
}

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