naoya_t@topcoder

Google Code Jam 2010 Round 1C

22:01 |

5/23 6pm〜

1Bで通ったので観戦モード（と言いつつ問題を解く）。

外出先から戻って18:25からのスタート。

時間内に3問とも解けた。終了後、practiceのデータを通したらC-large以外は全部通った。76点相当。実行時間＋submitの手間を考慮しても141〜142位あたりで通過。

ていうか何でC-large通らなかったんだ？（後述）

A. Rope Intranet 18:32 (0:07)

• こういうの最近見た気がします
• あれだ。一昨日のSRM470 Div1 Medium
• バブルソートの回数でおｋ

#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 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),till=(to);var<=till;var++)
#define all(c)  (c).begin(),(c).end()
#define rall(c)  (c).rbegin(),(c).rend()

#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> ii;

int main(){
  int T; cin >> T;
  rep(t,T){ // 15
    int N; cin >> N;
    vector<ii> wire(N);
    rep(n,N){
      int a, b; cin >> a >> b;
      wire[n] = ii(a,b);
    }
    sort(all(wire));
    int s=0;
    rep(n,N){
      rep(i,n) {
        if(wire[n].second<wire[i].second)s++;
      }
    }
    printf("Case #%d: %d\n", 1+t, s);
  }
  return 0;
}

B. Load Testing 18:48 (0:23)

皆さん題意がつかめずに苦労されていたようですが…

負荷テストを何度かやって、サーバがどこまでの負荷に耐えられるか知りたい。（求める負荷は厳密な数字ではなく）a≦x≦a*C みたいな範囲でわかればいい。あと何回負荷テストをしたら、要求する狭さで範囲が求まるか。

• 対数空間で二分探索する感じ。logの底がC、みたいな。
  • たぶん答えは ceiling( log_2( log_C( P/L ) ) ) みたいな値

int main(){
  int T; cin >> T;
  rep(t,T){
    int l,p,c; cin >> l >> p >> c; // 1<=L<P<=1e9, C:2..10
    double x = log((double)p/l)/log((double)c);
    int ans = max(0, (int)ceil(log(x)/log(2.0)));
    printf("Case #%d: %d\n", 1+t, ans);
  }
  return 0;
}

• これで答えがあうよ
• でもチキンなので整数演算で書きました

// #include,#defineの内容はA,B,C共通なので省略
typedef pair<int,int> ii;
typedef long long ll;

int main(){
  int T; cin >> T;
  rep(t,T){
    int l,p,c; cin >> l >> p >> c; // 1<=L<P<=1e9, C:2..10
    ll L=l, P=p, C=c;
    int ans;
    if (P <= L*C) {
      ans = 0;
    } else {
      ans=1;
      for(ll j=L,m=C*C; j*m<P; m*=m)
        ans++;
    }
    printf("Case #%d: %d\n", 1+t, ans);
  }
  return 0;
}

C. Making Chess Boards 19:40 (1:15)

与えられた白黒パターンの木版からチェス盤（というか市松模様）を切り出す問題。

大きい順、上から、左から、と明確に優先順位があるので一意に求まる。計算量だけの問題か。

• ある升目（行r,列c）から右にどれだけ市松模様が続いているか、をO(1)で分かるようにしておいて
• (r,c)を左上、(r+w-1,c+w-1)を右下とする幅w高さwの正方形を切り出したら市松模様になっているかの判定は、正方形の左端各行(r+i,c)からw以上市松模様が続いていることと、左端各行の色が交互に白黒白黒…となっていること
• 切り出した場所については、市松模様が続いていないのがわかる数字を設定しておけばよい（※ここでバグった）

// #include,#defineの内容はA,B,C共通なので省略
typedef pair<int,int> ii;

inline int unhex(char c){
  if (c<='9') return c-'0';
  else return c-'A'+10;
}

int main(){
  int T; cin >> T;
  rep(t,T){
    int M,N; cin >> M >> N; // それぞれ４の倍数; 1-512/512
    vector<vector<int> > bt(M,vector<int>(N,0));
    vector<vector<int> > pt(M,vector<int>(N,0));
    rep(m,M) {
      string s; cin >> s;
      rep(i,N/4){
        int c=unhex(s[i]);
        for(int j=0,mk=8;j<4;j++,mk>>=1){
          //if (i*4+j >= N) cout << "err" << endl;
          bt[m][i*4+j] = (c & mk)?1:0;
        }
      }
      int cont=0, last=bt[m][N-1];
      for(int i=N-1; i>=0; i--){
        if (bt[m][i]==last) {
          pt[m][i] = cont = 1;
        } else {
          pt[m][i] = ++cont;
        }
        last = bt[m][i];
      }
    }

    int maxw=min(M,N), rest=M*N;
    vector<int> ks(maxw+1,0);
    for(int w=maxw; w>1; w--){
      for(int sy=0; sy<=M-w; sy++) {
        for(int sx=0; sx<=N-w; sx++) {
          if (pt[sy][sx] < w) continue;
          bool ok=true;
          for(int r=1,po=bt[sy][sx]; r<w; r++){
            int y=sy+r;
            if (pt[y][sx] < w || bt[y][sx]==po) { ok=false; break; }
            po = 1 - po;
          }
          if (ok) { // take it
            ks[w]++; rest -= w*w;
            rep(r,w) {
              int y=sy+r;
              rep(c,w){
                pt[y][sx+c] = 0;
              }
              if (sx==0) continue;
              int b=pt[y][sx-1];
              for (int x=sx-1; x>=0; x--){
                if (pt[y][x]==1) break; ///OOPS
                pt[y][x]-=b-1; //printf("  (%d,%d)-%d=%d¥n", x,y,b, pt[y][x]);
              }
            }
          }
        }
      }
    }
    ks[1] = rest;

    vector<ii> res;
    for(int w=1; w<=maxw; w++) {
      if (ks[w] > 0) res.pb(ii(w,ks[w]));
    }
    reverse(all(res));

    int K=sz(res);
    printf("Case #%d: %d¥n", t+1, K);
    rep(k,K) {
      printf("%d %d¥n", res[k].first, res[k].second);
    }
  }
  return 0;
}

C-large (practice) を通しても1秒で終わる。しかしincorrectだ…オーバーフローは無いはずだし何でだろうと思ってソースを見返したら

                if (pt[y][x]==1) break;

がおかしい。既にチェス盤を切り出した所であれば0になっているはずだしそれならbreakしてほしい。

                if (pt[y][x]<=1) break;

が正しい。これでC-largeも通った。（C-smallが通ったのは偶然だろう）

というわけで皆さんお疲れ様でした。次はRound 2でお会いしましょう。