Google Code Jam 2012 Round1A
今日Round1Bの日だなーと思ったら，Round1Aのブログを書いていなかった．
A,B完答でRound2進出です
Problem A Password Problem
問題
現在，B文字あるパスワードのうちA文字タイプした状態である
ただし，そのA文字は打ち間違えがあるかもしれない．
として，i番目の文字が正しくタイプされた確率を示すことにする
- そのまま打ち直す
- 数文字バックスペースで戻って打ち直す
- まずエンターを押してリセット，その後打ち直す
これらの動作が許される時，打鍵数の期待値を最小にせよ
ただし，打ち直し中にはタイポは発生しないものとする
考えたこと
すべての行動パターンを試すだけ．
予め「i番目以内に間違いが存在する確率」を覚えておくと，
各行動パターンの打鍵数期待値は「成功確率*成功時打鍵数+失敗確率*失敗時打鍵数」で表せる．
小数の出力方法でまた手こずった．いい加減覚えたい．
コード
int main(){ int n_case; cin >> n_case; cout.setf(ios::fixed, ios::floatfield); for( int loop = 0 ; loop < n_case ; loop++ ){ int A, B; cin >> A>>B; vector<double> Ps; for(int i = 0 ; i < A ; i++ ){ double tmp; cin >> tmp; Ps.push_back( tmp ); } double ans = B+2; double Prob[100000]; memset( Prob, 0 , sizeof(Prob) ); Prob[0] = 1-Ps[0]; for( int i = 0 ; i+1 < A; i++ ){ Prob[i+1] = Prob[i]+(1-Prob[i])*(1-Ps[i+1]); } int rest = B-A; for( int n_erase = 0 ; n_erase+1 <= A; n_erase++ ){ int n_succeed = rest+n_erase*2+1; int n_failed = n_succeed+B+1; double failed_prob = Prob[A-n_erase-1]; //cout << n_succeed <<"*"<< (1-failed_prob)<<"+"<< n_failed<<"*"<<failed_prob<<endl; double anstmp = (1-failed_prob)*n_succeed+(failed_prob) * n_failed; //cout << anstmp << endl; ans = min(anstmp,ans); } cout << "Case #" << loop+1 << ": "; cout <<setprecision(6) << ans<<endl; } return 0; }
計算量はとかですかね．
Problem B Kingdom Rush
問題
Nステージあるゲームがある．
各ステージには1-star ratingと2-star ratingという二つの難易度があり
2-star ratingをクリアすれば星が二つ，
1-star ratingをクリアすれば星が一つもらえる．
ただし，同じステージの1-star ratingクリア後に2-star ratingをクリアしても星は一つしか貰えない．
各ratingがクリアできるか否かは，それまでに獲得した星の数で決まるものとする．
ステージはどんな順番で挑戦しても良いものとする．
各ステージの1-star rating, 2-star ratingの難易度を与えるので
このゲームを完全にクリアするための最小のステージチャレンジ数を答えよ．
もしもクリア不可能の場合はToo Badと返せ．
考えたこと
もらえる星の数はどのステージでも変わらないので，2-ratingをクリア出来る物があるならそれをクリアしながら星を集めていけば良い．
もし2-ratingをクリアできるものがないのなら，1-ratingクリア出来る物のなかで，2-ratingクリアが一番むずかしいものをクリアして星を稼いでいくとよさそうだ
こんなgreedyで書いてみる．
1-ratingをクリアしてるか否かの情報操作で一回バグったが，割りとすぐにミスに気づいて修正出来たので良かった．
コード
int main(){ int n_case; cin >> n_case; for( int loop = 0 ; loop < n_case ; loop++ ){ int n_level; cin >> n_level; vector<pair<int,int> > vec; for( int i = 0 ; i < n_level ; i++ ){ int first,second; cin >> first >> second; vec.push_back( make_pair( second,first ) ); } sort( vec.begin(), vec.end() ); int n_star = 0; int num = 0; for( int i = 0 ; i < n_level ;i++ ){ if( n_star < vec[i].first ){ bool flag = false;; for( int j = n_level-1 ; j >=0 ;j-- ){ if( vec[j].second == -1 ) continue; if( n_star >= vec[j].second ){ n_star++; //cout << "erase " << vec[j].second << endl; vec[j].second = -1; flag = true; break; } } if( flag == false ){ num = -1; break; } i--; } else{ if( vec[i].second == -1 ){ n_star++; //cout << "erase " << vec[i].first << endl; } else{ //cout << "erase " << vec[i].first <<","<< vec[i].second << endl; vec[i].second = -1; n_star+=2; } } //cout << n_star << endl; num++; } if( num == -1 ) cout << "Case #" << loop+1 << ": "<< "Too Bad"<<endl; else cout << "Case #" << loop+1 << ": "<< num<<endl; } return 0; }
計算量はステージ数をNとした時，くらい．
Nの上限はlargeでも1000なので問題なく終わる．
Problem C Recycled Numbers
問題
2車線の車道があり，車(長さ5m)が数台一定速度で動いている．
車線変更は瞬時に行える物とする．
このまま進んだ時，どれかの車が速度を変えなくてはならない時間を返せ．
永遠にすべての車が速度を保ったまま移動可能な時はPossibleを返せ．
考えたこと(未完)
チェックしなければいけないタイミングと言うのは，車の先端-末端がぶつかったタイミングすべてを調べれば良い．
じゃあそのすべての時間について車がニ車線に配置できるか調べれば良いのではないか？
書いた
あれ
サンプル通らない＼(^o^)／
より詳細に見てみると，
車A 速度4 初期位置0
車B 速度2 初期位置29
車C 速度1 初期位置35
車D 速度1 初期位置44
このケースが綺麗な反例になっていた
車BがCを抜くためにはCとDの車間距離が4mである(位置は車の後部と原点との距離で表されるので，車間の距離は車の長さの5をひかなくてはならない)ことより
車Cと車Dが車線L，車Bが車線Rを通るような形で抜かなくてはならない．
しかしそうすると，時刻12で車Aが車線Rを通ってC,Dを抜こうとした時，Bにぶつかってしまう．
しかし，僕が書いたプログラムでは，この時は「車Bと車Dの位置を瞬時に入れ替える事で，衝突が発生しなくなる」と判定していた．
つまり，二車線に車を配置できるか？だけを考えただけでは，車の瞬間移動という，実際には起こり得ない動作も許してしまうわけです．
じゃあどうすれば良いのか，は，わからずじまいで時間切れ＼(^o^)／
