今回のは英文少なくて読みやすかった。がしかし275点の、ただの与えられた数値の平均なのにまわりくどく書いたり、900点の計算量が穴。
275 AverageAverage
{{与えられた数で作れる部分集合の平均}の集合}の平均を求めろ。
なんですが、与えられた数を足して割るだけっていう解法で十分通ってしまう非常に凶悪な問題。
+25点は落とし穴用かよ!!
class AverageAverage { public: double average(vector <int> numList) { double ret = 0; vector<double> sec; int sz = numList.size(); int cnt,sum; for(int i=1;i<(1<<sz);i++){ sum = cnt = 0; for(int j=0;j<sz;j++){ if( i&(1<<j) ){ sum += numList[j]; cnt++; } } sec.push_back((double)sum/cnt); } for(int i=0;i<sec.size();i++){ ret += sec[i]; } return ret/sec.size(); } };
Passed System Test => 243.90 Pt.
500 LockersDivTwo
ヨセフスのお芋の拡張版みたいな感じで、コピペしても良かったのかもしれないが、シミュレーションするソースを書いた。そしたらデバッグに死ぬほど時間費やした。泣きそうになった。
class LockersDivTwo { public: int lastOpened(int N) { vector<int> data(N); rep(i,N){ data[i] = i+1; } int n = 1; while(data.size() != 1){ for(vector<int>::iterator it = data.begin();it != data.end();){ it = data.erase(it); for(int i=0;i<n;i++){ if(it != data.end())it++; } } n++; } return data[0]; } };
Passed System Test => 271.25 Pt.
900 BaseConfusion
「NとMが与えられる。N以上M以下の数のB進数に変換したものをB+1進数として扱い、それを十進数にしたものの総和を求めよ。」という問題。
普通に変換するだけじゃ駄目。なぜかというとNとMは3億5000万くらいの範囲で与えられるから計算量明らかにバグる。てか普通に線形ループするだけで死ぬ3億5000万とか。
何かループに頼らない効率的な解法があるんでしょうが、検討がつきそうでつかなかったのでやめた。ガウス少年的なことをしようと思ったけど時間無かった。もっと早く手をつければ良かったかもしれない。
typedef long long ll; ll dec(string a,ll b){ ll src = 1; ll ret = 0; for(ll i=a.size()-1;i>=0;i--){ if('a'<=a[i])ret+= src*(a[i]-'a'+10); else ret += src*(a[i]-'0'); src*=b; } return ret; } string hex(ll a,ll b){ string ret; ll c; while(a){ c = a%b; if(c>=10)ret += 'a'+c-10; else ret += '0'+c; a /= b; } reverse(ret.begin(),ret.end()); return ret; } class BaseConfusion { public: long long sum(ll M, ll N, ll B) { long lo ng go = 0; string s; for(ll i=M;i<=N;i++){ go+=dec(hex(i,B),B+1); } return go; } };
Compliled. 0.0Pt
Challenge
2人TLEで撃墜。もう一人撃墜できたはずなんだけど他の人に撃墜された。
ていうかチャレンジ終わるまで3人撃墜したもんだと思ってたのに・・・。
そんで調子乗って275の足して総和のやつにチャレンジ送って撃墜。-25。
50.0*2 - 25.0*1 = 75.0Pt.
結果
243.90 + 271.25 + 0.0 + 75.0 = 590.15 Pt.
590.15点 ― 181位
レート: 789● ⇒ 881●
