Google Code Jam - Qualification Round

参加者の皆さんお疲れ様でした。
今回初参加、C++でチャレンジしましたよー。問題文の英語…辛かったですｗ

問題A

Alien Language
文字列の生成規則と文字列が与えられて、指定された生成規則で与えられた文字列のうちいくつ生成できるかという問題です。


簡単な構文解析と、n文字目に何の文字が生成される可能性があるかを記録して解きました。

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

int hash[15][26];

void parse(string& patt){
  int ind=0;
  for(int i=0;i<patt.size();i++){
    if( patt.at(i)=='(' ){
      for(i++;patt.at(i)!=')';i++){
        hash[ind][patt.at(i)-'a']=1;
      }
    }else{
      hash[ind][patt.at(i)-'a']=1;
    }
    ind++;
  }
  return;
}
int main(void){
  int L,D,N;
  for(;cin>>L>>D>>N;){
    vector<string> v;
    for(int i=0;i<D;i++){ string s; cin>>s; v.push_back(s); }
    for(int X=1;X<=N;X++){
      int ans=0;
      printf("Case #%d: ",X);
      memset(hash,0,sizeof(hash));
      string pattern;
      cin>>pattern;
      parse(pattern);
      for(int j=0;j<D;j++){
        int m;
        for(m=0;m<L && hash[m][v[j][m]-'a'];m++);
        if(m==L){
          ans++;
        }
      }
      printf("%d\n",ans);
    }
  }
  return 0;
}

問題B

Watersheds
高さの値が記録されたマップ情報が与えられます。
高い場所から低い場所に流水したときの区分けをしたマップ情報を出力する問題です。
流水するのは4方向、多くても1か所にしか流れ込まず、同じ高さのときは北西東南という優先順位で決めます。
区分けしたマップの左上から順に辞書順アルファベットを与えます。


マップの高い場所から、区分けされた場所or流水できない場所まで深さ優先探索。

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int dy[]={1,0,0,-1};
const int dx[]={0,1,-1,0};
int W,H,field[100][100],ans[100][100],cnt;

int fill(int x,int y){
  int dmin=101*101,next_x,next_y;
  for(int k=0;k<4;k++){
    int tx=x+dx[k];
    int ty=y+dy[k];
    if(tx<0 || tx>=W || ty<0 || ty>=H)continue;
    if(field[y][x]>field[ty][tx] && dmin>=field[ty][tx]){
      dmin=field[ty][tx]; next_x=tx; next_y=ty;
    }
  }
  if(dmin!=101*101){
    if(ans[next_y][next_x]==0){
      ans[next_y][next_x]=fill(next_x,next_y);
    }
    return ans[next_y][next_x];
  }
  else{
    cnt++;
    return cnt;
  }
}

int main(void){
  int T;
  vector<int> vx,vy;
  
  cin>>T;
  for(int x=1;x<=T;x++){
    cnt=0;
    memset(ans,0,sizeof(ans));
    memset(field,0,sizeof(field));
    printf("Case #%d:\n",x);

    int dmax=-1;
    cin>>H>>W;
    for(int i=0;i<H;i++)for(int j=0;j<W;j++){
      cin>>field[i][j];
      if(dmax<=field[i][j]){
        if(dmax==field[i][j]){ vx.push_back(j); vy.push_back(i); }
        else{
          vx.clear(); vy.clear();
          vx.push_back(j); vy.push_back(i);
        }
        dmax=field[i][j];
      }
    }

    for(;;){
      for(int p=0;p<vx.size();p++){
        ans[vy.at(p)][vx.at(p)] = fill(vx.at(p),vy.at(p));
      }
      
      vx.clear(); vy.clear();
      int d2max=-1;
      
      for(int i=0;i<H;i++)for(int j=0;j<W;j++){
        if(dmax>field[i][j] && d2max<=field[i][j] && ans[i][j]==0){
          if(d2max==field[i][j]){ vx.push_back(j); vy.push_back(i);}
          else{
            vx.clear(); vy.clear();
            vx.push_back(j); vy.push_back(i);
          }
          d2max=field[i][j];
        }
      }
      if(d2max==-1)break;
      dmax=d2max;
    }
    
    char alpha[30],cc='a';
    memset(alpha,0,sizeof(alpha));
    
    for(int i=0;i<H;i++){
      for(int j=0;j<W;j++){
        if(j)printf(" ");
        
        if(alpha[ans[i][j]]==0){
          alpha[ans[i][j]]=cc;
          printf("%c",cc);
          cc++;
        }else{
          printf("%c",alpha[ans[i][j]]);
        }
      }
      puts("");
    }
  }
  return 0;
}

問題C

Welcome to Code Jam
与えられた文字列の先頭から任意に文字を選択し、文字列"welcome to code jam"が生成できるパターン数を答える問題です。
出力するパターン数は下位4桁のみを出力します。

動的計画法です。

#include <iostream>
#include <string>
using namespace std;

int common_str(string& str){
  string C="welcome to code jam";
  int size=C.size();
  int dp[2][str.size()];
  memset(dp,0,sizeof(dp));
  
  for(int i=0;i<size;i++){
    int sum=0;
    for(int j=0;j<str.size();j++){
      if(i && C[i-1]==str[j] && dp[1][j]==i){
        sum+=dp[0][j];
      }
      sum%=10000;
      if(C[i]==str[j]){
        dp[0][j]=i?sum:1; dp[1][j]=i+1;
      }
    }
  }
  int ans=0;
  for(int i=0;i<str.size();i++){
    if(dp[1][i]==size && C[size-1]==str[i])ans+=dp[0][i];
    ans%=10000;
  }
  return ans;
}

int main(void){
  for(int N;cin>>N;){
    cin.ignore();
    for(int X=1;X<=N;X++){
      string s;
      getline(cin,s);
      printf("Case #%d: ",X);
      int ans=common_str(s);
      if(ans>=1000)printf("%d\n",ans);
      else printf("%s%d\n",ans>=100?"0":ans>=10?"00":"000",ans);
    }
  }
  return 0;
}

small,largeともに正解してスコア99ptのRank:1586でした。
全問正解しないと次へ進めないと思っていましたが、33pt以上なら通過のようです。人数制限はない様子。
それにしても…どれもコードが汚いｗ。特にBが一番酷いですね…
他の方のコードも見れるので後で勉強します。鮮やかに解いてる人がいるに違いない。


Code Jam Statistics (2015)
Google Code Jam のデータを色々とまとめたサイトを教えてもらいました。
これは便利すぎるｗ
code jamの過去問も後でやろうっと。