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;
	}

};