GCJ-Qualification Round 2012

Google CodeJam Qualification Round 2012が終わりました。
20点以上の参加者がRound1に行きます。

Problem A : Speaking in Tongues

ある文字を他の文字に書き換える一定なルールで、入力の文字列を変換して、出力します。
ま、簡単ですね。
問題とは、ルールは何だろう？問題文には、乗っていません。
ですが、例題を見たら、わまりましたよ。

ProblemA

#include <map>
#include <iostream>
#include <stdio.h>
#include <string> 
using namespace std; 

const string RULE_IN = "ejp mysljylc kd kxveddknmc re jsicpdrysi rbcpc ypc rtcsra dkh wyfrepkym veddknkmkrkcd de kr kd eoya kw aej tysr re ujdr lkgc jvzq"; 
const string RULE_OUT= "our language is impossible to understand there are twenty six factorial possibilities so it is okay if you want to just give upqz"; 

int main(){
freopen("A-small-attempt1.in","r",stdin); 
freopen("A-small-attempt1.out","w",stdout); 
int T; 
string str, ans; 
cin >> T; 
getline(cin, str); 
for(int testid = 1; testid <= T; ++testid){
getline(cin,str);  
ans = ""; 
for(int i = 0; i < str.length(); ++ i){
int vt = RULE_IN.find(str[i]); 
if (vt > -1) ans += RULE_OUT[vt];
else cout << "############" << str[i] << endl << endl; 
}
cout << "Case #" << testid << ": " << ans << endl; 
}
return 0; 
}

Problem B : Dancing With the Googlers

ヒューリスティックなアルゴリズムを用いました。

ヒントとは、不思議な(a,b,c)のbest scoreの方が大きい。
例えば、total score  = 21にします。不思議な(a,b,c)のbest scoreは8です(6+7+8)。しかし、普通な(a,b,c)のbest scoreは7しかありません。

total scoreをソートして、大きい方から、可能の限りに最大(普通な)best scoreを計算します。そのbest scoreはPより大きいであったら、結果に1を加える。もしではなかったら、(不思議な)best scoreを計算します。

Problem B

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

int bestscore(int x, bool sur) {
if (x == 0) return 0; 
if (x == 1) return 1; 
if (!sur){ // 普通の場合 
if (x % 3 == 0) return x / 3;
else return x / 3 + 1; 
}
else { // 不思議の場合
if (x % 3 == 2) return x / 3 + 2; 
else return x / 3 + 1; 
}
}
int main(){
freopen("B-large.in","r",stdin); 
freopen("B-large.out","w",stdout); 
int T, total[200], S, P, N, ans; 
cin >> T; 

for(int testid = 1; testid <= T; ++testid) {
cin >> N >> S >> P; 
ans = 0; 
for(int i = 0; i < N; ++i) { cin >> total[i]; }
sort(total,total+N);
int numsur = 0;
bool usedsur = false; //不思議か、ではないか
for(int i = N-1; i >= 0; --i ){
if (!usedsur) {
if (bestscore(total[i],usedsur) >= P) {
ans ++; 
}
else {
usedsur = true; 
if (bestscore(total[i],usedsur) >= P && numsur < S) {
ans ++; 
numsur ++; 
}
}
}
else {
if (bestscore(total[i],usedsur) >= P && numsur < S) {
ans ++; 
numsur ++; 
}
}
}
cout << "Case #" << testid << ": " << ans << endl; 
}
return 0; 
}

Problem C : Recycled Numbers

私はちょっとバイトがありましたので、Problem A+Bだけ解きました。（20点以上になるはずですから十分）

簡単に全探索します。データが大きくない？と疑問があるかもしれませんが、実行時間がほぼ8分ありますから、叙述ですね。

Problem D : Hall of Mirrors


Comments