SRM475
Div1にさっさと行くことが出来たので、良しとしましょう。
今回はうさぎ祭り。
RabbitVoting
計算するだけ。
#include <algorithm> #include <iostream> #include <map> #include <numeric> #include <set> #include <sstream> #include <string> #include <vector> using namespace std; #define FOR(i,s,e) for (int i = int(s); i != int(e); i++) #define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++) #define ISEQ(c) (c).begin(), (c).end() class RabbitVoting { public: string getWinner(vector<string> names, vector<string> votes) { int max = 0; int maxnumber = -1; vector<int> alpha((int)names.size(),0); for(int i=0; i<(int)names.size(); i++){ if(names[i] == votes[i]) continue; for(int j=0; j<(int)names.size(); j++){ if(votes[i] == names[j]){ alpha[j] += 1; if(alpha[j] > max){ max = alpha[j]; maxnumber = j; }else if(alpha[j] == max){ max = alpha[j]; maxnumber = -1; } } } } if(maxnumber!=-1) return names[maxnumber]; else return ""; } };
RabbitStepping
めんどくさいです。
もっとスマートな解法が絶対にあるはずなんだけど、そんな事考えるよりコード書いたほうが早かったので。
可読性の低いコードの典型例。
#include <algorithm> #include <iostream> #include <map> #include <numeric> #include <set> #include <sstream> #include <string> #include <vector> using namespace std; #define FOR(i,s,e) for (int i = int(s); i != int(e); i++) #define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++) #define ISEQ(c) (c).begin(), (c).end() class RabbitStepping { public: double getExpected(string field, int r) { vector<int> a; for(int i=0; i<(int)field.size(); i++){ if(i>(int)field.size()-r-1) a.push_back(1); else a.push_back(0); } vector<vector<int> > prev; int res = 0; int trial = 0; do{ int i=0; int k=0; for(; k<(int)prev.size(); k++){ for(i=0; i<(int)field.size(); i++){ if(prev[k][i] != a[i]) break; } if(i==(int)field.size()) continue; } prev.push_back(a); vector<int> sim; for(int i=0; i<(int)field.size(); i++){ if(a[i]==1) sim.push_back(i+1); else sim.push_back(0); } for(int i=0; i<(int)field.size()-2; i++){ int back=0; int now =0; int forw=0; for(int j=0; j<(int)field.size()-i; j++){ if(j==(int)field.size()-i-1){ if(sim[j] != 0){ if(back != 0){ back = 0; }else{ back = j+1; } } sim[j] = 0; }else if(sim[j] != 0){ if(j==0){ forw = 1; }else if(j==(int)field.size()-i-2){ if(back != 0){ back = 0; }else{ back = j+1; } }else if(sim[j]!=0){ switch(field[j]){ case 'W': if(back != 0){ back = 0; }else{ back = j+1; } break; case 'B': forw = j+1; break; case 'R': if(i==0 || sim[j] == j){ if(back != 0){ back = 0; }else{ back = j+1; } }else{ forw = j+1; } break; default: break; } } } if(j != 0){ sim[j-1] = back; } back = now; now = forw; forw = 0; } } if(sim[0]!=0) res++; if(sim[1]!=0) res++; trial++; }while(next_permutation(a.begin(),a.end())); return (double)res/(double)trial; } };