naoya_t@topcoder

Google Code Jam 2009: Round 2

過去問 | 19:38 |

• 去年のRound 2の問題を見てみた
• 去年は1758/3000位だったらしい。(500位で通過)
• しかし同じ問題だったらアウトな感じ

A. Crazy Rows

• [2,1,1,0] みたいな配列を [0,1,2,3] かそれ以下にするswapの回数。
• v[i]>iの場合、最初に手に入るi以下の数字を持ってくる。
• その繰り返し(0..N-1)でswap回数の和を取れば終わる

#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cctype>
using namespace std;

#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)

int main(){
  int T; cin >> T;//1..60
  rep(t,T){
    int N; cin >> N;//1..40
    vector<int> m(N,-1);
    rep(n,N){
      string s; cin >> s;
      rep(i,N) if(s[i]=='1')m[n]=i;
    }

    int k=0;
    rep(n,N){
      if (m[n]<=n) continue;
      for(int i=n+1;i<N;++i){
        int t=m[i];
        if(t<=n) { //n..)i
          k += i-n;
          for(int j=i;j>n;--j) m[j]=m[j-1];
          m[n] = t;
          break;
        }
      }
    }
    printf("Case #%d: %d\n", t+1, k);
  }
  return 0;
}

B. A Digging Problem

• あー。
• あとで見る

C. Stock Charts

• クロスないしタッチしてるかどうか見て、組分けの考えられる組み合わせを全て試す方法ではsmallならなんとか時間に間に合う。でもIncorrectだった。グラフ問題。最大フローとかで何とかなるような気がするんだけどどう解いたらよいか
• Contest Analysis読んだ。二部グラフの最大マッチングに落とせるので確かに最大フロー。
• すぱげってぃこーどからコピペしたmaximumFlowだと思った結果が出ない。確認のために自分で書いてみる（というか1年半前の自分からコピペ）

#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cctype>
using namespace std;

#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)

#define infty 987654321
int maximumFlow(const vector<vector<int> >& capacity, int s, int t) {
  int w = capacity.size();
  // residual networks
  vector<vector<int> > resid(w, vector<int>(w,0));
  for(int j=0; j<w-1; ++j){
    for(int k=j+1; k<w; ++k){
      resid[j][k] = capacity[j][k]; // = capacity[j][k] - flow[j][k]
      resid[k][j] = 0; // = flow[k][j]
    }
  }
  // find another way
  for (int total=0; ;++total) {
    bool another_way = false;
    vector<int> prev(w, infty);
    queue<pair<int,int> > q; q.push(pair<int,int>(s,-1));
    while (!q.empty()) {
      pair<int,int> p = q.front();
      int node = p.first, prev_node = p.second;
      q.pop();
      prev[node] = prev_node;
      if (node==t) { another_way = true; break; }
      rep(i,w) {
        if (resid[node][i] == 0) continue;
        if (prev[i] < infty) continue;
        q.push(pair<int,int>(i,node));
      }
    }
    // no more ways
    if (!another_way) return total;
    for (int node=t; node!=s; node=prev[node]) {
      int prev_node = prev[node];
      resid[prev_node][node]--;
      resid[node][prev_node]++;
    }
  }
  return 0;
}

int main(){
  int T; cin >> T;
  rep(t,T){
    int n, k; cin >> n >> k; // 1..100, 2..25
    vector<vector<int> > price(n,vector<int>(k));
    rep(j,n) rep(i,k) cin >> price[j][i]; //0..1e6
    vector<vector<bool> > dir(n,vector<bool>(n,false));

    int w=1+n+n+1;
    vector<vector<int> > capacity(w, vector<int>(w,0));
    rep(i,n) capacity[0][1+i] = 1;
    rep(i,n) {
      rep(j,n) {
        if (i==j) continue;
        bool x=true;
        rep(h,k) if (price[i][h] >= price[j][h]) { x=false; break; }
        if (x) capacity[1+i][1+n+j] = 1;
      }
    }
    rep(i,n) capacity[1+n+i][1+n+n] = 1;
    
    int maxflow = maximumFlow(capacity, 0, 1+n+n);
    int ans = n - maxflow;
    printf("Case #%d: %d\n", 1+t, ans);
  }
  return 0;
}

D. Watering Plants

• smallは簡単に解ける。問題はlarge
• あとで見る