問い81
解法
一段ずつの動的計画法で一発です。
#include<stdio.h>
#include<string.h>
int main(){
int ans[81][81],num;
char c;
memset(ans,0,sizeof(ans));
for(int i=1;i<=80;i++){
for(int j=1;j<=80;j++){
scanf("%d%c",&num,&c);
if(i==1){
ans[i][j]=num+ans[i][j-1];
}else if(j==1){
ans[i][j]=num+ans[i-1][j];
}else{
ans[i][j]=num+(ans[i-1][j]<ans[i][j-1]?ans[i-1][j]:ans[i][j-1]);
}
}
}
printf("%d",ans[80][80]);
}
問い82
解法
この問題は特殊なグラフとみてダイクストラ法で解いてもいいのですが、尺取り虫法と動的計画法を組み合わせて解いてみました。
#include<stdio.h>
#include<string.h>
int main(){
int map[81][81],memo[81][81];
char c;
memset(map,0,sizeof(map));
memset(memo,0,sizeof(memo));
for(int i=1;i<=80;i++){
for(int j=1;j<=80;j++){
scanf("%d%c",&map[i][j],&c);
}
}
for(int col=1;col<=80;col++){
for(int row=1;row<=80;row++)memo[row][col]=memo[row][col-1]+map[row][col];
//上から下へ尺取り虫法
for(int row=2;row<=80;row++){
int num=memo[row-1][col]+map[row][col];
if(memo[row][col]>num)memo[row][col]=num;
}
//下から上へ尺取り虫法
for(int row=79;row>=1;row--){
int num=memo[row+1][col]+map[row][col];
if(memo[row][col]>num)memo[row][col]=num;
}
}
int ans=memo[1][80];
for(int row=1;row<=80;row++)if(ans>memo[row][80])ans=memo[row][80];
printf("%d",ans);
}
問い83
解法
流石にここら辺まで品雑になると素直にダイクストラ法で実装するのが楽です。
#include<stdio.h>
#include<queue>
struct S{
int num,row,col;
bool operator<(const S& s)const{
return num>s.num;//優先順位付きキューで小さい数字から出てくるように計算
}
};
int main(){
int map[81][81],memo[81][81];
std::priority_queue<S> qu;
char c;
memset(memo,0,sizeof(memo));
for(int i=1;i<=80;i++){
for(int j=1;j<=80;j++)scanf("%d%c",&map[i][j],&c);
}
S s,nextS;
s.row=s.col=1;
s.num=map[1][1];
qu.push(s);
int dxs[]={1,0,-1,0};
int dys[]={0,1,0,-1};
while(!qu.empty()){
s=qu.top();
qu.pop();
if(s.row==80&&s.col==80)break;
for(int i=0;i<4;i++){
int r=s.row+dys[i];
int c=s.col+dxs[i];
if(r<1||80<r||c<1||80<c)continue;
nextS.row=r;
nextS.col=c;
nextS.num=s.num+map[r][c];
if(memo[r][c]!=0&&memo[r][c]<=nextS.num)continue;
map[r][c]=nextS.num;
qu.push(nextS);
}
int t;
}
printf("%d",s.num);
}
問い85
解法
長方形の縦横をa,bとすると作れる長方形の数はa(a+1)b(b+1)/4個となります。
aが決まれば後はbに関する2次方程式なのでこれを解くだけです。
#include<stdio.h>
#include<math.h>
int main(){
int limit=2000*1000,sa,ans=limit,ansSa=limit;
for(double a=1;a*(a+1)*a*(a+1)<=limit*4;a+=1){
int b=(-1.0+sqrt(1.0+4.0*limit*4.0/(a*a+a)))/2.0;
int m=(a*(a+1)*b*(b+1))/4;
sa=m-limit;
if(sa<0)sa=-sa;
if(ansSa>sa){
ansSa=sa;
ans=a*b;
}
m=(a*(a+1)*(b+1)*(b+2))/4;
sa=m-limit;
if(sa<0)sa=-sa;
if(ansSa>sa){
ansSa=sa;
ans=a*(b+1);
}
}
printf("%d",ans);
}
問い87
解法
2乗、3乗、4乗は密度が低いので全ての組み合わせを試しても十分間に合います。
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
const int up=10000;
std::vector<__int64> sosuu2,sosuu3,sosuu4;
std::set<int> memo;
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;
sosuu2.push_back(4);
sosuu3.push_back(8);
sosuu4.push_back(16);
for(int i=3;i<=up;i+=2){
if(so[i]==false)continue;
if(i<7072)sosuu2.push_back(i*i);
if(i<369)sosuu3.push_back(i*i*i);
if(i<85)sosuu4.push_back(i*i*i*i);
i2=i*2;
for(int j=i*3;j<=up;j+=i2){
so[j]=false;
}
}
}
int main(){
setSo();
std::set<int> ans;
for(int i=0;i<sosuu2.size();i++){
for(int j=0;j<sosuu3.size();j++){
for(int k=0;k<sosuu4.size();k++){
int sum=sosuu2[i]+sosuu3[j]+sosuu4[k];
if(sum<5000*10000)ans.insert(sum);
}
}
}
printf("%d",ans.size());
}
最終更新:2013年01月04日 02:38