| 889位 | 180.92pt | |
| 250 | Accepted | 180.92 |
|---|---|---|
| 500 | WA | 0.0 |
| 1000 | Opend | 0.0 |
| Hack | - |
1264→1270(+6)
10ヶ月くらいぶりのTopCoder.
自分のクズっぷりが遺憾なく発揮された結果がこれである.
まず思い付いたのが, 与えられた名前を出てきた回数とmapにぶちこんで, 出てきた回数で二分探索or線型探索する方法.
勝つ可能性があるかどうかは, 自分が最初に飲む→あとは回数が少ない順に飲むでOK.
C++で書くのが久々で, mapとかどうやって使うんだっけーと思っていたら, playersのサイズが8以下というのを見つけ, next_permutationと普通にシミュレーションすればいいと思い, そのように書いた.
string get(vector<string> &players){
double a = 1, b = 1;
map<string, double> memo;
rep(i, players.size()){
if(i%2 == 0){
memo[players[i]] += a/2.0;
a /= 2.0;
}else{
memo[players[i]] += b/2.0;
b /= 2.0;
}
}
double m = -1;
string res = "fooo";
foreach(it, memo){
if(it->second >= m){
m = it->second;
res = it->first;
}
}
int cnt = 0;
foreach(it, memo){
if(it->second == m)
++cnt;
}
if(cnt > 1) return "";
return res;
}
inline vector <string> EllysJuice::getWinners(vector <string> players){
vector <string> res;
sort(players.begin(), players.end());
do{
string a = get(players);
bool f = true;
rep(i,res.size()) if(res[i] == a) f = false;
if(f && (a != "")) res.pb(a);
}while(next_permutation(players.begin(), players.end()));
sort(res.begin(), res.end());
return res;
}
getのa,bをintで取るとか色々やらかして, 割とクズい感じであったが, まぁACった.
後で考えてみれば, 1人の時はその人, 2人以上の時は2回以上飲んでいる人を返せばいいのは明らかであった....
問題文を読んでそのまま思い付いた方針を採った.
ab=n!になるのは, (1<<n!の素因数の種類)程度のパターン数であるから, nまでの素因数分解を適当にやってやればいいか的な方針.</ppp>
よく見るとa/b<1でなければならず, {a,b}に対して分母と分子が一意に決まるので, 1<<(n!の素因数の種類-1)が正解である.
この修正を忘れていたのだが, デバッグ実行していたのが250のままで, サンプルに全部通っていると勘違いし, 更に1LLにしなければならないのを, 大きい数字入力しても通っているので, LLにし忘れてないだろうと思ってそのまま提出してしまった.
後で通したコードはこれ.
inline long long EllysFractions::getCount(int N){ long long res = 0; vector<int> d(300); int cnt = 0; for(int i=2; i<=N; ++i){ int k = i; for(int j=2; k!=1; ++j){ if(k%j == 0){ if(!d[j]) ++cnt; ++d[j]; k /= j; --j; } } if(cnt)res += 1LL<<(cnt-1); } return res; }
ついでに, 1<<-1がどうなるかは割とアレらしく, i=2を気をつけるべきらしい.
また, cntが増えるのは明らかにiが素数の時なので, そもそも素因数分解までせずともよかった.
この問題に関する僕のクズさは本当に異常である...
とりあえずxorゲーなので, 文字列からlong longにする.
2-SATかとも一瞬思ったが, xorなのでなんか違うっぽい.
蟻本に出てるunion-findのやつかと思ったが, どうすればうまく行くか, 最小に出来るか等思い付かない.
「各電球は高々2つのスイッチにしか繋がっていない」に注目して, てきとーに探索しても割と余裕で行けるのではないかと考え, 実装する.
サンプルが1つだけ合わず, 時間切れ.
条件分岐のネストを間違えていた.
終了後に直して提出するものの, Systemtest合わず.
よく見直してみると, またも1LLにするのを忘れていて, 直しても更に, TLEする.
連結成分で分解して, 各連結成分に対して, 「スイッチを1つ入れる→その他が決まる」みたいな事をやれば良いらしい.
確かにそうだし, 同じような事をどこかでやった事があるような気がする.
成長していないというか, 退化しているような気がする･･･
1Bはもうちょっといい結果が出せるように頑張ろう.