問い181
問題文と２時間ほどにらめっこして到達した答え。
整数論の授業は人生で一度も受けたことがないのでまあ頑張ってアルゴリズムをひとりで考えてみた。
BWの組み合わせに番号を振って、黒白の石の数とセットを小さいほうからメモ化で積み上げていくコード。
memo[黒石の数][白石の数][この組でのBWのセットの最大値]であとはこれをメモ化を使いながら動的計画法でアセプト。
コード実行時間５秒。
まあまあだと思う。
必要のなさそうなループが一か所あるようなのでそこを削れれば今のコードより１０００倍くらい早くなるかも？
調べて解くより自分で考えて解く方が楽しいというのはプログラマ（プロアマとわず）としては完全に欠点だな。
プログラマは自分で考えるより調べて応用できる方が重要だもの、俺はプロのプログラマにはなれない。
#include<stdio.h>
#include<string.h>
#include<iostream>
const int bSize=60;
const int wSize=40;
const int hashSize=(bSize+1)*(wSize+1);
__int64 memo[bSize+1][wSize+1][hashSize+1];
void calc(int b,int w){
__int64 temp;
for(int i=1;i<hashSize;i++){
int b1=i/(wSize+1);
int w1=i%(wSize+1);
temp=0;
if(b>=b1&&w>=w1){
//解いただけでアップアップ状態だけど、このループ、ループなしで計算できるかも？
for(int j=0;j<=i;j++){
temp+=memo[b-b1][w-w1][j];
}
memo[b][w][i]=temp;
}
}
}
int main(){
memset(memo,0,sizeof(memo));
memo[0][0][0]=1;
__int64 ans=0;
for(int b=0;b<=bSize;b++){
for(int w=0;w<=wSize;w++){
calc(b,w);
}
}
for(int i=1;i<hashSize;i++){
ans+=memo[bSize][wSize][i];
std::cout<<memo[bSize][wSize][i]<<"\n";
}
std::cout<<ans;
}
問い185
Number Mind は, 有名なゲームMaster Mindの変種である.
色つきのペグの代わりに, 秘密の数字を推理する. 推理するごとに, 正しい桁がいくつあったかのみが伝えられる. つまり, 答えが1234で, 2036と推理した場合, 1つの桁が正しいと伝えられる. 数字は正しいが場所が違うということは伝えられない.
例えば, 以下の5桁の推理では,
90342 ;2 桁正しい
70794 ;0 桁正しい
39458 ;2 桁正しい
34109 ;1 桁正しい
51545 ;2 桁正しい
12531 ;1 桁正しい
答えの数字は39542の唯一つとなる.
以下の推理に基づいて,
5616185650518293 ;2 桁正しい
3847439647293047 ;1 桁正しい
5855462940810587 ;3 桁正しい
9742855507068353 ;3 桁正しい
4296849643607543 ;3 桁正しい
3174248439465858 ;1 桁正しい
4513559094146117 ;2 桁正しい
7890971548908067 ;3 桁正しい
8157356344118483 ;1 桁正しい
2615250744386899 ;2 桁正しい
8690095851526254 ;3 桁正しい
6375711915077050 ;1 桁正しい
6913859173121360 ;1 桁正しい
6442889055042768 ;2 桁正しい
2321386104303845 ;0 桁正しい
2326509471271448 ;2 桁正しい
5251583379644322 ;2 桁正しい
1748270476758276 ;3 桁正しい
4895722652190306 ;1 桁正しい
3041631117224635 ;3 桁正しい
1841236454324589 ;3 桁正しい
2659862637316867 ;2 桁正しい
16桁の唯一つの答えの数字を答えよ.
解法
賢い方法を思いつかなかったのでまずは答えだけもとめようと思い２重再帰の全探索で答えを求めてみました。
答えが一つであることを利用してsaiki関数の最後のcheck処理で少しずるをしています。
答えが複数になる場合はもう少し工夫が必要です。
#include<stdio.h>
#include<string.h>
void saiki(int deep,char commits[17]);
int size;
bool last=false;
int outs[17][10];
struct D{
char text[17];
int hit;
D(char t[17],int h){
for(int i=0;i<17;i++)text[i]=t[i];
hit=h;
}
};
D datas[]=
{
D("5616185650518293",2),
D("3847439647293047",1),
D("5855462940810587",3),
D("9742855507068353",3),
D("4296849643607543",3),
D("3174248439465858",1),
D("4513559094146117",2),
D("7890971548908067",3),
D("8157356344118483",1),
D("2615250744386899",2),
D("8690095851526254",3),
D("6375711915077050",1),
D("6913859173121360",1),
D("6442889055042768",2),
D("2321386104303845",0),
D("2326509471271448",2),
D("5251583379644322",2),
D("1748270476758276",3),
D("4895722652190306",1),
D("3041631117224635",3),
D("1841236454324589",3),
D("2659862637316867",2)
};
void saiki2(int deep,int p,char commits[17],int commit){
if(commit>datas[deep].hit)return;
if(p==16){
if(commit!=datas[deep].hit)return;
saiki(deep+1,commits);
return;
}
char c1=datas[deep].text[p],c2=commits[p];
if(c2=='a'){
if(outs[p][c1-'0']==0&&commit<datas[deep].hit){
commits[p]=c1;
saiki2(deep,p+1,commits,commit+1);
commits[p]='a';
}
if(last==true)return;
outs[p][c1-'0']++;
saiki2(deep,p+1,commits,commit);
outs[p][c1-'0']--;
}else{
if(c1==c2){
saiki2(deep,p+1,commits,commit+1);
}else{
saiki2(deep,p+1,commits,commit);
}
}
}
void check(char commits[17]){
for(int i=0;i<size;i++){
if(commits[i]=='a'){
for(int j=0;j<10;j++){
if(outs[i][j]==0)commits[i]='0'+j;
}
}
}
}
void saiki(int deep,char commits[17]){
if(deep>=size){
check(commits);
printf("ans=%s\n",commits);
last=true;
return;
}
//int a;
//printf("(%d %s)",deep,commits);
//scanf("%d",&a);
saiki2(deep,0,commits,0);
}
int main(){
size=sizeof(datas)/sizeof(D);
//printf("%s %d\n",datas[1].text,datas[1].hit);
char commits[17];
memset(commits,'a',sizeof(commits));
memset(outs,0,sizeof(outs));
commits[16]='\0';
saiki(0,commits);
}
問い186
今, 100万人のユーザをもつ電話システムの通信記録がある.
Rec Nr Caller Called
1 200007 100053
2 600183 500439
3 600863 701497
... ... ...
n番目の記録の掛けた側と掛けられた側の電話番号は Caller(n) = S2n-1 と Called(n) = S2nで与えられる. S1, S2, ...は“ラグ付きフィボナッチ生成器”で定義される.
1 ≤ k ≤ 55については, Sk = [100003 - 200003k + 300007k3] (modulo 1000000)
56 ≤ kでは, Sk = [Sk-24 + Sk-55] (modulo 1000000)である.
もしCaller(n) = Called(n)であれば, ユーザは間違って電話を掛けたとされ通信は切断される. そうでない場合には, 通信は成功している.
XがYに電話を掛けるかその逆のときに, ユーザXとユーザYが友達であると呼ぶ. 同様に, XがYの友達であるかつYがZの友達であるとき, XがZの友達の友達であると呼ぶ. 同様にして長い連鎖が得られる.
首相の電話番号は524287である. 何回電話を掛けると99%のユーザ (首相自身も含む) が首相の友達になるだろうか?
(注: 切断された通信は数えない.)
解法
ユニオン木の概念を使って問題を解きます。
電話がかかるたびに生成されていくフレンドリストのグラフを以下の要領で纏めていきます。
電話がかかった場合、番号が小さいか大統領の電話ならそちらの番号を新しいボスとしてユニオン木にまとめていきます。
統合された方は統合された方のボスのボスとして統合する方のボスを新しいボスとして上位者に設定し、人数の報告を聞きます。
これを繰り返せばそこそこの速度で計算が終わります。
#include<stdio.h>
#include<set>
#include<vector>
#include<iostream>
const int all=100*10000;
int callCount=0;
int friendCount[all+2],toBoss[all+2];
int presidentNo=524287;
void unionFriend(int call1,int call2){
if(call1==call2)return;
callCount++;
std::vector<int> friendChain[2];
while(1){
friendChain[0].push_back(call1);
if(toBoss[call1]==-1)break;
call1=toBoss[call1];
}
while(1){
friendChain[1].push_back(call2);
if(toBoss[call2]==-1)break;
call2=toBoss[call2];
}
if(call1==call2)return;
int changeBoss,bossNo;
if(call1==presidentNo||(call1<call2&&call2!=presidentNo)){
changeBoss=1;
bossNo=call1;
friendCount[call1]+=friendCount[call2];
friendCount[call2]=0;
}else if(call2==presidentNo || (call2<call1 && call1!=presidentNo)){
changeBoss=0;
bossNo=call2;
friendCount[call2]+=friendCount[call1];
friendCount[call1]=0;
}else{
//あり得ないが念のため
int a;
printf("code Error %d %d\n",call1,call2);
scanf("%d",&a);
}
for(unsigned int i=0;i<friendChain[changeBoss].size();i++){
toBoss[friendChain[changeBoss][i]]=bossNo;
}
}
int main(){
int S[60];
__int64 k,mod=all;
for(int i=0;i<=all;i++){
friendCount[i]=1;//自分自身と知り合い
toBoss[i]=-1;//まだi番の番号にボスはいない
}
for(k=1;k<=55;k++){
S[(int)k]=(100003 - 200003*k + 300007*k*k*k)%mod;
if(k%2==0){
unionFriend(S[(int)k],S[(int)k-1]);
}
}
int K=k-1;
while(friendCount[presidentNo]<99*10000){
K++;
S[K%56]=(S[(K-55)%56]+S[(K-24)%56])%mod;
if(K%2==0){
unionFriend(S[K%56],S[(K-1)%56]);
}
}
printf("%d",callCount);
}
問い187
解法
ええと余りよくないコードです。
何の工夫もなく全探索してるだけで遅いです。
一億くらいなら扱う数字も小さいからいけるかと思ったのですが意外と時間かかりました。
反面教師にしかならないコードですね。
#include<stdio.h>
#include<vector>
const int up=11000;
std::vector<int> sosuu;
bool so[up+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 check(int n){
int a,count=0;
for(int i=0;i<sosuu.size();i++){
a=sosuu[i];
while(n%a==0){
count++;
n/=a;
if(count>1)break;
}
if(count>1)break;
}
if(n!=1)count++;
return count==2;
}
int main(){
setSo();
int ans=0;
for(int n=1;n<10000*10000;n++){
ans+=(check(n));
}
printf("%d",ans);
}
問い188
1777↑↑1855の最後の8桁を求めよ.
人生で初めてみる演算子というか相変わらず整数論の教育を人生で一度も受けたことがなかったので、どんな概念かわからなかったのですが、とりあえず乗算の周期性を利用して３０分ほどひとりで考えてコードを書いて解いてみました。
整数論について知らず調べ物もせず書いたコードなので多分効率の悪いコードだと思う。
今のところコード実行時間は0.905秒。
#include<stdio.h>
#include<map>
#include<iostream>
#include<time.h>
__int64 size=1,mod=100000000;
std::map<int,int> toNum;
__int64 hp(__int64 a,__int64 k){
if(k==1)return a;
return toNum[(int)hp(a,k-1)%size];
}
int main(){
double start=clock();
__int64 a=1777,b=a*a;
toNum[0]=1;
while(b!=a){
b=(b*a)%mod;
size++;
}
b=1;
for(int no=0;no<size;no++){
toNum[no]=b;
b=(b*a)%size;
}
__int64 k=hp(a,1854);
b=1;
for(int i=0;i<k;i++)b=(b*a)%mod;
std::cout<<"ans="<<b<<" time="<<clock()-start;
}
問い189
解法
とりあえず一段ずつに分けての動的計画法でアセプト。
速度が出なかったので、一段の三角形の色を２ビットずつで扱う方法に切り替えてみたrgbでｒが0、ｇが１、ｂが２。
コード実行時間３０秒だからぎりぎり合格。
もしかしたら再帰と動的計画法を組み合わせたほうが早いかも。
#include<stdio.h>
#include<map>
#include<set>
#include<iostream>
#include<time.h>
int main(){
double start=clock();
std::map<__int64,__int64> board[9];
std::map<__int64,__int64>::iterator it;
std::set<__int64> now,next;
std::set<__int64>::iterator sIt;
board[0][0]=1;
__int64 t,t1,ans=0;
__int64 maskU,maskD;
__int64 r=0,g=1,b=2,r1=0,g1=4,b1=8;
now.insert(0);
now.insert(1);
now.insert(2);
maskU=0x3;
maskD=0xc;
for(int i=1;i<=7;i++){
for(sIt=now.begin();sIt!=now.end();sIt++){
t=(*sIt);
t1=t&3;
t=t<<4;
if(t1!=r){
next.insert(t|r1|g);
next.insert(t|r1|b);
}
if(t1!=g){
next.insert(t|g1|r);
next.insert(t|g1|b);
}
if(t1!=b){
next.insert(t|b1|r);
next.insert(t|b1|g);
}
}
for(it=board[i-1].begin();it!=board[i-1].end();it++){
__int64 pattern=(*it).first;
for(sIt=next.begin();sIt!=next.end();sIt++){
__int64 patternD=((*sIt)&maskD)>>2;
__int64 patternU=pattern&maskU;
bool out=false;
//なにかブール演算で一発判定とか行かないかな？
for(int j=0;j<i;j++){
if((patternU&3)==(patternD&3)){
out=true;
break;
}
patternU=patternU>>4;
patternD=patternD>>4;
}
if(out==true)continue;
if(board[i].find((*sIt))==board[i].end())board[i][(*sIt)]=0;
board[i][(*sIt)]+=(*it).second;
}
}
printf("%d ",board[i].size());
ans=0;
for(it=board[i].begin();it!=board[i].end();it++){
//std::cout<<(*it).second<<" ";
ans+=(*it).second;
}
std::cout<<"ans="<<(ans)*3<<"\n";
now.clear();
now.insert(next.begin(),next.end());
next.clear();
maskU=(maskU<<4)|0x3;
maskD=(maskD<<4)|0xc;
}
std::cout<<"time="<<clock()-start;
}
動的計画法と再帰探索を組み合わせてみた手法。
次の段の計算に必要なのはその段の奇数列目のみということに注目して速度アップ。
コードも短くシンプルになったし速度も１.903秒と上がったが、まだ不十分。
他の人のコードは眺めただけでまだ読んでないが１秒切るのが普通らしい。
この問題スクリプトで0.1秒を切ってる人たちはみてる世界が違う。
私は素朴に見えた世界でしか問題を解いてないような気がする。
まだまだ俺って実力ないな、、、
他の人のコードを見てなんとなく思いついたこと、もしかして私のコードsaiki関数のところで無駄な探索処理が繰り返されているってことか？
前の段の探索結果を再利用して計算結果を抑えろってことかも。
でもなんか実装が難しそうだな。
#include<stdio.h>
#include<map>
#include<set>
#include<iostream>
#include<time.h>
std::map<__int64,__int64> board[9];
std::map<__int64,__int64>::iterator it;
void saiki(__int64 patternU,__int64 nowPattern,int old,int col,int size,int row,__int64 add){
if(col==size){
if(board[row].find(nowPattern)==board[row].end())board[row][nowPattern]=0;
board[row][nowPattern]+=add;
return;
}
int bad1=old,bad2=-1;
if(col%2==1){
bad2=patternU&3;
patternU=patternU>>4;
}
nowPattern=nowPattern<<2;
for(int color=0;color<3;color++){
if(color==bad1||color==bad2)continue;
int c=(col%2==0)*color;
saiki(patternU,nowPattern|c,color,col+1,size,row,add);
}
}
int main(){
double start=clock();
board[0][0]=1;
for(int i=1;i<=7;i++){
for(it=board[i-1].begin();it!=board[i-1].end();it++){
saiki((*it).first,0,-1,0,i*2+1,i,(*it).second);
}
printf("%d ",board[i].size());
__int64 ans=0;
for(it=board[i].begin();it!=board[i].end();it++){
//std::cout<<(*it).second<<" ";
ans+=(*it).second;
}
std::cout<<" ans="<<(ans)*3<<"\n";
}
std::cout<<"time="<<clock()-start;
}
問い189解法３
ここから先は他の人のコードを参考にしてコードを書いてみました。
とりあえずRGBの色の対称性を利用して計算量を下げてみた。
コード実行時間0.575秒、１秒は切れたがmapが足をひっぱているためにこれ以上はstd::mapでは無理。
std::mapを隙間のない配列に変換すればもう少し速度が出そうです。
２段目がRGR、BDBだとこの二つはその後の組み合わせ数は同じとなります。
これを利用して以後同じパターンは纏めていきます。
#include<stdio.h>
#include<map>
#include<set>
#include<iostream>
#include<time.h>
std::map<int,__int64> board[9];
std::map<int,__int64>::iterator it;
std::map<int,int> sweep[9];
int changeColor[5][3]={{2,1,0},
{2,0,1},
{1,2,0},
{1,0,2},
{0,2,1}};
void unionSet(int pattern,int size,int row){
size=(size+1)/2;
for(int i=0;i<5;i++){
int p1=pattern,p2=0;
for(int c=0;c<size;c++){
int color=(p1>>(c*2))&3;
p2|=(changeColor[i][color])<<(c*2);
}
sweep[row][p2]=p1;
}
}
void saiki(int patternU,int nowPattern,int old,int col,int size,int row,__int64 add){
if(col==size){
if(sweep[row].find(nowPattern)!=sweep[row].end()){
board[row][sweep[row][nowPattern]]+=add;
return;
}
if(board[row].find(nowPattern)==board[row].end())board[row][nowPattern]=0;
board[row][nowPattern]+=add;
unionSet(nowPattern,size,row);
return;
}
int bad1=old,bad2=-1;
if(col%2==1){
bad2=patternU&3;
patternU=patternU>>2;
nowPattern=nowPattern<<2;
}
for(int color=0;color<3;color++){
if(color==bad1||color==bad2)continue;
int c=(col%2==0)*color;
saiki(patternU,nowPattern|c,color,col+1,size,row,add);
}
}
int main(){
double start=clock();
board[0][0]=1;
for(int i=1;i<=7;i++){
for(it=board[i-1].begin();it!=board[i-1].end();it++){
saiki((*it).first,0,-1,0,i*2+1,i,(*it).second);
}
printf("%d ",board[i].size());
__int64 ans=0,t=0;
for(it=board[i].begin();it!=board[i].end();it++){
//std::cout<<(*it).second<<" ";
ans+=(*it).second;
if(t<(*it).first)t=(*it).first;
}
std::cout<<" ans="<<(ans)*3<<" "<<t<<"\n";
}
std::cout<<"time="<<clock()-start;
}
最終更新：2012年11月17日 14:02
