naoya_t@topcoder

Codeforces Beta Round #17 (Div.2)

22:17 |

• やってる事に気づき、途中から外野で問題を解いてみた。50分ぐらい
• これは自分のレーティング（lieutenant）だと参加できないのか？

A. Flag

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)
#define REP(var,ar)  for(int var=0,lim=(ar).size();var<lim;var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define all(c)  (c).begin(),(c).end()
#define found(s,e)  ((s).find(e)!=(s).end())

int main(){
  int n,m;cin>>n>>m;
  int lastline=-1;
  bool yn=true;
  rep(r,n){
    string s;cin>>s;
    int co=s[0];
    if(r>0 && co==lastline) { yn=false;goto ans;}
    FOR(c,1,m-1) if(s[c]!=co) {yn=false;goto ans;}
    lastline=co;
  }
 ans:
  cout << (yn ? "YES" : "NO") << endl;
  return 0;
}

B. Burglar and Matches

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)
#define REP(var,ar)  for(int var=0,lim=(ar).size();var<lim;var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define all(c)  (c).begin(),(c).end()
#define found(s,e)  ((s).find(e)!=(s).end())

int main(){
  int n,m;cin>>n>>m;
  vector<int> bs(11,0);
  rep(i,m){
    int ai,bi;cin >> ai >> bi;
    bs[bi] += ai;
  }
  int t=0;
  for(int j=10;j>=1;--j){
    if(bs[j]==0)continue;
    if(n==0)break;
    if(bs[j]>=n){
      t+=n*j; bs[j]-=n; n=0;
    } else {
      t+=bs[j]*j; n-=bs[j]; bs[j]=0;
    }
  }
  cout << t << endl;
  return 0;
}

C. Monitor

• 入力が2e9近い時、分数の演算をintでやると桁あふれする
• (x,y)=(2,4)のとき(1,2)と同様の結果を返さなくてはならない

int gcd(int m, int n)
{
  if (m == 0 || n == 0) return 0;
  if (m == 1 || n == 1) return 1;
  if (m == n) return m;
  while (1) {
    if (m == 0) return n;
    if (n == 0) return m;
    if (m > n) m %= n; else n %= m;
  }
}

int main(){
  int a,b,x,y; cin>>a>>b>>x>>y;
  int g=gcd(x,y); x/=g; y/=g;
  int r=min(a/x, b/y);
  cout << r*x << " " << r*y << endl;
  return 0;
}

D. Logging

• 分が同じ行は10行まで、という制約を見落としてた

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)
#define REP(var,ar)  for(int var=0,lim=(ar).size();var<lim;var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define all(c)  (c).begin(),(c).end()
#define found(s,e)  ((s).find(e)!=(s).end())

int main(){
  int n,ans;cin>>n;
  char buf[40]; cin.getline(buf,40);
  int lastm = 0, daych = 0, cnt=0;
  rep(i,n){
    cin.getline(buf,40);
    int hh = 10*(buf[1]-'0') + (buf[2]-'0'); if(hh==12) hh=0;
    int mm = 10*(buf[4]-'0') + (buf[5]-'0');
    if (buf[7]=='p') hh+=12;
    int m = hh*60 + mm;
    if (m==lastm) {
      cnt++; if (cnt>10) { daych++; cnt=1; }
    } else if (m < lastm) {
      daych++;
      lastm = m; cnt=1;
    } else {
      lastm = m; cnt=1;
    }
  }
  cout << 1+daych << endl;
  return 0;
}

E. Fish

• 確率問題。これは時間内に解けなくて放置。

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
• あとで見る