project euler 16~20

16. 2^1000の値をすべて足すといくつになるか
ex. 2^4 = 16 -> 1+6 = 7
boostに頼りました。bigIntegerと文字列処理

#include<boost/multiprecision/cpp_int.hpp>
#include<boost/lexical_cast.hpp>

using namespace boost::multiprecision;
using namespace boost;

int main(void){
   mp_uint1024_t a = 2;
   rep(i,999) a *= 2; //2^1 = 2
   string str = lexical_cast<string>(a);
   int sum=0;
   rep(i,str.size()){
      sum += str[i]-'0';
   }
   cout << sum << endl;
   return 0;
}

18. 三角形の頂点から底辺までの通路の和を求める
1
2 3
4 5 6
を計算すると
1
3 4
8 9 10 となり最長は10
動的計画法を使って解く

#define n 15

int main(void){
   int table[n][n] = {0};
   int a=1,b=1;
   for(int i=0;i<a;i++){
      if(a == n+1 || b == n+1) break;
      for(int j=0;j<b;j++){
         cin >> table[i][j];
      }
      a++,b++;
   }
   int dp[n][n] = {0};
   dp[0][0] = table[0][0];
   for(int i=1;i<n;i++){
      for(int j=0;j<n;j++){
         dp[i][j] = max(dp[i-1][j]+table[i][j],dp[i-1][j-1]+table[i][j]);
      }
   }
   vector<int> res;
   rep(i,n){
      rep(j,n){
         cout << dp[i][j] <<" ";
      }
      cout << endl;
   }
   for(int i=0;i<n;i++) res.push_back(dp[n-1][i]);
   cout << *max_element(ALL(res)) << endl;
   return 0;
}

19.1901年から2000までで月初めの曜日が日曜である回数を求める
boost使ってもよかったのですが今回はphpのmktimeを使いました

<?php
//sunday is 0
$cnt=0;
for($year = 1901;$year<=2001;$year++){
    for($month = 1;$month <= 12;$month++){
        if(0 == date("w", mktime(0, 0, 0, $month, 1, $year))) $cnt++;//h,m,s
    }
}
echo "$cnt\n";
?>

20.階乗の値を16(上記)のように合計値をだします。
やり方は16と同様です

#include<boost/multiprecision/cpp_int.hpp>
#include<boost/lexical_cast.hpp>

using namespace boost;
using namespace boost::multiprecision;

int main(void){
   mp_uint1024_t a = 1;
   for(int i=100;i>=1;i--) a *=i;
   string str = lexical_cast<string>(a);
   int res=0;
   rep(i,str.size()){
      res += str[i]-'0';
   }
   cout << res << endl;
   return 0;
}