naoya_t@topcoder

Google Code Jam: Qualification Round (24hrs)

GCJ2009 | 12:53 |

Google Code Jam初参加の巻

http://code.google.com/codejam/contest

• 参加
  • 起きたら８時過ぎてた
  • ひと仕事片付けて9am過ぎに参戦
  • サーバ側の問題で入力データがダウンロードできない時間が２時間弱続く
  • ３問ともC++で通すチキンっぷり
• 結果
  • 76pts(/99)で予選通過。参加?????人のうち2539位。
  • C-largeで、gets()をfgets()に書き直したせいでデータ読み込みでミスっててCase番号が途中からずれてた。その後のアルゴリズムは合ってた
  • 最初からvector<string>でデータが貰えるTopCoderに甘やかされている

問題と入力データはPrevious Contestsで見られます。

基本方針

• 最初からLargeが通るように書く
• あせらない

(A) AlienLanguage.cpp

• 正規表現ですね
• ここは自力でパースできるもんねってところを見せておく（＝バグの温床を増やす）か
• 26bitだしintでマスク作るか
• 最大最悪ケースのテストデータとかAWKで作ってテストしてから投稿
  • てか別にAWKで解いて終わりで良かったのでは

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int L, D, N;

int parse(vector<int>& ans, const string& s)
{
  ans.resize(L); for(int i=0;i<L;i++) ans[i]=0;

  int p=0;
  for(int i=0,len=s.size(); i<len;){
    int c=s[i++];
    if (c=='(') {
      while((c=s[i++])!=')'){
        ans[p] |= 1 << (c-'a');
      }
      p++;
    } else {
      ans[p++] = 1 << (c-'a');
    }
  }
  return p;
}

main()
{
  cin >> L >> D >> N;
  // L: [1-10] or [1-15]
  // D: [1-25] or [1-5000]
  // N: [1-10] or [1-500]

  // loading lexicon
  vector<vector<int> > lexicon(D,vector<int>(L,0));
  for(int d=0;d<D;d++){
    string s; cin >> s;

    int p = parse(lexicon[d], s);
  }

  // loading cases
  for(int n=0;n<N;n++){
    string s; cin >> s;

    vector<int> case_(L,0);
    int p = parse(case_, s);

    int K = 0;
    for(int d=0;d<D;d++){
      int x=0;
      for(int i=0;i<L;i++) if (lexicon[d][i] & case_[i]) x++;
      if (x==L) K++;
    }
    printf("Case #%d: %d\n", 1+n, K);
  }
}

(B) Watershed.cpp

TopCoderだとこの程度のでも焦ってミスるんだよね

• 各地点から東西南北どちらに水が流れるか、あるいは流れない(sink)かを調べる。sentinelぐらい使えるもんね
  • 調べたついでに、流れ先の「流れ元リスト」に自分を登録
  • sinkが現れたら仮idをふっておく
• 全sinkについて、流れ元リストを頼りに再帰的に全地点の流れ先sink（仮id）を求め伝播させる
• 出力時に、sink仮idを出現順にa-zに置き換え表示
• 最大最悪ケースのテストデータとか(AWKで)作ってテストしてから投稿
  • これもAWKで解けるレベル
  • 最悪すぎてsink数が（問題制約の）26を超えすぎて出力が変な文字で埋まったとか内緒

#include <iostream>
#include <vector>
#include <string>
#include <list>

using namespace std;

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)

vector<vector<int> > m; // source map
vector<vector<int> > d; // N=0 W=1 E=2 S=3 // sink=-1
vector<pair<int,int> > sink;
vector<vector<vector< pair<int,int> > > > chain;
vector<vector<int> > sm;

void paint(int h, int w, int sid)
{
  tr(chain[h][w],it) {
    int h2=it->first, w2=it->second;
    sm[h2][w2] = sid;
    paint(h2,w2,sid);
  }
}

main()
{
  int T, H, W, sid;

  cin >> T;

  rep(t,T){
    printf("Case #%d:\n", 1+t);

    sid = 0;
    
    cin >> H >> W;

    m.resize(H+2);
    sm.resize(H+2);
    d.resize(H+2);
    chain.resize(H+2);
    sink.resize(0);
    rep(h,H+2){
      m[h].resize(W+2);
      sm[h].resize(W+2);
      d[h].resize(W+2);
      chain[h].resize(W+2);
      rep(w,W+2) {
        m[h][w] = 99999;
        sm[h][w] = 99999;
        d[h][w] = -1;
        chain[h][w].resize(0);
      }
    }

    for(int h=1;h<=H;h++){
      for(int w=1;w<=W;w++){
        cin >> m[h][w];
      }
    }

    for(int h=1;h<=H;h++){
      for(int w=1;w<=W;w++){
        int a=m[h][w], dir=-1;
        if (m[h-1][w]<a) { dir=0; a=m[h-1][w]; }
        if (m[h][w-1]<a) { dir=1; a=m[h][w-1]; }
        if (m[h][w+1]<a) { dir=2; a=m[h][w+1]; }
        if (m[h+1][w]<a) { dir=3; a=m[h+1][w]; }
        d[h][w] = dir;

        switch(dir){
          case -1: sink.push_back( make_pair(h,w) ); sm[h][w] = sid++; break;
          case 0: chain[h-1][w].push_back( make_pair(h,w) ); break;
          case 1: chain[h][w-1].push_back( make_pair(h,w) ); break;
          case 2: chain[h][w+1].push_back( make_pair(h,w) ); break;
          case 3: chain[h+1][w].push_back( make_pair(h,w) ); break;
        }

      }
    }

    rep(s,sid){
      int h=sink[s].first, w=sink[s].second;
      paint(h,w,s);
    }

    // allocate characters [a-z]
    vector<int> corr(sid,0); int ch='a';
    for(int h=1;h<=H;h++){
      for(int w=1;w<=W;w++){
        int id=sm[h][w];
        if (corr[id]) continue;
        corr[id]=ch++;
      }
    }

    // replace & output
    rep(h,H){
      string o; o.resize(W*2-1);
      rep(i,W*2-1) o[i]=' ';
      rep(w,W){
        o[w*2] = corr[sm[h+1][w+1]];
      }
      cout << o << endl;
    }
  }
}

(C) WelcomeToCodeJam.cpp

• 教科書にDPの例として載りそうなくらいDP。
• 最初 gets() 使って書いてたけど、コンパイルするとwarningが出るのが嫌なので fgets() に書き換えた。別にwarning出るくらいいいのに… で、fgets()だと改行コードも入るので501では足りない・・・ (pts-=23)
• 面倒くさがって、500字のテストを書かなかったのも良くない

※以下、投稿時のコード

#include <iostream>
#include <vector>
#include <string>
#include <map>

using namespace std;

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

char msg[502], *salut="welcome to code jam";
int msg_len, salut_len=19;
map<pair<int,int>,long long> ht;

long long find_welcome(int msg_ix, int salut_ix)
{
  if (msg_len - msg_ix < salut_len - salut_ix) return 0LL;
  
  pair<int,int> key = make_pair(msg_ix,salut_ix);
  if (found(ht,key)) return ht[key];

  long long cnt = 0LL;
  if (msg[msg_ix] == salut[salut_ix]) {
    if (salut_ix == salut_len-1)
      cnt++;
    else
      cnt += find_welcome(msg_ix+1, salut_ix+1);
  }
  cnt += find_welcome(msg_ix+1, salut_ix);
  
  cnt %= 10000LL;
  
  ht[key] = cnt;

  return cnt;
}

main()
{
  int N;

  cin >> N;

  fgets(msg,501,stdin); // gets(msg);
  
  rep(n,N){
    ht.clear();

//  gets(msg);
//  msg_len=strlen(msg);
    fgets(msg,501,stdin); ←501を502にすれば通る
    rep(i,strlen(msg)) if(msg[i]<0x20){ msg_len=i; msg[i]=0; break; }

    long long cnt = find_welcome(0,0);
    printf("Case #%d: %04lld\n", 1+n, cnt);
  }
}

追記: getline()

それ

  string s;
  getline(cin, s);

でできるよ(泣)