でっかい数を作るソルバー
ネタバレ注意。
問題解説
全ての元凶
http://twitter.com/s01/status/21375206236
ネタバレ含む解説
http://d.hatena.ne.jp/sylph01/20100817/1282028426
http://d.hatena.ne.jp/sylph01/20100818/1282120209
xhl's ソルバー
ソースは末尾に載せておきます。
$ g++ -O3 solver.cpp $ ./a.out 1000000
とかすると、確か 3063060 が出てきた気がします。
http://twitter.com/xhl/status/21426888852
注意: 必要環境: 64bit環境、メモリ40GBくらい。実行時間30分くらい。ゆっくりAmazon EC2でも使っていってね!!!
$ g++ -O3 solver.cpp $ ./a.out 1000
くらいなら普通のPCでも動く雰囲気です。これでも 2934360 くらい出ます。
解法解説
解法: DP。
1.1〜2.0の数の部分集合Xに対し、Xに属する数を全て一回ずつと任意個の+-*/()を使ってできる数の「最大値 MAX(X)」「最小値 MIN(X)」「最小の正の値 MINABSP(X)」「最大の負の値 MINABSN(X)」「可能な値全ての集合 ALL(X)」をメモ化探索で求めます。
ALL は MINABSP(X), MINABSN(X)を求める時に使っています。何か-何か、みたいなパターンでMINABSPを実現する場合には、Xを二つの部分集合A,Bに分割して、a∈ALL(A)とb∈ALL(B)の中からa-bが最小かつa>bのものを見つけています(見つからない場合は適当な0以下の値を返しています)。
普通にやると、このALLのサイズがとんでもなく大きくなるため、このソルバーではALLのサイズに上限(コマンドライン引数で与えている)を設けています。この一点以外は厳密解法になっているはずです。
厳密解法に向けて
私はここで一度力尽きることにしたので、厳密解に向けた妄想を吐き出しておきます。
後は任せた(ぉ
本質的に重要なのは、MINABSP(X)(or MINABSN(X))の計算です。これさえできれば問題なく厳密解に到達できるはず。
MAX(X)のXのサイズは最大10なので、MINABSP(X)におけるXの最大サイズは9です。
なので9要素のMINABSP(X)が計算できればはっぴー。
で、私の実装ではMINABSP(X)の計算に(そしてそのためだけに)ALL(X)を使っていて、ALL(X)の計算が厳密にできないため近似解になっています。
ALL(A)のAの最大サイズは8です(MINABSP(X)のXを8要素のAと1要素のBに分割)。
ALL(A)の計算については、Aのサイズが6個以下までならALL(A)のサイズは3.5M要素くらいに収まるので、省メモリ化すればなんとかなる気がします。
Aのサイズが7 or 8の場合は250M or 20G要素くらいになると試算したので、ヒトゲノム解析センターの2TBメモリマシン( https://supcom.hgc.jp/japanese/sys_const/000013.html )使うとかしない限り無理です(メモリが足りたとしても計算時間が...)。
別にALL(A)の全ての要素を計算する必要はなくて、必要なのは最低限、b∈ALL(B)に対し、「bより大きい最小の数 GREATERMIN(A,b)」及び「bより小さい最大の数 LESSMAX(A,b)」の二つだけです。
ここで問題になるかもしれないのは値bの種類数ですが、Aのサイズが7 or 8の場合Bのサイズは高々2 or 1なので、各Bに対し高々6倍(B={x,y}に対し{x+y,x-y,y-x,x*y,x/y,y/x})くらいです。
6要素以下まで落とせばALL(A)が使えるので、7,8要素の部分だけ、なんとか「bより大きい最小の数」「bより小さい最大の数」で持ちこたえられれば、厳密解に手が届くのではないでしょーか。
ただ、メモリに乗っても計算時間はかなり長くなるのではないかと思います。
ソルバーのソース
#include<stdio.h> #include<limits.h> #include<float.h> #include<map> #include<math.h> #include<set> using namespace std; #define N 10 typedef long double DOUBLE; #define NONZERO(t) (fabs(t) >= 1e-9) int popcount(int a){ int c = 0; for( int i = 0; i < N; i ++ ) if( a & (1<<i) ) c ++; return c; } DOUBLE min( DOUBLE x, int &l, int &r, int &f, int mask1, int mask2, int op, DOUBLE y ) { if( x > y ){ l = mask1; r = mask2; f = op; return y; } else return x; } DOUBLE max( DOUBLE x, int &l, int &r, int &f, int mask1, int mask2, int op, DOUBLE y ) { if( x < y ){ l = mask1; r = mask2; f = op; return y; } else return x; } DOUBLE minabsp( DOUBLE x, int &l, int &r, int &f, int mask1, int mask2, int op, DOUBLE y ) { if( y > 0 && NONZERO(y) && (x <= 0 || y < x) ){ l = mask1; r = mask2; f = op; return y; } else return x; } DOUBLE minabsn( DOUBLE x, int &l, int &r, int &f, int mask1, int mask2, int op, DOUBLE y ) { if( y < 0 && NONZERO(y) && (x >= 0 || y > x) ){ l = mask1; r = mask2; f = op; return y; } else return x; } DOUBLE VALUE[] = {1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0, 2.1, 2.2, 2.3, 2.4, 2.5}; DOUBLE getMAX( int mask ); DOUBLE getMIN( int mask ); DOUBLE getMINABSP( int mask ); DOUBLE getMINABSN( int mask ); class ALLST{ public: ALLST(int mask1_,int mask2_, int op_, DOUBLE d1_, DOUBLE d2_): mask1(mask1_), mask2(mask2_), op(op_), d1(d1_), d2(d2_){} ALLST(){} DOUBLE d1, d2; signed short mask1; signed short mask2; char op; }; #define ALLST_ ALLST map<DOUBLE, ALLST> &getALL( int mask ); void showMAX( int mask ); void showMIN( int mask ); void showMINABSP( int mask ); void showMINABSN( int mask ); void showALL( int mask, DOUBLE D ); DOUBLE dpMAX[(1<<N)]; int dpfMAX[(1<<N)]; int dplMAX[(1<<N)]; int dprMAX[(1<<N)]; void showMAX( int mask ) { int op = dpfMAX[mask]; int l = dplMAX[mask]; int r = dprMAX[mask]; printf( "("); if( 100 <= op ) printf( "%.2lf", (double)VALUE[op-100]); else switch( op ){ case 2: showMAX(l); printf( "+" ); showMAX(r); break; case 3: showMAX(l); printf( "-" ); showMIN(r); break; case 41: showMAX(l); printf( "*" ); showMAX(r); break; case 42: showMAX(l); printf( "*" ); showMIN(r); break; case 43: showMIN(l); printf( "*" ); showMAX(r); break; case 44: showMIN(l); printf( "*" ); showMIN(r); break; case 51: showMAX(l); printf( "/" ); showMAX(r); break; case 52: showMIN(l); printf( "/" ); showMAX(r); break; case 53: showMAX(l); printf( "/" ); showMIN(r); break; case 54: showMIN(l); printf( "/" ); showMIN(r); break; case 55: showMAX(l); printf( "/" ); showMINABSP(r); break; case 56: showMIN(l); printf( "/" ); showMINABSP(r); break; case 57: showMAX(l); printf( "/" ); showMINABSN(r); break; case 58: showMIN(l); printf( "/" ); showMINABSN(r); break; default: printf( "<INVALID:%d>", op ); } printf( ")"); } DOUBLE getMAX( int mask ) { if( dpfMAX[mask] ) return dpMAX[mask]; for( int i = 0; i < N; i ++ ){ if( mask == (1<<i) ){ dpfMAX[mask] = 100+i; return dpMAX[mask] = VALUE[i]; } } DOUBLE D = DBL_MIN; int &ff = dpfMAX[mask]; int &l = dplMAX[mask]; int &r = dprMAX[mask]; ff = 1; for( int i = 0; i < (1<<N); i ++ ){ if( (i & mask) != i ) continue; int mask1 = i & mask; int mask2 = ~i & mask; if( mask1 == 0 || mask2 == 0 ) continue; D = max( D, l, r, ff, mask1, mask2, 2, getMAX(mask1) + getMAX(mask2) ); D = max( D, l, r, ff, mask1, mask2, 3, getMAX(mask1) - getMIN(mask2) ); D = max( D, l, r, ff, mask1, mask2, 41, getMAX(mask1) * getMAX(mask2) ); D = max( D, l, r, ff, mask1, mask2, 42, getMAX(mask1) * getMIN(mask2) ); D = max( D, l, r, ff, mask1, mask2, 43, getMIN(mask1) * getMAX(mask2) ); D = max( D, l, r, ff, mask1, mask2, 44, getMIN(mask1) * getMIN(mask2) ); DOUBLE t; t = getMAX(mask2); if( NONZERO(t) ){ D = max( D, l, r, ff, mask1, mask2, 51, getMAX(mask1) / t ); D = max( D, l, r, ff, mask1, mask2, 52, getMIN(mask1) / t ); } t = getMIN(mask2); if( NONZERO(t) ){ D = max( D, l, r, ff, mask1, mask2, 53, getMAX(mask1) / t ); D = max( D, l, r, ff, mask1, mask2, 54, getMIN(mask1) / t ); } t = getMINABSP(mask2); if( NONZERO(t) ){ D = max( D, l, r, ff, mask1, mask2, 55, getMAX(mask1) / t ); D = max( D, l, r, ff, mask1, mask2, 56, getMIN(mask1) / t ); } t = getMINABSN(mask2); if( NONZERO(t) ){ D = max( D, l, r, ff, mask1, mask2, 57, getMAX(mask1) / t ); D = max( D, l, r, ff, mask1, mask2, 58, getMIN(mask1) / t ); } } return dpMAX[mask] = D; } DOUBLE dpMIN[(1<<N)]; int dpfMIN[(1<<N)]; int dplMIN[(1<<N)]; int dprMIN[(1<<N)]; void showMIN( int mask ) { int op = dpfMIN[mask]; int l = dplMIN[mask]; int r = dprMIN[mask]; printf( "("); if( 100 <= op ) printf( "%.2lf", (double)VALUE[op-100]); else switch( op ){ case 2: showMIN(l); printf( "+" ); showMIN(r); break; case 3: showMIN(l); printf( "-" ); showMAX(r); break; case 41: showMAX(l); printf( "*" ); showMAX(r); break; case 42: showMAX(l); printf( "*" ); showMIN(r); break; case 43: showMIN(l); printf( "*" ); showMAX(r); break; case 44: showMIN(l); printf( "*" ); showMIN(r); break; case 51: showMAX(l); printf( "/" ); showMAX(r); break; case 52: showMIN(l); printf( "/" ); showMAX(r); break; case 53: showMAX(l); printf( "/" ); showMIN(r); break; case 54: showMIN(l); printf( "/" ); showMIN(r); break; case 55: showMAX(l); printf( "/" ); showMINABSP(r); break; case 56: showMIN(l); printf( "/" ); showMINABSP(r); break; case 57: showMAX(l); printf( "/" ); showMINABSN(r); break; case 58: showMIN(l); printf( "/" ); showMINABSN(r); break; default: printf( "<INVALID:%d>", op ); } printf( ")"); } DOUBLE getMIN( int mask ) { if( dpfMIN[mask] ) return dpMIN[mask]; for( int i = 0; i < N; i ++ ){ if( mask == (1<<i) ){ dpfMIN[mask] = 100+i; return dpMIN[mask] = VALUE[i]; } } DOUBLE D = DBL_MAX; int &ff = dpfMIN[mask]; int &l = dplMIN[mask]; int &r = dprMIN[mask]; ff = 1; for( int i = 0; i < (1<<N); i ++ ){ if( (i & mask) != i ) continue; int mask1 = i & mask; int mask2 = ~i & mask; if( mask1 == 0 || mask2 == 0 ) continue; D = min( D, l, r, ff, mask1, mask2, 2, getMIN(mask1) + getMIN(mask2) ); D = min( D, l, r, ff, mask1, mask2, 3, getMIN(mask1) - getMAX(mask2) ); D = min( D, l, r, ff, mask1, mask2, 41, getMAX(mask1) * getMAX(mask2) ); D = min( D, l, r, ff, mask1, mask2, 42, getMAX(mask1) * getMIN(mask2) ); D = min( D, l, r, ff, mask1, mask2, 43, getMIN(mask1) * getMAX(mask2) ); D = min( D, l, r, ff, mask1, mask2, 44, getMIN(mask1) * getMIN(mask2) ); DOUBLE t; t = getMAX(mask2); if( NONZERO(t) ){ D = min( D, l, r, ff, mask1, mask2, 51, getMAX(mask1) / t ); D = min( D, l, r, ff, mask1, mask2, 52, getMIN(mask1) / t ); } t = getMIN(mask2); if( NONZERO(t) ){ D = min( D, l, r, ff, mask1, mask2, 53, getMAX(mask1) / t ); D = min( D, l, r, ff, mask1, mask2, 54, getMIN(mask1) / t ); } t = getMINABSP(mask2); if( NONZERO(t) ){ D = min( D, l, r, ff, mask1, mask2, 55, getMAX(mask1) / t ); D = min( D, l, r, ff, mask1, mask2, 56, getMIN(mask1) / t ); } t = getMINABSN(mask2); if( NONZERO(t) ){ D = min( D, l, r, ff, mask1, mask2, 57, getMAX(mask1) / t ); D = min( D, l, r, ff, mask1, mask2, 58, getMIN(mask1) / t ); } } return dpMIN[mask] = D; } DOUBLE dpMINABSP[(1<<N)]; int dpfMINABSP[(1<<N)]; int dplMINABSP[(1<<N)]; int dprMINABSP[(1<<N)]; DOUBLE dpLMINABSP[(1<<N)]; DOUBLE dpRMINABSP[(1<<N)]; void showMINABSP( int mask ) { int op = dpfMINABSP[mask]; int l = dplMINABSP[mask]; int r = dprMINABSP[mask]; printf( "("); if( 100 <= op ) printf( "%.2lf", (double)VALUE[op-100]); else switch( op ){ case 41: showMINABSP(l); printf( "*" ); showMINABSP(r); break; case 42: showMINABSN(l); printf( "*" ); showMINABSN(r); break; case 51: showMINABSP(l); printf( "/" ); showMAX(r); break; case 52: showMINABSN(l); printf( "/" ); showMIN(r); break; case 3: showALL(l, dpLMINABSP[mask]); printf( "-" ); showALL(r, dpRMINABSP[mask]); break; case 2: showALL(l, dpLMINABSP[mask]); printf( "+" ); showALL(r, dpRMINABSP[mask]); break; default: printf( "<INVALID:%d>", op ); } printf( ")"); } DOUBLE getMINABSP( int mask ) { if( dpfMINABSP[mask] ) return dpMINABSP[mask]; for( int i = 0; i < N; i ++ ){ if( mask == (1<<i) ){ dpfMINABSP[mask] = 100+i; return dpMINABSP[mask] = VALUE[i]; } } int &ff = dpfMINABSP[mask]; int &l = dplMINABSP[mask]; int &r = dprMINABSP[mask]; ff = 1; DOUBLE D = 0; for( int i = 0; i < (1<<N); i ++ ){ if( (i & mask) != i ) continue; int mask1 = i & mask; int mask2 = ~i & mask; if( mask1 == 0 || mask2 == 0 ) continue; D = minabsp( D, l, r, ff, mask1, mask2, 41, getMINABSP(mask1) * getMINABSP(mask2) ); D = minabsp( D, l, r, ff, mask1, mask2, 42, getMINABSN(mask1) * getMINABSN(mask2) ); if( NONZERO(getMAX(mask2)) ) D = minabsp( D, l, r, ff, mask1, mask2, 51, getMINABSP(mask1) / getMAX(mask2) ); if( NONZERO(getMIN(mask2)) ) D = minabsp( D, l, r, ff, mask1, mask2, 52, getMINABSN(mask1) / getMIN(mask2) ); if( popcount(mask1) < popcount(mask2) || (popcount(mask1) == popcount(mask2) && mask1 < mask2) ){ map<DOUBLE, ALLST> &s1 = getALL(mask1); map<DOUBLE, ALLST> &s2 = getALL(mask2); for( map<DOUBLE, ALLST>::const_iterator it1 = s1.begin(), ite1 = s1.end(); it1 != ite1; ++ it1 ){ DOUBLE a = it1->first; { map<DOUBLE, ALLST>::const_iterator it = s2.lower_bound(a); if( it != s2.begin() ){ -- it; DOUBLE Dx = D; D = minabsp( D, l, r, ff, mask1, mask2, 3, a - it->first ); if( D != Dx ){ dpLMINABSP[mask] = a; dpRMINABSP[mask] = it->first; } } } { map<DOUBLE, ALLST>::const_iterator it = s2.upper_bound(-a); if( it != s2.end() ){ DOUBLE Dx = D; D = minabsp( D, l, r, ff, mask1, mask2, 2, a + it->first ); if( D != Dx ){ dpLMINABSP[mask] = a; dpRMINABSP[mask] = it->first; } } } { map<DOUBLE, ALLST>::const_iterator it = s2.upper_bound(a); if( it != s2.end() ){ DOUBLE Dx = D; D = minabsp( D, l, r, ff, mask2, mask1, 3, it->first - a ); if( D != Dx ){ dpLMINABSP[mask] = it->first; dpRMINABSP[mask] = a; } } } } } } return dpMINABSP[mask] = D; } DOUBLE dpMINABSN[(1<<N)]; int dpfMINABSN[(1<<N)]; int dplMINABSN[(1<<N)]; int dprMINABSN[(1<<N)]; DOUBLE dpLMINABSN[(1<<N)]; DOUBLE dpRMINABSN[(1<<N)]; void showMINABSN( int mask ) { int op = dpfMINABSN[mask]; int l = dplMINABSN[mask]; int r = dprMINABSN[mask]; printf( "("); if( 100 <= op ) printf( "%.2lf", (double)VALUE[op-100]); else switch( op ){ case 41: showMINABSP(l); printf( "*" ); showMINABSN(r); break; case 42: showMINABSN(l); printf( "*" ); showMINABSP(r); break; case 51: showMINABSN(l); printf( "/" ); showMAX(r); break; case 52: showMINABSP(l); printf( "/" ); showMIN(r); break; case 3: showALL(l, dpLMINABSN[mask]); printf( "-" ); showALL(r, dpRMINABSN[mask]); break; case 2: showALL(l, dpLMINABSN[mask]); printf( "+" ); showALL(r, dpRMINABSN[mask]); break; default: printf( "<INVALID:%d>", op ); } printf( ")"); } DOUBLE getMINABSN( int mask ) { if( dpfMINABSN[mask] ) return dpMINABSN[mask]; for( int i = 0; i < N; i ++ ){ if( mask == (1<<i) ){ dpfMINABSN[mask] = 100 + i; return dpMINABSN[mask] = VALUE[i]; } } DOUBLE D = 0; int &ff = dpfMINABSN[mask]; int &l = dplMINABSN[mask]; int &r = dprMINABSN[mask]; ff = 1; for( int i = 0; i < (1<<N); i ++ ){ if( (i & mask) != i ) continue; int mask1 = i & mask; int mask2 = ~i & mask; if( mask1 == 0 || mask2 == 0 ) continue; D = minabsn( D, l, r, ff, mask1, mask2, 41, getMINABSP(mask1) * getMINABSN(mask2) ); D = minabsn( D, l, r, ff, mask1, mask2, 42, getMINABSN(mask1) * getMINABSP(mask2) ); if( NONZERO(getMAX(mask2)) ) D = minabsn( D, l, r, ff, mask1, mask2, 51, getMINABSN(mask1) / getMAX(mask2) ); if( NONZERO(getMIN(mask2)) ) D = minabsn( D, l, r, ff, mask1, mask2, 52, getMINABSP(mask1) / getMIN(mask2) ); if( popcount(mask1) < popcount(mask2) || (popcount(mask1) == popcount(mask2) && mask1 < mask2) ){ map<DOUBLE, ALLST> &s1 = getALL(mask1); map<DOUBLE, ALLST> &s2 = getALL(mask2); for( map<DOUBLE, ALLST>::const_iterator it1 = s1.begin(), ite1 = s1.end(); it1 != ite1; ++ it1 ){ DOUBLE a = it1->first; { map<DOUBLE, ALLST>::const_iterator it = s2.lower_bound(a); if( it != s2.begin() ){ -- it; DOUBLE Dx = D; D = minabsn( D, l, r, ff, mask2, mask1, 3, it->first - a ); if( D != Dx ){ dpLMINABSN[mask] = it->first; dpRMINABSN[mask] = a; } } } { map<DOUBLE, ALLST>::const_iterator it = s2.upper_bound(a); if( it != s2.end() ){ DOUBLE Dx = D; D = minabsn( D, l, r, ff, mask1, mask2, 3, a - it->first ); if( D != Dx ){ dpLMINABSN[mask] = a; dpRMINABSN[mask] = it->first; } } } { map<DOUBLE, ALLST>::const_iterator it = s2.lower_bound(-a); if( it != s2.begin() ){ -- it; DOUBLE Dx = D; D = minabsn( D, l, r, ff, mask1, mask2, 2, a + it->first ); if( D != Dx ){ dpLMINABSN[mask] = a; dpRMINABSN[mask] = it->first; } } } } } } return dpMINABSP[mask] = D; } map<DOUBLE, ALLST> *dpALL[(1<<N)]; void showALL( int mask, DOUBLE d ) { ALLST st = (*dpALL[mask])[d]; #if 1 if( st.op >= 100 ){ printf( "%.2lf", (double)VALUE[st.op-100]); } else{ printf( "(" ); showALL( st.mask1, st.d1 ); printf( "%c", " +-*/"[st.op] ); showALL( st.mask2, st.d2 ); printf( ")" ); } #endif } int g_limit = 10000; map<DOUBLE, ALLST> &getALL( int mask ) { if( dpALL[mask] ) return *dpALL[mask]; map<DOUBLE, ALLST> *s = new map<DOUBLE, ALLST>; for( int i = 0; i < N; i ++ ){ if( mask == (1<<i) ){ s->insert( make_pair(VALUE[i], ALLST_(0,0,100+i,0,0)) ); return *(dpALL[mask] = s); } } int c = 0; for( int i = 0; i < N; i ++ ){ if( mask & (1<<i) ) c++; } int T = 0; for( int i = 0; i < (1<<N); i ++ ){ if( (i & mask) != i ) continue; int mask1 = i & mask; int mask2 = ~i & mask; if( mask1 == 0 || mask2 == 0 ) continue; map<DOUBLE, ALLST> &s1 = getALL(mask1); map<DOUBLE, ALLST> &s2 = getALL(mask2); for( map<DOUBLE, ALLST>::const_iterator it1 = s1.begin(), ite1 = s1.end(); it1 != ite1; ++ it1 ){ DOUBLE a = it1->first; for( map<DOUBLE, ALLST>::const_iterator it2 = s2.begin(), ite2 = s2.end(); it2 != ite2; ++ it2 ){ DOUBLE b = it2->first; (*s)[a + b] = ALLST_(mask1, mask2, 2, a, b); (*s)[a - b] = ALLST_(mask1, mask2, 3, a, b); (*s)[a * b] = ALLST_(mask1, mask2, 4, a, b); if( NONZERO(b) ) (*s)[a / b] = ALLST_(mask1, mask2, 5, a, b); if( c >= 6 && s->size() >= g_limit ){ goto END; } } } } END:; return *(dpALL[mask] = s); } int main(int argc,char *argv[]) { memset( dpfMAX, 0x00, sizeof(dpfMAX) ); memset( dpfMIN, 0x00, sizeof(dpfMIN) ); memset( dpfMINABSP, 0x00, sizeof(dpfMINABSP) ); memset( dpfMINABSN, 0x00, sizeof(dpfMINABSN) ); memset( dpALL, 0x00, sizeof(dpALL) ); int mask = (1<<N) - 1; g_limit = atoi( argv[1] ); printf( "%lf\n", (double)getMAX(mask) ); showMAX(mask); }