「オイラープロジェクト201～210」の編集履歴（バックアップ）一覧に戻る
*問い201
数の集合Aについて, sum(A)でAの要素の和を表す. 集合B = {1,3,6,8,10,11}を考えよう. Bの3要素の部分集合は20個あり, それぞれ和は以下になる.
sum({1,3,6}) = 10,
sum({1,3,8}) = 12,
sum({1,3,10}) = 14,
sum({1,3,11}) = 15,
sum({1,6,8}) = 15,
sum({1,6,10}) = 17,
sum({1,6,11}) = 18,
sum({1,8,10}) = 19,
sum({1,8,11}) = 20,
sum({1,10,11}) = 22,
sum({3,6,8}) = 17,
sum({3,6,10}) = 19,
sum({3,6,11}) = 20,
sum({3,8,10}) = 21,
sum({3,8,11}) = 22,
sum({3,10,11}) = 24,
sum({6,8,10}) = 24,
sum({6,8,11}) = 25,
sum({6,10,11}) = 27,
sum({8,10,11}) = 29.
これらの和は1つしか現れない場合もそうでない場合もある. 集合Aについて, U(A,k)で, Aのk要素の集合全体について和を取ったときに1回のみ現れる和の集合を表す. 上の例をとると, U(B,3) = {10,12,14,18,21,25,27,29}であり, sum(U(B,3)) = 156となる.
今, 100個の要素を持つ集合 S = {12, 22, ..., 1002}を考える. Sの50要素の部分集合は100891344545564193334812497256個ある.
50要素の部分集合の和の中で1回のみ現れる和の集合の総和を求めよ. すなわち, sum(U(S,50))を求めよ.
*解法
メモリ使用量を抑えてみようとmapを使ったらなんか遅い。
もう少しましなコードを考えてみようと思う。
#include<stdio.h>
#include<iostream>
#include<map>
const int up=300000;
std::map<int,__int64> memo[51];
std::map<int,__int64>::iterator it;
int main(){
int num,num2;
memo[0][0]=1;
for(int i=1;i<=100;i++){
num=i*i;
for(int p=49;p>=0;p--){
for(it=memo[p].begin();it!=memo[p].end();it++){
num2=num+(*it).first;
if(memo[p+1].find(num2)==memo[p+1].end())memo[p+1][num2]=0;
memo[p+1][num2]+=(*it).second;
}
}
printf("%d ",i);
}
__int64 ans=0;
for(it=memo[50].begin();it!=memo[50].end();it++){
if((*it).second==1)ans+=(*it).first;
}
std::cout<<ans<<"\n";
}
*問い203
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20203
指定された段数のパスカルの三角形の中から有る条件を満たす数を求めよという問題。
同じ計算は二度しないというどんな単純労働でも当てはまる原則に従い、出てきた数字のリストを作ります。
後は判別関数で足しこむか判別するだけです。
判別関数は平方根の概念を使えばもう少し高速化出来る気もします。
#include<stdio.h>
#include<set>
#include<iostream>
const int size=51;
bool isDiv(__int64 n){
for(__int64 i=2;i*i<=n;i+=1+(i&1)){
if(n%(i*i)==0)return false;
}
return true;
}
int main(){
__int64 row[size+2]={0},max=0;
row[1]=1;
std::set<__int64> memo;
std::set<__int64>::iterator it;
for(int r=0;r<size-1;r++){
for(int c=r+2;c>0;c--){
row[c]=row[c]+row[c-1];
memo.insert(row[c]);
if(max<row[c])max=row[c];
}
}
__int64 ans=0;
for(it=memo.begin();it!=memo.end();it++){
ans+=(*it)*isDiv((*it));
}
std::cout<<ans;
}
*問い204
ハミング数とは, どの素因数も5以下であるような正整数のことである. 最初から順に並べると, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15となる. 108以下のハミング数は1105個ある.
素因数がn以下の正整数を, type nの一般化ハミング数と呼ぶことにする. するとハミング数はtype 5の一般化ハミング数である.
109以下のtype 100の一般化ハミング数の個数を答えよ.
解法
最初に思いついたコード。
1000万以下の数までハミング数であるかどうかをメモ化していく。
１０００万以上の数は割っていってる最中で、１０００万以下の数になったらその数がハミング数であるかどうかメモ化部分と照合して計算量を下げるコード。
素因数分解の一意性を利用している。
もう少し早く動くかと思ったが答えが出るまで数分かかるので少し遅い、手元のパソコンで３分もかかった。
メモリも結構くってる。
このコードはアプローチの仕方が間違っていた。
#include<stdio.h>
#include<vector>
#include<algorithm>
const int up=100;
const int up2=10000000;
std::vector<int> sosuu;
bool so[up+1];
bool okMemo[up2+1];
void setSo(){
int i2;
memset(so,true,sizeof(so));
so[0]=so[1]=false;
for(int i=4;i<=up;i+=2)so[i]=false;
sosuu.push_back(2);
for(int i=3;i<=up;i+=2){
if(so[i]==false)continue;
sosuu.push_back(i);
i2=i*2;
for(int j=i*3;j<up;j+=i2){
so[j]=false;
}
}
}
bool isOK(const int n){
int a=n;
bool ans=false,stop=false;
for(int i=0;i<sosuu.size();i++){
while(a%sosuu[i]==0){
a/=sosuu[i];
if(up2>a){
ans=okMemo[a];
stop=true;
break;
}
}
if(stop==true)break;
}
if(up2>n)okMemo[n]=ans;
return ans;
}
int main(){
setSo();
okMemo[1]=okMemo[2]=true;
int ans=2;
for(int i=3;i<=1000000000;i++){
ans+=isOK(i);
}
printf("%d",ans);
}
より正しいアプローチに変えたコード。
1から掛け算で全ての場合を求めていくコード。
こちらのコードの方が発想がシンプルでコードもすっきりしている。
シンプルですっきりしているということは競技プログラムの大抵の問題でより良いコードが書けたという指標である。
実際こちらは一瞬で答えが出る。
#include<stdio.h>
const int up=100;
const int up2=1000000000;
const int sosuu[25]={2,3,5,7,11,13,17,19,23,29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
int ans=0;
void saiki(int p,__int64 num){
if(num>up2)return;
ans++;
for(int i=p;i<=24;i++){
saiki(i,num*sosuu[i]);
}
}
int main(){
saiki(0,1);
printf("%d",ans);
}
*問い205
ピーターは4面のサイコロを9つ持っている. サイコロの各面には1, 2, 3, 4と書いてある. コリンは6面のサイコロを6つ持っている. サイコロの各面には1, 2, 3, 4, 5, 6と書いてある.
ピーターとコリンはサイコロを投じ, 出た目の合計を比べる. 合計が多い方が勝ちである. もし出た目の合計が等しければ勝負は引き分けになる.
ピーターがコリンに勝つ確率はいくつだろうか? 10進7桁にroundし, 0.abcdefgという形で回答欄に入力せよ.
解法
さいころの数が少ないので動的計画法でさいころの分布を求めて、後はコリンの目がでたらピーターはそれ以上の目を出したばあいの組み合わせを計算して足し合わせていくだけです。
さいころの数が物凄いことになったら標準偏差や数学の知識を駆使しないと解けません。
計算量は大雑把に言って３０００回+memcpy*10回、全探索しても大した量でもないので計算量を抑えた意味はあまりでてません。
プロジェクトオイラーの問題を解いていると自分のレベルの低さがばかり感じます。
#include<stdio.h>
#include<string.h>
int main(){
double memo4[37]={0},memo6[37]={0},next4[37],next6[37];
memo4[0]=memo6[0]=1;
for(int i=0;i<9;i++){
memset(next4,0,sizeof(next4));
for(int i=0;i<37;i++){
for(int j=1;j<5&&i>=j;j++){
next4[i]+=memo4[i-j];
}
}
memcpy(memo4,next4,sizeof(next4));
}
for(int i=0;i<6;i++){
memset(next6,0,sizeof(next6));
for(int i=0;i<37;i++){
for(int j=1;j<7&&i>=j;j++){
next6[i]+=memo6[i-j];
}
}
memcpy(memo6,next6,sizeof(next6));
}
double sum4=0,sum6=0,ans=0;
for(int i=0;i<=36;i++){
sum4+=memo4[36-i];
memo4[36-i]=sum4;
sum6+=memo6[i];
}
for(int i=0;i<36;i++){
ans+=memo4[i+1]*memo6[i];
}
ans=(ans/sum4)/sum6;
printf("%.7lf",ans);
}
*問い206
二乗すると「1_2_3_4_5_6_7_8_9_0」の形となるような唯一の正整数を求めよ. ただし, 「_」は1桁の数である.
解法
__int64の扱える範囲を少しだけはみ出てるいじわる問題。
とりあえず末尾が0なので答えの１桁目も0ということを利用して解きます。
コードが少し遅いのでもう少し工夫の血がありそうです。
b*b=1_2_3_4_5_6_7_8_9_0
b=a*10;
1_2_3_4_5_6_7_8_9_0=a*a*100
(__int64)1_2_3_4_5_6_7_8_9_0/100=1_2_3_4_5_6_7_8_9=a*a
solve 1_2_3_4_5_6_7_8_9=a*a
もう少し賢い解法がありそうです。
#include<stdio.h>;
#include<iostream>
bool isOK(__int64 a){
a*=a;
for(int i=9;i>0;i--){
if(a%10!=i)return false;
a/=100;
}
return true;
}
int main(){
__int64 a=101010101;
while(!isOK(a++));
std::cout<<(a-1)*10;
}
