Problem 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";
}
もう少しましなコード。
ビット演算を使って高速化。
３重ループの一番内側をビット演算にすることで２重ループにした小手先コード。
今回の問題は0,1,2以上以外の数えが意味がないことを利用して、数の数えを２ビットに縮約。
128bit整数型とかあればもっと簡潔に書けるんだけどないのでstd::mapをint64２つに置き換えました。
合計数ｎとしてcount50[0][n]の50ビット目までが２５個まで使った数の数えで、count50[1][n]の50ビット目までが26個から５０個までの数えを担当。
２重ループ内部のビット演算は各２ビットごとに１ビット目は足し算、２ビット目はorを取ることで３以上は３に収まるようになっている。
コード作成時参考になったのはエイトクイーン問題をビット演算で高速に解くコード。
コード作成後、他の人のコードを見てたらulanさんのコードが私と同じ発想で私よりエレガントなコードを書いてた、勉強になる。
プログラム作りは難しいな。
コード実行時間0.156sec
他の人が十数秒から数秒かかってる中私のコードは実行速度は多分上位。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<time.h>
const int up=300000;
__int64 count50[2][up+1];
int main(){
memset(count50,0,sizeof(count50));
//std::cout<<check<<"\n";
int i2,top;
__int64 t1,t2,t3,t4;
double start=clock();
for(int i=1;i<=100;i++){
i2=i*i;
top+=i2;
if(top>=up)top=up;
for(int n=top;n>i2;n--){
t1=count50[0][n-i2]<<2;
t2=(t1&0x2aaaaaaaaaaaai64)|(count50[0][n]&0x2aaaaaaaaaaaai64);
t3=(t1&0x1555555555555i64)+(count50[0][n]&0x1555555555555i64);
count50[0][n]|=(t2|t3);
t1=(count50[1][n-i2]<<2)|(count50[0][n-i2]>>48);
t2=(t1&0x2aaaaaaaaaaaai64)|(count50[1][n]&0x2aaaaaaaaaaaai64);
t3=(t1&0x1555555555555i64)+(count50[1][n]&0x1555555555555i64);
count50[1][n]|=(t2|t3);
}
count50[0][i2]+=(count50[0][i2]&3)>1?0:1;
}
__int64 ans=0;
for(int i=0;i<up;i++){
if(((count50[1][i]>>48)&3)==1)ans+=i;
}
std::cout<<ans<<"time"<<clock()-start;
}
問い202
解法
反射したときの線対称を考えると三角形でできたパスカルの三角形のような図が浮かび上がってきたのでそれを利用してアセプト。
線対称で得られるCは規則的に並びます。
反射の途中で120億、、、回に達しないでCから出てしまう場合を排除して条件を満たす点を数え上げるだけです。
今のコードは答えをみてみよう程度の軽い気持ちで適当に書いたコード低速です。
後で12017639147の素因数分解を使って行う高速なコードに書きかえる予定。
#include<stdio.h>
#include<string.h>
#include<set>
#include<iostream>
__int64 GCD(__int64 a, __int64 b){
while( 1 ){
a = a % b;
if( a == 0 )return b;
b = b % a;
if( b == 0 )return a;
}
}
int main(){
const __int64 up=12017639147i64;
__int64 t,t2=1,p,r,herf,ans=0;
r=(up+3)/2;
herf=r/2+(r&1);
p=r%3==0?3:r%3==1?2:1;
std::cout<<up;
while(p<herf){
if(GCD(p,r)==1)ans++;
p+=3;
}
std::cout<<ans*2;
}
素因数分解してチェックを簡略化したら意外と速度が出た。
#include<stdio.h>
#include<string.h>
#include<set>
#include<iostream>
__int64 GCD(__int64 a, __int64 b){
while( 1 ){
a = a % b;
if( a == 0 )return b;
b = b % a;
if( b == 0 )return a;
}
}
int main(){
const __int64 up=12017639147i64;
__int64 t,t2=1,p,r,herf,ans=0;
r=(up+3)/2;
herf=r/2+(r&1);
p=r%3==0?3:r%3==1?2:1;
std::cout<<up<<" "<<p<<"\n";
while(p<herf){
if(p%5!=0 && p%11!=0 && p%17!=0 && p%23!=0 && p%29!=0 && p%41!=0 && p%47!=0) ans++;
p+=3;
}
std::cout<<ans*2;
}
問い203
同じ計算は二度しないというどんな単純労働でも当てはまる原則に従い、出てきた数字のリストを作ります。
後は判別関数で足しこむか判別するだけです。
判別関数は平方根の概念を使えばもう少し高速化出来る気もします。
#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;
}
問い208
７２度の弧を描きながら動くロボットが７０回動いてスタート地点に戻ってくる組み合わせを求めよという問題。
一度旋回すると５種類のベクトルのどれかの足し算が行われます。
右右旋回、右左旋回、左右旋回、左左旋回全てのパタンで移動をベクトルの係数として位置を計算してベクトルが打ち消し合う場合を引きながら計算します。
これを利用してメモ化計算で解いてみたら意外と組み合わせ数が少なかったので驚きました。
３５回目までの結果を利用すればもしかしたら計算量が落ちるかもしれません。
#include<stdio.h>
#include<map>
#include<iostream>
#include<algorithm>
int nextR[2][2][5]={ {{1,2,3,4,0},{1,0,4,3,2}},
{{1,0,4,3,2},{1,2,3,4,0}}};
int dxs[5][3]={ {1,0, 0},
{0,1, 0},
{0,0, 0},
{0,-1,0},
{-1,0,0}};
int dys[5][3]={ {1,0,0},
{0,1,0},
{0,0,1},
{0,1,0},
{1,0,0}};
const int left=0;
const int right=1;
struct robo{
int dxs[3],dys[3],dr,iti;
void reset(){
for(int i=0;i<3;i++)dxs[i]=dys[i]=0;
dr=left;
iti=0;
}
bool operator<(const robo& r)const{
for(int i=0;i<3;i++){
if(dxs[i]!=r.dxs[i])return dxs[i]<r.dxs[i];
if(dys[i]!=r.dys[i])return dys[i]<r.dys[i];
}
if(dr!=r.dr)return dr<r.dr;
return iti<r.iti;
}
void posCalc(){
int dell=std::min(dys[0]/2,std::min(dys[1]/2,dys[2]));
if(dys[0]>=dell*2&&dys[1]>=dell*2&&dys[2]>=dell){
dys[0]-=dell*2;
dys[1]-=dell*2;
dys[2]-=dell;
}
}
};
void addXY(robo& r,int oldPos,int sig){
for(int i=0;i<3;i++){
r.dxs[i]+=dxs[oldPos][i]*sig;
r.dys[i]+=dys[oldPos][i];
}
}
void print(robo r){
printf("(%d %d %d %d %d %d %d %d)",r.dxs[0],r.dxs[1],r.dxs[2],r.dys[0],r.dys[1],r.dys[2],r.iti,r.dr);
}
int main(){
robo r;
r.reset();
std::map<robo,__int64> memo,next;
std::map<robo,__int64>::iterator it;
memo[r]=1;
__int64 perm;
for(int i=0;i<70;i++){
for(it=memo.begin();it!=memo.end();it++){
r=(*it).first;
perm=(*it).second;
//print(r);
if(r.dr==left){
//printf("L%d ",perm);
//左左旋回
addXY(r,r.iti,1);
r.iti=nextR[left][left][r.iti];
r.dr=left;
r.posCalc();
if(next.find(r)==next.end())next[r]=0;
//print(r);
next[r]+=perm;
//左右旋回
r=(*it).first;
addXY(r,(r.iti+4)%5,1);
r.iti=nextR[left][right][r.iti];
r.dr=right;
r.posCalc();
if(next.find(r)==next.end())next[r]=0;
//print(r);
next[r]+=perm;
}else{
//右左旋回
//printf("R");
addXY(r,(r.iti+4)%5,-1);
r.iti=nextR[right][left][r.iti];
r.dr=left;
r.posCalc();
if(next.find(r)==next.end())next[r]=0;
//print(r);
next[r]+=perm;
//右右旋回
r=(*it).first;
addXY(r,r.iti,-1);
r.iti=nextR[right][right][r.iti];
r.dr=right;
r.posCalc();
if(next.find(r)==next.end())next[r]=0;
//print(r);
next[r]+=perm;
}
//printf("\n");
}
memo.clear();
memo.insert(next.begin(),next.end());
next.clear();
std::cout<<i<<" "<<memo.size()<<"\n";
}
robo r1,r2;
r1.reset();
r2.reset();
r1.dr=left;
r2.dr=right;
std::cout<<memo[r1]<<" "<<memo[r2]<<" "<<memo[r1]+memo[r2];
}
問い209
解法
論理学の授業を受けたことがなかったので何を問われているか最初わからなかった問題。
全ての(a,b,c,d,e,f)に対して条件を満たす真理値表の数を数える問題。
τ(a, b, c, d, e, f) AND τ(b, c, d, e, f, a XOR (b AND c)) = 0を満たすということは
a=b
b=c
c=d
d=e
e=f
f=a XOR (b AND c)
としてまた
τ(a, b, c, d, e, f) AND τ(b, c, d, e, f, a XOR (b AND c)) = 0を満たす必要がありこのチェーンは複数のグループに分かれて幸いなことに重複がありませんでした。
よって個別にチェーンを計算したら下記のコードとなりました。
問題が簡単すぎたらしくショートコード等で皆回答を工夫してるようです。
私は特に工夫もなく素朴にコードを書きました。
#include<stdio.h>
#include<string.h>
#include<vector>
#include<iostream>
int mask[6]={32,16,8,4,2,1};
int memo[65];
std::vector<int> list;
__int64 ans[10]={0};
int calcNext(int bits){
int b=(bits&mask[1])!=0;
int c=(bits&mask[2])!=0;
int a=(bits&mask[0])!=0;
int f=a^(b&c);
return ((bits<<1)&63)|f;
}
int main(){
int count=0,bits2;
memset(memo,-1,sizeof(memo));
for(int bits=0;bits<64;bits++){
if(memo[bits]==-1){
bits2=bits;
list.push_back(0);
while(memo[bits2]==-1){
memo[bits2]=count;
list[count]++;
bits2=calcNext(bits2);
}
count++;
}
}
__int64 ans=1;
__int64 tPerm[50]={0},fPerm[50]={0},t=1,f=0,t2,f2;
for(int i=1;i<50;i++){
t2=f;
f2=f+t;
t=t2;
f=f2;
tPerm[i]=t;
fPerm[i-1]=f;
}
for(int i=0;i<list.size();i++){
int p=list[i];
ans*=(tPerm[p]+fPerm[p]);
}
std::cout<<ans;
}
最終更新：2012年12月07日 17:24
