はやし屋

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

JOI予選2007やってみた

勝 利

1.おつり AOJ0521
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0521
テーブル作らずできないかなーでやったら出来た

#include<cstdio>
int main(){
  int n;
  while(scanf("%d",&n)&&n){
    int ch = 1000-n,ret = 0;
    for(int i = 1 ; i < 1000 ; i*=10){
      int cur = ch/i%10;
      ret += cur / 5;
      ret += cur % 5;
    }
    printf("%d\n",ret);
  }
}

2.JOIとIOI AOJ0522
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0522
STLを使いたかった

#include<string>
#include<iostream>

using namespace std;

int calc(string t , string s){
  int ret = 0;
  for(int p = 0; ~(p=s.find(t,p)) ; ++p)ret++;
  return ret;
}

int main(){
  string s;
  while(cin >> s){
    cout << calc("JOI",s) << endl;
    cout << calc("IOI",s) << endl;
  }
}

3.カードゲーム AOJ0523
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0523
いい感じにシミュレーション

#include<cstdio>
int main(){
  int n ;
  while(scanf("%d",&n)&&n){
    bool c[2][222] = {};
    for(int i = 0 ; i < n ; ++i){
      int t;scanf("%d",&t);
      c[0][t]=true;
    }
    for(int i = 1 ; i <= 2*n ; ++i)if(!c[0][i])c[1][i]=true;
    int pl[2] = {n,n};
    int cur = 1 , now = 0;
    while(pl[0]&&pl[1]){
      for(;cur <= 2*n;++cur){
	if(c[now][cur]){
	  pl[now]--;
	  c[now][cur] = false;
	  break;
	}
      }
      if(cur == 2*n+1){
	cur = 1;
      }
      now^=1;
    }
    printf("%d\n%d\n",pl[1],pl[0]);
  }
}

4.星座さがし AOJ0524
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0524
解法すぐ思いついたけどnとm逆であること気づかなくて時間かけた

#include<cstdio>
int main(){
  int n,m;
  while(scanf("%d",&n) && n){
    int nx[1111],ny[1111];
    int mx[1111],my[1111];
    for(int i = 0 ; i < n ; ++i){
      scanf("%d%d",nx+i,ny+i);
    }
    scanf("%d",&m);
    for(int i = 0 ; i < m ; ++i){
      scanf("%d%d",mx+i,my+i);
    }
    int diffx , diffy;
    for(int i = 0 ; i < m ; ++i){
      int cnt = 0;
       diffy = my[i] - ny[0];
       diffx = mx[i] - nx[0];
      for(int j = 0 ; j < n; ++j)
	for(int k = 0 ; k < m ;++k)
	  if(mx[k] == nx[j] + diffx)
	    if(my[k] == ny[j] + diffy)
	      cnt++;
      if(cnt == n)break;
    }
    printf("%d %d\n",diffx,diffy);
  }
}

5.おせんべい AOJ0525
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0525
ビット臭かったので適当にやったら出来た
一発でコンパイル通って一発でACして嬉しい
が、後から見ると変数の意味がぐちゃぐちゃになってた

#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
  int w , h;
  while(scanf("%d%d",&h,&w)&&(w|h)){
    int stage[11111] = {};
    for(int i = 0 ; i < h ; ++i){
      for(int j = 0 ; j < w ; ++j){
	int t;scanf("%d",&t);
	stage[j] |= t << i;
      }
    }

    int ret = 0;
    for(int bit = 0 ; bit < 1 << h ; ++bit){
      int cnt = 0;
      for(int i = 0 ; i < w ; ++i){
	int bit1 = stage[i] ^ bit;
	int bit2 = __builtin_popcount(bit1);
	cnt += max(bit2,h-bit2);
      }
      ret = max(ret,cnt);
    }
    printf("%d\n",ret);
  }
}


6.船旅 AOJ0526
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0526
全点対最短路問題
ワーシャルフロイドでやったことなかったからやってみた。
1sで、5000回聞かれ、愚直ワーシャルフロイドO(100^3)やるとTLEするから少し工夫して、
聞かれたとこだけ回すことにする。これでワーシャルフロイドのオーダーO(100^2)ぐらいになった。
オーダー減らしはこれだけで十分。

#include<cstdio>
#define min(a,b) ((a)<(b)?(a):(b))
#define INF (1<<20)

int main(){
  int n , Q;
  int wf[111][111];
  while(scanf("%d%d",&n,&Q)&&(n|Q)){
    for(int i = 0 ; i < 111 ; ++i){
      for(int j = 0 ; j < 111 ; ++j)
	wf[i][j] = INF;
      wf[i][i] = 0;
    }
    while(Q--){
      int type ,a , b;
      scanf("%d%d%d",&type,&a,&b);
      a--,b--;
      if(type){
	int cost ;
	scanf("%d",&cost);
	wf[a][b] = wf[b][a] = min(wf[b][a],cost);
	for(int i = 0 ;i < n ; ++i)
	  for(int j = 0 ; j < n ; ++j){
	    wf[i][j] = min(wf[i][j] ,wf[i][a]+wf[a][b]+wf[b][j]);
	    wf[i][j] = min(wf[i][j] ,wf[i][b]+wf[b][a]+wf[a][j]);
	  }
      } else printf("%d\n",wf[a][b]!=INF?wf[a][b]:-1);
    }
  }
}

感想
・変数間違えやすいマン
・6問目はDijkstraの方がわかりやすいと思った。
・眠い中でやったのでバグらせまくった。
・安定したい