JOI2008 予選

タイムカード

---

秒に直して割ったり余りを求めたりして頑張る。

#include<iostream>
using namespace std;
int main(){
  int h1, m1, s1, h2, m2, s2;
  while(cin >> h1 >> m1 >> s1 >> h2 >> m2 >> s2){
    int tim = h2 * 3600 + m2 * 60 + s2 - h1 * 3600 - m1 * 60 - s1;
    cout << tim / 3600 << " " << tim % 3600 / 60 << " " << tim % 60 << endl;
  }
}

コンテスト

---

普通にやった。

#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
using namespace std;
int main(){
  vector< int > A(10),B(10);
  for(int i = 0 ; i < 10 ; i++ ) cin >> A[i];
  for(int i = 0 ; i < 10 ; i++ ) cin >> B[i];
  sort(A.rbegin(),A.rend());
  sort(B.rbegin(),B.rend());
  cout << accumulate(A.begin(),A.begin()+3,0) << " "
       << accumulate(B.begin(),B.begin()+3,0) << endl;
}

連鎖

---

ちょっと頭使った。とりあえず全通り試す方針で、上へ下へと広げて連鎖をチェックする方針でいった。

#include<iostream>
#include<algorithm>
using namespace std;
#define INF ( 1 << 30 )
int n, d, ret, chain[10000];
int solve(int left){
  int right = left + 1, all = n;
  while(true){
    int color = chain[left], dis = 0;
    while( chain[left] == color && left >= 0 && ++dis ) left--;
    while( chain[right] == color && right < n && ++dis ) right++;
    if(dis < 4) return all;
    all -= dis;
  }
}
int main(){
  while(cin >> n, n){
    int ret = INF;
    for(int i = 0 ; i < n ; i++ ) cin >> chain[i];
    for(int i = 0 ; i < n ; i++ ){
      for(int j = 1 ; j < 4 ; j++ ){
        swap( chain[i], j);
        ret = min( ret, solve( i));
        swap( chain[i], j);
      }
    }
    cout << ret << endl;
  }
}

薄氷渡り

---

DFSでやったらすぐできた。

#include<iostream>
#include<algorithm>
using namespace std;
const int dy[] = { 1, 0, 0, -1}, dx[] = { 0, -1, 1, 0};
int h, w, mas[90][90];
bool used[90][90];
int dfs( int y, int x){
  if(used[y][x] || !mas[y][x]) return 0;
  used[y][x] = true;
  int ret = 0;
  for(int i = 0 ; i < 4 ; i++ ){
    int ny = y + dy[i], nx = x + dx[i];
    if(ny >= 0 && ny < h && nx >= 0 && nx < w){
      ret = max( ret, dfs( ny, nx) + 1);
    }
  }
  used[y][x] = false;
  return ret;
}
int main(){
  while(cin >> h >> w, h){
    for(int i = 0 ; i < h ; i++ ){
      for(int j = 0 ; j < w ; j++ ){
        cin >> mas[i][j];
      }
    }
    int ret = 0;
    for(int i = 0 ; i < h ; i++ ){
      for(int j = 0 ; j < w ; j++ ){
        ret = max( ret, dfs( i, j));
      }
    }
    cout << ret << endl;
  }
}

シャッフル

---

カードの枚数が10^9なので普通にやったら間に合わないのは自明。
シャッフルの回数が5000回以下なので,[始まりの番号,終わりの番号]を
pairで持たせて凄く頑張って実装すればできる気がする(震え声)。
どう考えてもバグって詰むのも自明だけど仕方ない。

#include<iostream>
#include<queue>
#include<map>
using namespace std;
#define fr first
#define sc second
typedef pair< int , int > P;
int n, m;
deque< P > d;
int _sum(P p){
  return p.sc - p.fr + 1;
}
int query(int& p,int& q,int& r){
  int ret = 0, ans = 0;
  while(ret + _sum(d.front()) < p){
    ret += _sum(d.front());
    d.pop_front();
  }
  if(ret != p - 1) d.front().fr += p - ret;
  ret = p;
  while(ret + _sum(d.front()) <= q){
    if(d.front().sc <= r) ans += _sum(d.front());
    else if(d.front().fr <= r) ans += _sum(P(d.front().fr,r));
    ret += _sum(d.front());
    d.pop_front();
  }
  if(!d.empty() && ret != q){
    P p = P(d.front().fr,d.front().fr + q - ret - 1);
    if(p.sc <= r) ans += _sum(P(p.fr,p.sc));
    else if(p.fr <= r) ans += _sum(P(p.fr,r));
  }
  return ans;
}
void shuffle(int* xy){
  deque< P > tmp[2];
  int ret = 0;
  for(int i = 0 ; i < 2 ; i++ ){
    while( ret + _sum(d.front()) <= xy[i]){
      tmp[i].push_back(d.front());
      ret += _sum(d.front());
      d.pop_front();
    }
    if(ret != xy[i]){
      tmp[i].push_back(P(d.front().fr,d.front().fr + xy[i] - ret - 1));
      d.front().fr = d.front().fr + xy[i] - ret;
      ret = xy[i];
    }
  }
  d.insert(d.end(),tmp[1].begin(),tmp[1].end());
  d.insert(d.end(),tmp[0].begin(),tmp[0].end()); 
}
int main(){
  while(cin >> n , n){
    cin >> m;
    d.push_back( P( 1, n));
    int p, q, r;
    cin >> p >> q >> r;
    while(m--){
      int xy[2];
      cin >> xy[0] >> xy[1];
      shuffle(xy);
    }
    cout << query(--p, q, r) << endl;
    d.clear();
  }
}

ビンゴ

---

上から下,左から右に向かって数字が大きくなっていることを利用する。
dp[今いる場所][今いる場所までの合計] = パターンの数

#include<iostream>
using namespace std;
int main(){
  int N, M, S, dp[51][3001];
  while(cin >> N >> M >> S , N){
    fill_n(*dp,51*3001,0);
    dp[0][0] = 1;
    for(int i = 1 ; i <= M ; i++ ){
      for(int j = N * N ; j ; j-- ){
        for(int k = i ; k <= S ; k++ ){
          dp[j][k] = (dp[j][k] + dp[j-1][k-i]) % 100000;
        }
      }
    }
    cout << dp[N*N][S] << endl;
  }
}