競プロ今日の備忘録

問題を解いた上での気づき、反省を

AOJ_0042: At Boss's Expense

At Boss's Expense | Aizu Online Judge

DP。DPで列挙して判定するだけ。DPテーブルと値段を入れる配列をグローバル宣言する必要なかったなと反省。いちいち初期化しなきゃなの億劫だ。 素数テーブルは簡単に実装できた。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

bool prime[1000001],dp[1000001];

void make_prime(){
  for(int i=0;i<1000001;i++) prime[i]=true;
  prime[0]=prime[1]=false;
  for(int i=2;i<=1000000;i++){
    if(prime[i]){
      for(int j=i*2;j<1000001;j+=i){
          prime[j]=false;
        }
    }
  }
}

int n,x;
vector<int> price;

int main(){
  make_prime();

  while(1){
    cin>>n>>x;
    if(!n && !x)break;
    while(price.size())price.pop_back();
    for(int i=0;i<1000001;i++){
      dp[i]=false;
    }
    for(int i=0;i<n;i++){
      int tmp;
      cin>>tmp;
      price.push_back(tmp);
      dp[tmp]=true;
    }

    sort(price.begin(),price.end());

    for(int i=0;i<n;i++){
      for(int j=0;j+price[i]<=x;j++){
        if(dp[j]) dp[j+price[i]]=true;
      }
    }

    int ans=0;

    for(int i=x;i>=1;i--){
      if(dp[i] && prime[i]){
        ans=i; break;
      }
    }

    if(ans==0){
      cout<<"NA"<<endl;
    }else{
      cout<<ans<<endl;
    }
  }
  return 0;
}

AOJ_0042: A Thief

泥棒 | Aizu Online Judge

DP。ナップザック問題ほぼそのまま。 入力がうまくいかなかくて面倒だった。 scanf関数でまず仮変数に値を代入してから配列に渡すことで一応の解決を見せる。なんだったのだろうか。

#include <bits/stdc++.h>

using namespace std;

int cnt,W,N,v[1000],w[1000],dp[1001][1001];

int main(){
  while(1){
    scanf("%d",&W);
    if(W==0) break;
    cnt++;
    scanf("%d",&N);

    for(int i = 0;i <N;i++){
      int a,b;
      scanf("%d,%d",&b,&a);
      v[i] = b;
      w[i] = a;
    }


    for(int i=0;i<N;i++){
      for(int j=0;j<=W;j++){
        if(w[i]>j){
          dp[i+1][j]=dp[i][j];
        }else{
          dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
        }
      }
    }
    int ans_v=dp[N][W],ans_w=W;
    for(int i=W;i>=0;i--){
      if(dp[N][i]<ans_v) break;
      else{
        ans_w=i;
      }
    }

    printf("Case %d:\n%d\n%d\n",cnt,ans_v,ans_w);

    for(int i=0;i<1000;i++){
      w[i]=v[i]=0;
    }
    memset(dp,0,sizeof(dp));
  }
  return 0;
}

AOJ_0157: Russian Dolls

Russian Dolls | Aizu Online Judge

DPの練習。最長増加部分列問題。 昨日の問題↓rainline.hatenadiary.jp は数列の並び順が完全に固定されてたけれど、今日の問題はもともと数列ではなくその順番は可換なのでループの回し方が異なった。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

vector< pair<int,int> > doll;
int dp[200];
int n,m,tmp1,tmp2;

int main(){
  while(cin>>n && n){
    for(int i=0;i<n;i++){
      cin>>tmp1>>tmp2;
      doll.push_back(make_pair(tmp1,tmp2));
    }
    cin>>m;
    for(int i=0;i<m;i++){
      cin>>tmp1>>tmp2;
      doll.push_back(make_pair(tmp1,tmp2));
    }

    sort(doll.begin(),doll.end());

    int ans=0;

    for(int i=0;i<n+m;i++){
      dp[i]=1;
      for(int j=0;j<n+m;j++){
        if(doll[i].first>doll[j].first && doll[i].second>doll[j].second){
          dp[i]=max(dp[i],dp[j]+1);
        }
      }
      ans=max(ans,dp[i]);
    }

    cout<<ans<<endl;

    while(doll.size()) doll.pop_back();
    memset(dp,0,sizeof(dp));
  }
  return 0;
}

JOI春合宿2007: Building

http://www.ioi-jp.org/camp/2007/2007-sp-tasks/2007-sp-day2_21.pdf

DPの練習。最長増加部分列問題そのまま。 O(n2)解法で解いた。後でO(nlogn)解法も理解しておきたい。

#include <cstdio>
#include <algorithm>

using namespace std;

int n,b[1000],dp[1000];

int main(){
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",&b[i]);
  }
  int ans=0;

  for(int i=0;i<n;i++){
    dp[i]=1;
    for(int j=0;j<i;j++){
      if(b[i]>b[j]){
        dp[i]=max(dp[i],dp[j]+1);
      }
    }
    ans=max(ans,dp[i]);
  }

  printf("%d\n",ans);

  return 0;
}

AOJ_0557: A First Grader

1年生 | Aizu Online Judge

DPの練習。レギオでやったものだったので難なく実装できた。 int型配列でオーバーフローを起こしてしまった。値の見通しをもって実装していきたい。

#include <cstdio>

using namespace std;

int n,num[100];
long long int dp[100][21];

int main(){
  scanf("%d",&n);
  for(int i=0;i<n;i++) scanf("%d",&num[i]);
  dp[0][num[0]]=1;

  for(int i=1;i<n;i++){
    for(int j=0;j<21;j++){
      if(dp[i-1][j]!=0){
        if(0<=j+num[i] && j+num[i]<=20){
          dp[i][j+num[i]]+=dp[i-1][j];
        }
        if(0<=j-num[i] && j-num[i]<=20){
          dp[i][j-num[i]]+=dp[i-1][j];
        }
      }
    }
  }

  long long int ans=dp[n-2][num[n-1]];

  printf("%lld\n",ans);

  return 0;
}

AOJ_0168: Kannondou

Kannondou | Aizu Online Judge

DPの練習。さすがに方針は楽に立てられた。 また問題文を読み落とした（「一日に十回」の部分）。それで大幅なロスをしてしまった。 しっかり整理してから取り組むようにしなければならない。

#include <cstdio>

using namespace std;

int n,dp[34];

int main(){
  while(1){
    scanf("%d",&n);
    if(n==0) break;
    for(int i=0;i<34;i++) dp[i]=0;
    dp[0]=1;

    for(int i=0;i<n;i++){
      dp[i+1]+=dp[i];
      dp[i+2]+=dp[i];
      dp[i+3]+=dp[i];
    }

    
    int ans=(dp[n]/3650)+1;

    printf("%d\n",ans);

  }
  return 0;

}

POJ_1979: Red and Black

1979 -- Red and Black

深さ優先探索。 解けるかどうかの確認だけのつもりがコーディングがうまくいかなくて苦戦した。 よくある'='と'=='のミスである。 しないように努めたいし、したとしても異状が起きた時にすぐに気づけるようにしたい。

#include <cstdio>

using namespace std;

char dots[20][20];
int H=-1,W=-1,xs,ys,dx[4]={1,0,-1,0},dy[4]={0,-1,0,1},cnt,nx,ny;

void dfs(int y,int x){
  //if(dots[y][x]=='*') return;

  dots[y][x]='*';
  cnt++;
  for(int i=0;i<4;i++){
    if(0<=x+dx[i] && x+dx[i]<W && 0<=y+dy[i] && y+dy[i]<H && dots[y+dy[i]][x+dx[i]]=='.'){
      dfs(y+dy[i],x+dx[i]);
    }
  }
  return;
}

int main(){
  while(1){
    cnt=0;
    scanf("%d%d",&W,&H);
    if(H==0 && W==0) break;

    for(int i=0;i<H;i++){
      scanf("%s",&dots[i]);
    }

    for(int i=0;i<H;i++){
      for(int j=0;j<W;j++){
        if(dots[i][j]=='@'){
          xs=j; ys=i;
        }
      }
    }

    dfs(ys,xs);

    printf("%d\n",cnt);
  }

  return 0;
}