問題

Dashboard - Qualification Round 2016 - Google Code Jam

問題概要

jamcoinという長さ $N(\ge 2)$ の文字列がある．jamcoinは以下の性質を満たす：

全ての桁が0か1で構成される．
最上位の桁と最下位の桁は必ず1である．
この文字列を2進数から10進数のどの数として解釈したとしても，その数は全て素数ではない．

長さ $N$ が与えられるので，jamcoinとしてあり得るものを $J$ 個答えよ( $J$ 個存在することは保証されている)．また，それぞれの数に対してjamcoinを2進数から10進数で解釈した時に「非自明な」約数(1と自分自身以外．つまり素数でないことを示せる数)をそれぞれ1つずつ答えよ．

アイデア

smallは愚直にループしてjamcoinが $J$ 個見つかるまで調べ続けた．largeも $N$ と $J$ が分かっていたので，埋め込むという手も無くはなかったけど，まあ予選だしもっといい方法があるだろうということで...

largeでは10進数で32桁の数字が与えられるということなので，long longにも収めることが出来ない， $x$ の約数を探すために，2から $\sqrt{x}$ の数で順番に割り切れるか試していくのでは間に合わない，と様々なところで問題が発生する．

(案1)

これに関しては全てに対して試すのではなく，ある程度の境界を用意(1000までとか)して，そこまでで割り切れなかったらその数字は諦めてしまおうというものである．与えられる $J$ は $N$ に対して余裕があるから多分これでも足りるだろう，と考える(実際に実行してみて足りていればそれで十分じゃないか)．それで，間の $N-2$ 桁を乱択で試しても十分に間に合う．

(案2)

実はそのようなことを悩まなくても，確実に2進数から10進数のいずれで解釈しても「非自明な」約数があるようなjamcoin文字列を生成することができてしまう．今回は与えられる $N$ がsmallもlargeもともに偶数であることに注目すると， $N=2k$ とし，jamcoinの文字列を $x_{2k} x_{2k-1} ... x_{k+1} x_k x_{k-1} ... x_2 x_1 x_0$ と表すことにすると，真ん中でちょうど分けて長さ $k$ の文字列を得た時に2つが同じならそれは必ず因数分解出来るので，非自明な約数を持つようにすることができる．

なぜなら，上半分の文字列が下半分の文字列に一致する時，文字列の形は $x_k x_{k-1} ... x_2 x_1 x_0 x_k x_{k-1} ... x_2 x_1 x_0$ という形になる．そして，このjamcoinを $b$ 進数と見なすと，10進数で表すところの $x_k b^{2k-1} + x_{k-1} b^{2k-2} + ... + x_2 b^{k+2} +x_1 b^{k+1} +x_0 b^{k} + x_k b^{k-1} + x_{k-1} b^{k-2} + ... + x_1 b + x_0$ という値になり，この数は因数分解できて $(x_k b^{k-1} + x_{k-1} b^{k-2} + ... + x_1 b + x_0) (b^k +1)$ となるので，かならず $b^k +1$ が約数になることが分かる．あとは条件をみたすように先頭と末尾を1にした文字列を $J$ 個生成して，この約数を答えとすれば良い．

実装(C++)

bitcoinとしての文字列を乱択で試し， $J$ 個見つかるまでやり続ける方法

#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

//sをb進数として解釈した時にxで割り切れるか
bool div(string s, int b, int x)
{
    int now=0;
    rep(i,s.size())
    {
        now = now*b+(s[i]-'0');
        now%=x;
    }

    return (now==0);
}

int main()
{
    int T;
    cin >>T;
    rep(t,T)
    {
        int N,J;
        cin >>N >>J;

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

        int ct=0;
        set<string> found;
        while(ct<J)
        {
            //ランダムな文字列生成
            string s="1";
            rep(i,N-2)
            {
                if(rand()%2==1) s+="1";
                else s+="0";
            }
            s+="1";

            //すでにある
            if(found.find(s)!=found.end()) continue;

            bool valid=true;
            vector<int> ans;

            //i進数で解釈した時に
            for(int i=2; i<=10; ++i)
            {
                bool ok=false;
                //jで割り切れるか
                for(int j=2; j<=1000; ++j)
                {
                    if(div(s,i,j))
                    {
                        ok=true;
                        ans.pb(j);
                        break;
                    }
                }

                if(!ok)
                {
                    valid=false;
                    break;
                }
            }

            if(valid)
            {
                ++ct;
                found.insert(s);

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

bitcoinを上半分と下半分に分け下半分の数を約数として答える方法

#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)
    {
        int N,J;
        cin >>N >>J;

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

        N/=2;

        ll pw[11];
        rep(i,11) pw[i]=1;
        for(ll i=1; i<=10; ++i)
        {
            rep(j,N) pw[i]*=i;
            pw[i]+=1;
        }

        //順番に文字列をJ個生成
        rep(i,J)
        {
            string s="1";
            rep(j,N-2)
            {
                if(i>>j&1) s+="1";
                else s+="0";
            }
            s+="1";

            cout << s+s;
            for(int j=2; j<=10; ++j)
                cout << " " << pw[j];
            cout << endl;
        }
    }
    return 0;
}

裏紙

ほぼ競プロ、たまに日記

GCJ 2016 Qual Round C - Coin Jam

問題

問題概要

アイデア

実装(C++)