naoya_t@topcoder

GCJ2001 QR参戦メモ

00:40 |

Google Code Jam 2011 - Qualification Round

http://code.google.com/codejam

（naoya.t さんで出ています）

競技やるの半年ぶりぐらいでしょうか…

10時過ぎに起きて参戦した時には既に100点の人が沢山。

（ディレクトリのタイムスタンプによると5/7 10:20am頃）

Aから順に解いていく。C++。最初からLarge通すつもりで考えた。

A. Bot Trust

• シミュレーション
• なんか1発でサンプルが通るやつが書けたけど（たぶん4問のうちで一番）慎重に見直した、というかprintfデバッグ
• small通った！（4分制限なんて前もあったっけ）
• largeもスムーズに結果が出た（←解答の正しさを保証するものではないが）。投稿。入力ファイルの方を間違って添付してないか不安になったので8分制限の内にもう一度投稿。

#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 popcount  __builtin_popcount
#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 tr(c,i)  for(__typeof__((c).begin()) i=(c).begin(),till=(c).end(); i!=till; i++)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))

typedef vector<int> Vi;
typedef vector<vector<int> > VVi;

typedef pair<int,int> ii;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)
#define caar(x) (x).first.first
#define cdar(x) (x).first.second
#define cadr(x) (x).second.first
#define cddr(x) (x).second.second

//#include "cout.h"
int solve(const vector<ii>& seq)
{
  int N = seq.size(); int t=0;
  int pos[2] = { 1, 1 }, dur[2] = { 0, 0 };
  rep(n,N){
    t++;
    int r=seq[n].first;
    int p=seq[n].second;
    int dis=abs(pos[r]-p); 
//    printf("Time=%d; (%d±%d %d±%d), %c to %d, dist %d\n",
//            t, pos[0],dur[0], pos[1],dur[1], r?'B':'O', p, dis);
    if (dis <= dur[r]){
      // put
      pos[r]=p;
      dur[r]=0; dur[1-r]++;
//      printf("  ... can push at %d. now (%d±%d, %d±%d)\n",
//             t, pos[0],dur[0], pos[1],dur[1]);
    }else{
      // need to wait
      int wait=dis-dur[r];
      t += wait;
      pos[r]=p;
      dur[r]=0; dur[1-r]+=1+wait;
//      printf("  ... can push at %d (waiting %d). now (%d±%d, %d±%d)\n",
//             t, wait, pos[0],dur[0], pos[1],dur[1]);
    }
  }
  return t;
}

int main(){
  int T;cin>>T;
  rep(t,T){
    int N;cin>>N;
    vector<ii> seq(N);
    rep(n,N){
      char r;int p; cin>>r>>p;
      seq[n] = make_pair(r=='B', p);
    }
    printf("Case #%d: %d\n", 1+t, solve(seq));
  }
  return 0;
}

B. Magicka

• やるだけ書くだけシミュレーション
• 2字の組み合わせは順不同なのでmapに逆順も入れておく的な
  • map<pair<char,char>,char> とかしてみたけど別にmap<string,char>とかでも
• small通った。
• largeもスムーズに投稿。

//(略)
typedef pair<char,char> cc;
#define cons(x,y) make_pair((x),(y))

int main(){
  int T;cin>>T;
  rep(t,T){
    map<cc,char> comb;
    int C;cin>>C; //0-1:36
    rep(c,C){
      string abc;cin>>abc;
      comb[cons(abc[0],abc[1])] = abc[2];
      comb[cons(abc[1],abc[0])] = abc[2];
    }

    set<cc> opp;
    int D;cin>>D; //0-1:28
    rep(d,D){
      string xy;cin>>xy;
      opp.insert(cons(xy[0],xy[1]));
      opp.insert(cons(xy[1],xy[0]));
    }

    int N;cin>>N; //1-10:100
    string seq;cin>>seq;

    vector<char> f;
    rep(n,N){
      char c=seq[n];
      int fl=f.size();
      if (fl==0) {
        f.pb(c); continue;
      }
      cc bc=cons(f[fl-1],c);
      if(found(comb,bc)){
        f[fl-1] = comb[bc];
      }else{
        bool is_opp=0;
        rep(j,fl){
          cc gc=cons(f[j],c);
          if(found(opp,gc)) {
            is_opp=1; break;
          }
        }
        if(is_opp){
          f.resize(0);
        }else{
          f.pb(c);
        }
      }
    }

    printf("Case #%d: [", 1+t); 
    int fl=f.size();
    rep(i,fl){
      if (i) printf(", ");
      putchar(f[i]);
    }
    printf("]\n");
  }
  return 0;
}

C. Candy Splitting

• XOR演算だよねこれ
  • P = ((p1 xor p2) xor p3) xor ...
  • S = ((s1 xor s2) xor s3) xor ...
• P = S ←→ 2進各桁のビット数総和の奇遇が等しい
  • ということは、全ての数(p1,..,pn,s1,..,sn)の各桁のビット数総和は2の倍数か
• Sを最大化する{s1,s2,s3,...}の選び方 ←→ Pを最小化する{p1,p2,p3,...}の選び方
  • サンプル見ながら、P = S が成り立つのであれば{p1,p2,..}は何でもよいのか、てか一番小さい数を１つだけ選べばよくね？
• ビット数総和とか思って __builtin_popcount()とか持ち出してsmall計算合わないぞあるぇーと思って、はっ！ビット数は桁毎に数えないとダメじゃんと気づく
• てか P xor S = 0じゃね？
  • てことは全ての数のxor和が0であることが成立条件で、一番小さい数を{p1}として残りを{s1,..,sn}にすればよいね
• small（2度目）通った
• largeもスムーズに投稿

//略
int main(){
  int T;cin>>T; //1-100
  rep(t,T){
    printf("Case #%d: ", 1+t);
    int N;cin>>N; //2-15:1000
    vector<int> c(N); // 1-1e6 < 2^20
    int s=0,x=0;
    rep(n,N){
      cin>>c[n]; s+=c[n]; x^=c[n];
    }
    if(x){
      printf("NO\n");
    }
    else{
      int pat=*min_element(all(c));
      printf("%d\n", s-pat);
    }
  }
  return 0;
}

D. GoroSort

• 順位を変えたいものだけを空中に飛ばして並べ替える、力任せというよりは運任せなソート
• 並び順の正しくない（というか１つも正しい場所に入っていない）N要素を正しく並び替えるのに必要なステップ数をf(N)とすると
  • f(0) = 0
  • f(1) = 0
  • f(2) = 1 + ( f(0)*1 + f(2)*1 )/2!
    • ∴ f(2) = 2
    • 2要素のpermutationは2!=2通り
    • 1投目で2要素が正しく並び替わる: 1通り {(1,2)}
    • 〃 2要素とも正しくならない（ので2要素についてやり直し）: 1通り {(2,1)}
  • f(3) = 1 + ( f(0)*1 + f(2)*3 + f(3)*2 )/3!
    • ∴ f(3) = 3
    • 3要素のpermutationは3!=6通り
    • 1投目で3要素が正しく並び替わる: 1通り {(1,2,3)}
    • 1投目で1要素だけ正しい位置に入り、2要素がまだ正しくない: 3通り {(1,3,2), (3,2,1), (2,1,3)}
    • 1投目で3要素とも正しくならない: 2通り {(2,3,1), (3,1,2)}
• ... というのをf(10)ぐらいまで計算してみて f(N)=Nになるっぽかったので
• 位置の合っていない要素の数を数えてそれをdoubleっぽく返せばよくね？
• small通った。
• largeもスムーズ。

//略
int main(){
  int T;cin>>T; //1-100
  rep(t,T){
    int N;cin>>N; //1-10:1000
    vector<int> od(N); int wo=0;
    rep(n,N){
      cin>>od[n]; if(od[n]!=1+n)wo++;
    }

//  printf("Case #%d: %8.6f\n", 1+t, (double)wo);
    printf("Case #%d: %d.000000\n", 1+t, wo);
  }
  return 0;
}

とりあえずsmallは4問とも通ったので40点確保。

→結果としては満点通過。（205位というのは参加した時間帯を表しているに過ぎないのでどうでもいい。むしろ4問解くのに2時間半ほどかかってしまっているという残念な事実に注視）

Round1は5/21(土)。A,B,Cのどれかで通ればよいのだけれど、1Bは出られないと思うのでとりあえず1Aを頑張りたい。