JOI予選2007

1.おつり AOJ0521

#include<iostream>
#include<algorithm>
using namespace std;
#define INF ( 1 << 30 )
int main(){
  int dp[1000],tmp[]={500,100,50,10,5,1},n;
  fill_n(dp,1000,INF);
  dp[0] = 0;
  for(int i = 0 ; i < 1000 ; i++ ){
    for(int j = 0 ; j < 6 ; j++ ){
      if(i - tmp[j] >= 0) dp[i] = min(dp[i],dp[i-tmp[j]]+1);
    }
  }
  while(cin >> n , n) cout << dp[1000-n] << endl;
}

なんかDPで解きたくなったので解いた。

---

2.JOI and IOI AOJ0522

#include<iostream>
#include<string>
using namespace std;
int main(){
  string s;
  while(cin >> s){
    int joi = 0, ioi = 0;
    for(int i = 2 ; i < s.size() ; i++ ){
      if(s.substr(i-2,3) == "JOI") joi++;
      else if(s.substr(i-2,3) == "IOI") ioi++;
    }
    cout << joi << endl << ioi << endl;
  }
}

substrで良い感じに抜き出してやった。

---

問題3.カードゲーム AOJ0523

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int main(){
  int n, use[201], now, ban;
  while(cin >> n , n){
    priority_queue<int,vector<int>,greater<int> > TaHa[2];
    queue<int> tmp;
    fill_n(use,201,false),now = 0,ban = 0;
    for(int i = 0 ; i < n ; i++ ){
      int card;
      cin >> card;
      use[card] = true;
      TaHa[0].push(card);
    }
    for(int i = 1 ; i <= 2*n ; i++) if(!use[i]) TaHa[1].push(i);
    while(!TaHa[0].empty() && !TaHa[1].empty()){
      while(!TaHa[ban].empty() && now >= TaHa[ban].top()){
        tmp.push(TaHa[ban].top());
        TaHa[ban].pop();
      }
      if(!TaHa[ban].empty()) now = TaHa[ban].top() , TaHa[ban].pop();
      else now = 0;
      while(!tmp.empty()) TaHa[ban].push(tmp.front()) , tmp.pop();
      ban ^= 1;
    }
    cout << TaHa[1].size() << endl << TaHa[0].size() << endl;
  }
}

優先度付きキューで解いた。デフォルトが降順になっていることに気付かずバグらせた。
priority_queueは降順。覚えたい(戒め)

---

問題4.星座探し AOJ0524

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
#define fr first
#define sc second
typedef pair< int , int > Pt;
int m, n;
bool serach( Pt *a, Pt *b, int& x,int& y){
  for(int j = 1 ; j < m ; j++ ){
    if(!binary_search(b,b+n,Pt(a[j].fr+x,a[j].sc+y))) return false;
  }
  return true;
}
int main(){
  while(cin >> m , m){
    Pt M[m];
    for(int i = 0 ; i < m ; i++ ) cin >> M[i].fr >> M[i].sc;
    cin >> n;
    Pt D[n];
    for(int i = 0 ; i < n ; i++ ) cin >> D[i].fr >> D[i].sc;
    sort(D,D+n);
    for(int i = 0 ; i < n ; i++ ){
      int x = D[i].fr - M[0].fr , y = D[i].sc - M[0].sc;
      if(serach(M,D,x,y)){
        cout << x << " " << y << endl;
        break;
      }
    }
  }
}

2分探索すれば早く探せるんじゃね的な考え方。
STL用意されてて良い。

---

問題5.おせんべい AOJ0525

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  int h,w;
  bool mas[10][10000];
  while( cin >> h >> w , h ){
    for(int i = 0 ; i < h ; i++ ){
      for(int j = 0 ; j < w ; j++ ){
        cin >> mas[i][j];
      }
    }
    int ans = 0;
    for(int i = 0 ; i < (1 << h) ; i++ ){
      int sum = 0;
      for(int j = 0 ; j < w ; j++ ){
        int cnt = 0;
        for(int k = 0 ; k < h ; k++ ){
          cnt += mas[k][j]^(i>>k&1);
        }
        sum += max( h - cnt , cnt );
      }
      ans = max( sum , ans );
    }
    cout << ans << endl;
  }
}

行の制約10じゃん。やったね！
裏返すパターンを全通り試すしか無い。ちょっと端折った。

---

問題6.船旅 AOJ0526

#include<iostream>
#include<algorithm>
using namespace std;
#define INF ( 1 << 26 )
int main(){
  int n,m,DATA[101][101];
  while(cin >> n >> m , n){
    fill_n(DATA[0],101 * 101,INF);
    for(int i = 0 ; i < 101 ; i++ ) DATA[i][i] = 0;
    while(m--){
      int s, a, b, c;
      cin >> s >> a >> b;
      if(s){
        cin >> c;
        if(DATA[a][b] > c){
          DATA[a][b] = DATA[b][a] = c;
          for(int j = 1 ; j <= n ; j++){
            for(int k = 1 ; k <= n ; k++){
              DATA[j][k] = min(DATA[j][k] , DATA[j][a] + DATA[a][k]);
              DATA[j][k] = DATA[k][j] = min(DATA[j][k] , DATA[j][b] + DATA[b][k]);
            }
          }
        }
      }else cout << (DATA[a][b] == INF ? -1 : DATA[a][b]) << endl;
    }
  }
}

普通にWFやるといっちゃうので更新された所だけを更新する。O(n^2)くらいに出来る。