プロジェクトオイラー Problem 259 「到達可能数」 †

Problem 259 「到達可能数」 †

以下の規則に従った数式の答えとなるような正整数を到達可能と定義する:

1 から 9 の数字を, この順番でちょうど 1 度ずつ使う

連続した数字はつなげることができる(たとえば, 数字 2, 3, 4 を使って数字 234 が得られる)

4 つの2項演算(足し算, 引き算, 掛け算, 割り算)のみが許される

各演算は何度も使えるし, 一度も使われなくてもよい

単項のマイナスは使用できない

演算の順番を決めるために(入れ子でもよい)括弧を何度も使用してよい

例えば, (1/23) * ((4*5)-6) * (78-9) = 42 なので, 42 は到達可能である.

全ての到達可能な正整数の合計を求めよ.

正答者注(123456789も式として認められる)

http://odz.sakura.ne.jp/projecteuler/index.php?Problem%20259

解法

2分割しながら再帰で全探索し、計算は構造体Ｓを通して分数で計算してみたところ意外と少ない計算量で答えが出ました。

#include<stdio.h>

#include<set>

#include<iostream>

__int64 gcd ( __int64 a, __int64 b )

{

  __int64 c;

  while ( a != 0 ) {

     c = a; a = b%a;  b = c;

  }

  return b;

}

struct S{

     __int64 u,d;

     bool operator<(const S& s1)const{

          if(u!=s1.u)return u<s1.u;

          return d<s1.d;

     }

     void yakubun(){

          __int64 u1=u,d1=d;

          if(u1<0)u1=-u1;

          if(d1<0)d1=-d1;

          __int64 g=gcd(u1,d1);

          u=u/g;

          d=d/g;

          if(d<0){

               u=-u;

               d=-d;

          }

     }

     

     S add(const S& s1){

          S reS;

          reS.u=u*s1.d+s1.u*d;

          reS.d=d*s1.d;

          reS.yakubun();

          return reS;

     }

     S dell(const S& s1){

          S reS;

          reS.u=u*s1.d-s1.u*d;

          reS.d=d*s1.d;

          reS.yakubun();

          return reS;

     }

     S mult(const S& s1){

          S reS;

          reS.u=u*s1.u;

          reS.d=d*s1.d;

          reS.yakubun();

          return reS;

     }

     S div(const S& s1){

          S reS;

          reS.u=u*s1.d;

          reS.d=d*s1.u;

          reS.yakubun();

          return reS;

     }

};

S toNum(int L,int R){

     S s1;

     s1.d=1;

     s1.u=0;

     for(int i=L;i<=R;i++){

          s1.u=s1.u*10+i;

     }

     return s1;

}

std::set<S> saiki(int L,int R){

     std::set<S> results,Lset,Rset;

     std::set<S>::iterator itL,itR;

     results.insert(toNum(L,R));

     S s1,s2;

     for(int i=L;i<R;i++){

          Lset=saiki(L,i);

          Rset=saiki(i+1,R);

          for(itL=Lset.begin();itL!=Lset.end();itL++){

               s1=(*itL);

               if(s1.d==0)continue;

               for(itR=Rset.begin();itR!=Rset.end();itR++){

                    s2=(*itR);

                    if(s2.d!=0){

                         results.insert(s1.add(s2));

                         results.insert(s1.dell(s2));

                         results.insert(s1.mult(s2));

                    }

                    if(s2.u!=0){

                         results.insert(s1.div(s2));

                    }

               }

          }

     }

     return results;

}

int main(){

     std::set<S> ansSets=saiki(1,9);

     std::set<S>::iterator it;

     S s1;

     __int64 ans=0;

     

     for(it=ansSets.begin();it!=ansSets.end();it++){

          s1=(*it);

          if(s1.d==1&&s1.u>0){

               ans+=s1.u;

          }

     }

     std::cout<<"\nans="<<ans;

}