Google Code Jam Japan 2011 予選
結果
A small,B Small,C Small,C Largeの4つでスコア28点で順位は343位でした。Smallが5点でLargeが13点です。
| Rank | Score | Time | A Small | A Large | B Small | B Large | C Small | C Large |
| 343 | 28 | 2:48:25 | 40:52 | --- | 2:48:25 | --- | 1:15:45 | 2:05:41 |
問題A. カードシャッフル
カードがM枚あり、それぞれのカードに1..Mの数字が書かれています。
カードの山をC回カットし、i回目のカットではカードの山の上からAi番目からBi枚取ってそれを残ったカードの山の上に置くようです。
C回のカットが終わったときカードの山の上からW番目のカードの数字を求める問題です。
Small 解法
愚直にシュミレーションします。配列の添字には気をつけましょう。ソースコード
#include <iostream> using namespace std; int main(){ int t; cin >> t; for(int i_=0 ; i_<t ; i_++ ){ int m,c,w,a,b; int h[101],temp[101]; for(int i=0 ; i<101 ; i++ ) h[i] = i+1; cin >> m >> c >> w; for(int i=0 ; i<c ; i++ ){ cin >> a >> b; for(int j=0 ; j <= a-2 ; j++ ){ temp[j+b] = h[j]; } for(int j=a-1 ; j <= a+b-2 ; j++ ){ temp[j-a+1] = h[j]; } for(int j=a+b-1 ; j < m ; j++ ){ temp[j] = h[j]; } for(int j=0 ; j < m ; j++ ){ h[j] = temp[j]; } } cout << "Case #" << (i_+1) << ": " << h[w-1] << endl; } }
Large 解法
Largeではカードの枚数が多いのでSmallの解法は使えません。逆順にシュミレーションします。最後の状態のW番目だけみてシュミレーションするので1回のカットでカードの移動が1枚になるのがとても嬉しいですね。
ソースコード
#include <iostream> using namespace std; int main(){ int t; cin >> t; for(int i_=0 ; i_<t ; i_++ ){ int m,c,w; int a[101], b[101]; cin >> m >> c >> w; for(int i=0 ; i<c ; i++ ){ cin >> a[i] >> b[i]; } for(int i=c-1 ; i >= 0 ; i-- ){ if( w <= b[i] ) w = a[i]-1+w; else if( w <= a[i]+b[i]-1 ) w = w-b[i]; } cout << "Case #" << (i_+1) << ": " << w << endl; } }
問題B. 最高のコーヒー
N種類のコーヒーがあり、i番目のコーヒーはCi杯ありTi日目に消費期限を迎え飲むとSiの満足度が得られる。
1日に1杯だけ消費期限の切れていないコーヒーを飲むことができる。
K日目までに得られる最大の満足度を求める。
Small 解法
N≦8,K≦8なので全探索します。幅優先探索でも深さ優先探索でもどちらでも問題ないと思います。
ソースコードは深さ優先探索で調べています。
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; int n,k,ans; void solve(int d, int p, vector<int> c, vector<int> t, vector<int> s){ if( d == k ){ ans = max( ans , p ); return; } bool flag = true; for(int i=0 ; i < n ; i++ ){ if( d < t[i] && c[i] > 0 ){ flag = false; c[i]--; solve( d+1 , p+s[i] , c , t , s ); c[i]++; } } if( flag ) solve( d+1 , p , c , t , s ); } int main(){ int t; cin >> t; for(int i_=0 ; i_<t ; i_++ ){ int c_,t_,s_; vector<int> c,t,s; cin >> n >> k; for(int i=0 ; i < n ; i++ ){ cin >> c_ >> t_ >> s_; c.push_back( c_ ); t.push_back( t_ ); s.push_back( s_ ); } ans = 0; solve( 0 , 0 , c , t , s ); cout << "Case #" << (i_+1) << ": " << ans << endl; } }
Large 解法
K日目から逆にたどって貪欲法で調べていくらしいです。うまくコードが書けなかったのでソースコードは割愛します。
問題C. ビット数
f(x)を「xを2進数表記した時の"1"の個数を返す関数」として
正の整数Nが与えられるので、a+b=Nを満たす自然数a,bの組の中でf(a)+f(b)が最大のものを求める。
Small 解法
N≦10000なので全探索します。(a,b)の組は高々(N/2+1)通りしかありません。ソースコード
#include <iostream> #include <algorithm> using namespace std; int f(int bits){ int n = 0; for( ; bits ; bits &= bits-1 ) n++; return n; } int main(){ int t; cin >> t; for(int i_=0 ; i_<t ; i_++ ){ int n, ans=0; cin >> n; for(int a=0 ; a <= n/2 ; a++ ){ ans = max( ans , f(a)+f(n-a) ); } cout << "Case #" << (i_+1) << ": " << ans << endl; } }
Large 解法
N≦10^18なので32bit整数では収まらないので気をつける必要があります。64bit整数(long long int)を使いましょう。
Nを超えない(最大の2のべき乗-1)をaとするとf(a)+f(N-a)が解となります。
ソースコード
#include <iostream> #include <algorithm> using namespace std; unsigned long long int f(unsigned long long int bits){ unsigned long long int n = 0LL; for( ; bits ; bits &= bits-1LL ) n++; return n; } unsigned long long int g(unsigned long long int n){ unsigned long long int i = 0xffffffffffffffffLL; while( n < i ) i >>= 1; return i; } int main(){ int t; cin >> t; for(int i_=0 ; i_<t ; i_++ ){ unsigned long long int n,ans=0; cin >> n; unsigned long long int a = g(n); cout << "Case #" << (i_+1) << ": " << ( f(a)+f(n-a) ) << endl; } }
感想
予選だけは通りたかったのでCはかなり念入りにテストしました。とりあえず予選通ってたのでよかったです。
全完できなかったし決勝はちょっとつらいかもしれない。
Tシャツほしいなー。
