Google Code Jam予選(2)
400ポイントと1000ポイントの問題があって、迷わず1000ポイントのほうを選択。
1000ポイントの問題は二種類あったそうだ。私に出題されたのはギアのトランスミッションの問題。問題の正確な意味を理解するのに40分ぐらいかかる。(かかりすぎ！)
歯がaのギアと歯がbのギアが噛み合わさると、ギア比は a / b になる。
歯がa,b,cのギアが順番に噛み合わさっていると、ギア比は a / b * b / c = a / c になる。つまり、ギア比は、最初のギアと最後のギアで割ったものになる。
それで、問題の内容は、前段のギアセットはすでに決められていて(vector<int> frontで与えられる)、後段のギアセットを決めなさいというもの。(すべては連結されているものと考える)
後段のギアの数はcntで、ギア比は最初と最後のギアの歯だけで決まるので、その組み合わせはfront.size()*cntだけある。後段にあるcnt個のギアのうち、最小の歯をもつものと最大の歯をもつものは、min,maxで与えられる。
また、front.size()*cnt個のギア比をソートして、そのソートされたリストのなかで隣接する部分の差(adjacent ratios)が最大となる部分、これをbiggest gapと呼ぶ。求めるのは、このbiggest gapが最小となるように後段ギアの未知の歯の数を決定したときの、biggest gapの値。
cntは3〜5なので、総当りで処理すればいいだけ。うひょー！なんだよこの問題、簡単すぎ！！プログラムよか、問題の英文のほうが難しいよ！！そんなわけで、ざざっと書いて、デバッグしてたら時間切れ。うわーん。そりゃないよー。一応、書いたソースは以下の。殴り書き & コピペを繰り返しているので汚いソースだけど参考用に。
うーん。来年までにプログラミング能力よか英語力をもっと養っておかなくてはなぁ．．(´ω`) そんなわけでお粗末な結果になりました。心よりゴメンナチイ。問題はあと5,000倍ぐらい難しくてもいいから、時間ちょうだいよ、時間。
稲葉さん、予選通過してそうだから、このあとのレポートは任せた！
http://www.kmonos.net/wlog/42.php#_0248040916
#define DBL_MIN -100000000000 // limits.h includeマンドクセ('A`)
#define DBL_MAX 100000000000 // limits.h includeマンドクセ('A`)
typedef unsigned int uint;class Transmission {
public:
double gears(vector <int> front, int min, int max, int cnt)
{
double min_gap = DBL_MAX;
vector<int> back_gear;
vector<double> tmp_ratio;
tmp_ratio.resize(front.size()*cnt);switch (cnt){
case 3: {
for(uint i=min+1;i<=(uint)max-1;++i){
back_gear.clear();
back_gear.push_back(min);
back_gear.push_back(i);
back_gear.push_back(max);
double gap = calc_gap(front,back_gear,tmp_ratio);
if (gap<min_gap) min_gap = gap;
}
break;
case 4: {
for(uint i=min+1;i<=(uint)max-2;++i){
for(uint j=i+1;j<=(uint)max-1;++j){
back_gear.clear();
back_gear.push_back(min);
back_gear.push_back(i);
back_gear.push_back(j);
back_gear.push_back(max);
double gap = calc_gap(front,back_gear,tmp_ratio);
if (gap<min_gap) min_gap = gap;
}
}
break;
}
case 5: {
for(uint i=min+1;i<=(uint)max-3;++i){
for(uint j=i+1;j<=(uint)max-2;++j){
for(uint k=j+1;k<=(uint)max-1;++k){
back_gear.clear();
back_gear.push_back(min);
back_gear.push_back(i);
back_gear.push_back(j);
back_gear.push_back(k);
back_gear.push_back(max);
double gap = calc_gap(front,back_gear,tmp_ratio);
if (gap<min_gap) min_gap = gap;
}
}
}
break;
}
}
}
return min_gap;
}
double calc_gap(const vector<int>&front,const vector<int>&back,
vector<double>&tmp_ratio){
uint k = 0;
for(uint i=0;i<front.size();++i){
for(uint j=0;j<back.size();++j){
tmp_ratio[k++] = ((double)front[i]) / back[j];
}
}
size_t size = tmp_ratio.size();
std::sort(&tmp_ratio[0],&tmp_ratio[size]);
double max = DBL_MIN;
for(uint i=0;i<size-1;++i){
double t = tmp_ratio[i+1]-tmp_ratio[i];
if (t > max) max = t;
}
return max;
}};
