Google Code Jam 2010 :: Qualification Round

参加者の皆さん、お疲れ様でした。
結果は、
AとCを完答して、Score66でした。
B問題は最後まで意味が分からず…。
感想としては、
GCJ is very difficult english game.

A__Snapper Chain

ただの2進数の問題。10進数のKが与えられて、下位N桁全てのビットが1ならON、違うならOFF

#include <iostream>
using namespace std;
int main()
{
  int N,K,T;
  cin>>T;
  for(int x=1; x<=T; x++){
    cin>>N>>K;
    printf("Case #%d: %s\n",x,( (K&((1<<N)-1))==((1<<N)-1)? "ON" : "OFF"));
  }
  return 0;
}

C__Theme Park

1日にR回運用するK人乗りのロケットコースターがあって、1人あたり1ユーロの儲けがある。
グループ数Nの客のデータが1行で与えられて、
1 4 2 1
のとき、1人のグループ、4人のグループ、2人のグループ、1人のグループ、の行列で、先頭から順番に乗る。
グループは必ず全員一緒に乗らないといけない。Kが6のとき、
1人のグループと、4人のグループが乗れるが、2人のグループは乗れない。
よって、[ 1 4 ]の計5人(5ユーロ)が1回目に乗ることになる。乗った後は、行列の後ろに並ぶ。
このときの客データは
2 1 1 4
これをR回繰り返したときの最大ユーロを求める。

smallだけなら、てきとーにループを廻すだけでも十分間に合う。
ただ、largeの場合は少し工夫が必要。
何回かロケットコースターを運用すると、客の行列データがループに入る。
行列データの状態とその状態に対する儲けのユーロを記録しておき、
ループに入ったら残りの運用回数とループの周期から、儲けユーロを計算する。

#include <iostream>
#include <map>
#include <set>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
  int T;
  cin>>T;
  for(int round=1; round<=T; round++){
    int R,k,N;
    long long ans = 0;
    vector<int> v;
    vector< pair<vector<int>,long long> > vv;
    set<vector<int> > set_vec;
    
    cin>>R>>k>>N;
    for(int i=0; i<N; i++){ int a; cin>>a; v.push_back(a); }
    
    for(int r=0; r<R; r++){
      vector<int> hikae = v;
      long long sum = 0;
      int j;
      
      for(j=0; j<N; j++){
        if( sum+v[j]>k )break;
        sum += v[j];
        v.push_back( v[j] );
      }
      v.erase( v.begin(), v.begin()+j );      

      if( set_vec.find( hikae ) != set_vec.end() ){
        int i,shuuki,amari,cnt;
        for(i=0; i<vv.size(); i++)if( vv[i].first==hikae )break;
        shuuki = vv.size() - i;
        cnt = R-r;
        amari  = cnt % shuuki;
        for(; i<vv.size() && cnt>0 ; i++){
          ans += ( vv[i].second * ( (R-r)/shuuki + ( amari>0 ? 1: 0 ) ) );
          if( amari>0 )amari--;
          cnt--;
        }
        break;
      }else{
        set_vec.insert( hikae );
        vv.push_back( make_pair(hikae,sum) );
        ans += sum;
      }
    }
    printf("Case #%d: %lld\n",round,ans);
  }
  
  return 0;
}

5/10　追記：
Cコードの明らかにデバッグ用、無意味な処理部分を削除。