ProjectEuler/11-20

11

• 範囲外参照条件とか面倒なので番兵置いた。

  #include
  
  using namespace std;
  
  int n[26][26];
  
  int main(){
  	int ans=0;
  
  	for(int i=3;i<23;i++){
  		for(int j=3;j<23;j++){
  			cin >> n[i][j];
  		}
  	}
  	for(int i=3;i<23;i++){
  		for(int j=3;j<23;j++){
  			ans=max(n[i][j]*n[i][j+1]*n[i][j+2]*n[i][j+3],ans);
  			ans=max(n[i][j]*n[i+1][j+1]*n[i+2][j+2]*n[i+3][j+3],ans);
  			ans=max(n[i][j]*n[i+1][j]*n[i+2][j]*n[i+3][j],ans);
  			ans=max(n[i][j]*n[i-1][j+1]*n[i-2][j+2]*n[i-3][j+3],ans);
  		}
  	}
  	cout << ans << endl;
  	return 0;
  }

12

#include

using namespace std;

int main(){
	int ans=1,cnt=0;
	for(int i=2;;i++){
		ans+=i;
		cnt=2;
		for(int k=2;;k++){
			if(ans%k==0){
				if(k*k==ans) cnt+=1;
				else cnt+=2;
				if(ans<=k*k)break;
			}
		}
		if(cnt>=500)break;
	}
	cout << ans << endl;
	return 0;
}

13

• テキトーに桁分散

  #include
  
  using namespace std;
  
  int ans[60]; // 60桁あれば足りそう
  
  int main(){
  	char tmp;
  	int t;
  
  	for(int i=0;i<100;i++){
  		for(int k=0;k<50;k++){
  			do{
  				cin >> tmp;
  			}while( tmp==' ' || tmp=='\n' );
  			t=static_cast<int>(tmp-'0');
  			ans[49-k]+=t;
  		}
  	}
  	for(int k=0;k<59;k++){
  		if(ans[k]>9){
  			ans[k+1]+=(ans[k]/10);
  			ans[k]=ans[k]%10;
  		}
  	}
  	int s=59;
  	while(!ans[s])s--;
  	for(int k=s;k>s-10;k--){
  		cout << ans[k];
  	}
  	cout << endl;
  	return 0;
  }

14

• 400万未満で一度計算した数はメモ化した。メモ化しなかったら結構時間掛かりそう。
• 計算途中でint型超える。

  #include
  
  using namespace std;
  
  const int N_MAX = 1000000;
  int step[N_MAX*4];
  
  void calc(int i){
  	long long int k=i;
  	step[i]=1;
  	while(k!=1){
  		k=( k%2 ? 3*k+1 : k/2 );
  		if(k<N_MAX*4){
  			if(!step[k]) calc(k);
  			step[i]+=step[k];
  			break;
  		}
  		step[i]++;
  	}
  }
  
  int main(){
  	int ans_n=0,ans_step=0;
  	step[1]=1;
  	for(int i=2;i<=N_MAX;i++){
  		if(step[i]){ continue; }
  		calc(i);
  		if(step[i]>ans_step){
  			ans_step=step[i];
  			ans_n=i;
  		}
  	}
  	cout << ans_n << endl;
  	return 0;
  }

15

• int型超える

  #include
  
  using namespace std;
  
  long long int map[21][21];
  
  int main(){
  	map[0][0]=1;
  	for(int i=1;i<21;i++){
  		map[0][i]=1;
  		map[i][0]=1;
  	}
  	for(int i=1;i<21;i++){
  		for(int j=1;j<21;j++){
  			map[i][j]=map[i-1][j]+map[i][j-1];
  		}
  	}
  	cout << map[20][20] << endl;
  	return 0;
  }

16

• 桁分散。無駄はあるけど数が小さいので気にしない。

  #include
  #include
  
  using namespace std;
  
  int dig[500]; // このぐらい桁あれば足りそう
  int tmp[500]; // 繰り上がり
  
  int main(){
  	dig[0]=1;
  	for(int i=1;i<=1000;i++){
  		fill(tmp,tmp+500,0);
  		for(int k=0;k<499;k++){
  			dig[k]=dig[k]*2+tmp[k];
  			if(dig[k]>9){
  				tmp[k+1]=dig[k]/10;
  				dig[k]=dig[k]%10;
  			}
  		}
  	}
  	int ans=0;
  	for(int k=0;k<499;k++) ans+=dig[k];
  	cout << ans << endl;
  	return 0;
  }

17

めんどい

18

• N_MAXを100にするとProblem 67
• 番兵置いた
• DP的な

  #include
  
  using namespace std;
  
  const int N_MAX = 15;
  
  int data[N_MAX][N_MAX+2];
  int path[N_MAX][N_MAX+2];
  
  int main(){
  	int ans=0;
  	for(int i=0;i<N_MAX;i++){
  		for(int j=1;j<=i+1;j++){
  			cin >> data[i][j];
  		}
  	}
  	path[0][1]=data[0][1];
  	for(int i=1;i<N_MAX;i++){
  		for(int j=1;j<=i+1;j++){
  			path[i][j]=max(path[i-1][j-1],path[i-1][j]);
  			path[i][j]+=data[i][j];
  		}
  	}
  	for(int j=1;j<=N_MAX;j++) ans=max(ans,path[N_MAX-1][j]);
  	cout << ans << endl;
  	return 0;
  }

19

めんどい

20

• また桁分散
• 掛け算だけど、掛ける数が高々2桁なので楽
• 100は掛けても0が2つ増えるだけだからいらない

  #include
  #include
  
  using namespace std;
  
  int dig[500]; // このぐらい桁あれば足りそう
  int tmp[500];
  
  void mul(int n){
  	fill(tmp,tmp+500,0);
  	for(int i=0;i<499;i++) tmp[i+1]=dig[i]*n;
  	for(int i=0;i<499;i++){
  		tmp[i+1]+=tmp[i]/10;
  		dig[i]=tmp[i]%10;
  	}
  }
  
  int main(){
  	int ans=0;
  	dig[0]=1;
  	for(int i=2;i<=99;i++) mul(i);
  	for(int i=0;i<500;i++) ans+=dig[i];
  	cout << ans << endl;
  	return 0;
  }