はやし屋

競技プログラミングのメモ きたない

JOI予選2009やってみた

ばぐるやばぐる

1.レシート AOJ 0543
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0543
なにして汚したんだろ

#include<cstdio>

int main(){
  for(int n;scanf("%d",&n)&&n;printf("%d\n",n))
    for(int t,i=9;i--;n-=t)scanf("%d",&t);
}

2.すごろく AOJ 0544
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0544
バグらせないように(いましめ)

#include<cstdio>
int main(){
  int n , m;
  while(scanf("%d%d",&n,&m)&&(n|m)){
    int mas[1111]={},go[1111];
    for(int i = 0 ; i < n ; ++i){
      scanf("%d",mas+i);
    }
    for(int i = 0 ; i < m ; ++i){
      scanf("%d",go+i);
    }
    int ret = 0,cur = 0;
    for(;cur < n-1;){
      cur += go[ret];
      cur += mas[cur];
      ret++;
    }
    printf("%d\n",ret);
  }
}

3.パーティー AOJ 0545
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0545
"入力例 2 において,あなたには友達はいない."
めっちゃbugbugしてた
落ち着きたい...

#include<cstdio>
int main(){
  int n , m;
  while(scanf("%d%d",&n,&m)&&(n|m)){
    bool g[555][555]={};
    bool ismyfr[555]={};
    for(int i = 0 ; i < m ; ++i){
      int a,b;scanf("%d%d",&a,&b);
      a--,b--;
      g[a][b] = g[b][a] = true;
    }
    int ret = 0;
    for(int i = 1 ; i < n ; ++i){
      if(g[0][i]){
	ismyfr[i] = true;
	for(int j = 1 ; j < n ; ++j){
	  ismyfr[j] |= g[i][j];
	}
      }
    }
    for(int i = 1 ; i < n ; ++i)ret += ismyfr[i];
    printf("%d\n",ret);
  }
}

4. カード並べ AOJ 0546
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0546
いろんな解法があるやつ
さ↑い↓き↑でやった

#include<cstdio>
#include<sstream>
#include<map>
using namespace std;
string itos(int v) {stringstream ss;ss<<v;return ss.str();}
map < string , bool > mp;
int n , k;
int data[11];
bool used[11];
 
void solve(int depth , string now){
  if(depth == k){
    mp[now];
    return ;
  }
  for(int i = 0 ; i < n ; ++i){
    if(!used[i]){
      used[i] = true;
      solve(depth+1,now+itos(data[i]));
      used[i] = false;
    }
  }
}
 
int main(){
  while(scanf("%d%d",&n,&k)&&(n|k)){
    mp.clear();
    for(int i = 0; i < n ; ++i){
      scanf("%d",data+i);
      used[i] = false;
    }
    solve(0,"");
    printf("%d\n",mp.size());
  }
}

5.通勤経路 AOJ0546
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0547
うまく数え上げる

#include<cstdio>
#define MOD 100000
int lis[111][111];
int dp[111][111][2];

void calc(){
  for(int i = 1 ; i < 111 ; ++i)
    for(int k = 0 ; k < 2 ; ++k)
    dp[i][1][k] = dp[1][i][k] = 1;
  
  for(int i = 2 ; i < 111 ; ++i){
    for(int j = 2 ; j < 111 ; ++j){
      dp[i][j][0] = (dp[i][j-1][0]+dp[i-2][j][1])%MOD;
      dp[i][j][1] = (dp[i-1][j][1]+dp[i][j-2][0])%MOD;
    }
  }
  for(int i = 1 ; i < 111 ; ++i)
    for(int j = 1 ; j < 111 ; ++j)
      lis[i][j] = (dp[i][j-1][0] + dp[i-1][j][1])%MOD;
}

int main(){
  int w , h;
  calc();
  while(scanf("%d%d",&w,&h)&&(w|h)){
    printf("%d\n",lis[h][w]);
  }
}

6.方向音痴のトナカイ AOJ0548
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0548
TLEすんじゃねとか思って触れなかった問題
遡ると状態数が減る
頭を整理してからやろう(いましめ)
ろくに眠ってなくてバグった(言い訳)

#include<cstdio>

int w , h;

int stage[11][11];

int sx,sy;

int dy[] = {0,-1,0,1};
int dx[] = {-1,0,1,0};

bool isover(int y , int x){
  return (y < 0 || x < 0 || x >= w || y >= h);
}

int solve(int y , int x , int ie){
  if(!ie){
    return (sx == x || sy == y);
  }
  int ret = 0;
  for(int i = 0 ; i < 4 ; ++i){
    int nx = x , ny = y;
    for(;;){
      nx += dx[i];
      ny += dy[i];
      if(isover(ny,nx))break;
      if(stage[ny][nx] == 1){
	stage[ny][nx] = -1;
	ret += solve(ny,nx,ie-1);
	stage[ny][nx] = 1;
	break;
      }
    }
  }
  return ret;
}

int main(){
  while(scanf("%d%d",&w,&h)&&(w|h)){
    int ie = 0;
    for(int i = 0 ; i < h ; ++i){
      for(int j = 0 ; j < w ; ++j){
	scanf("%d",stage[i]+j);
	if(stage[i][j] == 1)ie++;
	if(stage[i][j] == 2)sy = i , sx = j;
      }
    }
    printf("%d\n",solve(sy,sx,ie));
  }
}

感想
・バグりやすい回だった
・ねむかった