TopCoder SRM 512 Div2 Hard DoubleRoshambo

よく出題意図がわからない問題…。
http://community.topcoder.com/stat?c=problem_statement&pm=11289

問題

２人で変則的なじゃんけんをN回行う。
じゃんけんの各回では、各人両手にグーチョキパーのいずれかを出す。
その時、以下のルールで得点が得られる。

• 右手同士および左手同士のじゃんけんでともに勝つと、２点もらえる。
• 右手同士のじゃんけんで勝ち、左手同士があいこだと、１点もらえる。
• それ以外のケースでは点がもらえない。

両者はN回で出せる手が決められている。
相手の手の順番がわかっているとき、自分が得られるスコアを最大化せよ。

解法

互いにN回出せる手が決まっているので、最適マッチング問題になる。
マッチングによって０～２点得られるので、２点を下回る得点をコストとみなし、最小コストフロー問題を解けばよい。

int sc[51][51];
class MinCostFlow {
public:
	struct edge { int to, capacity; ll cost, reve;};
	static const int MV = 5000;
	vector<edge> E[MV];
	ll dist[MV], prev_v[MV], prev_e[MV], NV;
	
	void init(int NV) { this->NV=NV; for(int i=0;i<MV;i++) E[i].clear();}
	void add_edge(int x,int y, int cap, int cost) {
		E[x].push_back((edge){y,cap,cost,E[y].size()});
		E[y].push_back((edge){x,0, -cost,E[x].size()-1}); /* rev edge */
	}
	
	int mincost(int from, int to, int flow) {
		int res=0,i,v;
		ZERO(prev_v); ZERO(prev_e);
		while(flow>0) {
			fill(dist, dist+NV, 1LL<<50);
			dist[from]=0;
			bool up=true;
			while(up) {
				up=false;
				FOR(v,NV) {
					if(dist[v]==1LL<<50) continue;
					FOR(i,E[v].size()) {
						edge &e=E[v][i];
						if(e.capacity>0 && dist[e.to]>dist[v]+e.cost) {
							dist[e.to]=dist[v]+e.cost;
							prev_v[e.to]=v;
							prev_e[e.to]=i;
							up=true;
						}
					}
				}
			}
			
			if(dist[to]==1LL<<50) return -1;
			int lc=flow;
			for(v=to;v!=from;v=prev_v[v]) lc = min(lc, E[prev_v[v]][prev_e[v]].capacity);
			flow -= lc;
			res += lc*dist[to];
			for(v=to;v!=from;v=prev_v[v]) {
				edge &e=E[prev_v[v]][prev_e[v]];
				e.capacity -= lc;
				E[v][e.reve].capacity += lc;
			}
		}
		return res;
	}
};

class DoubleRoshambo {
	public:
	int N;
	int maxScore(vector <string> A, vector <string> E) {
		N=A.size();
		int x,y;
		MinCostFlow mcf;
		mcf.init(1000);
		FOR(x,N) mcf.add_edge(200,x,1,0);
		FOR(x,N) mcf.add_edge(100+x,300,1,0);
		
		ZERO(sc);
		FOR(x,N) FOR(y,N) {
			int c=2;
			if((A[x][1]=='R' && E[y][1]=='S') || 
			   (A[x][1]=='S' && E[y][1]=='P') || 
			   (A[x][1]=='P' && E[y][1]=='R')) {
				c--;
				if((A[x][0]=='R' && E[y][0]=='S') ||
		             (A[x][0]=='S' && E[y][0]=='P') ||
				             (A[x][0]=='P' && E[y][0]=='R'))
				             c--;
				else if(A[x][0]!=E[y][0]) c=2;
			}
			mcf.add_edge(x,100+y,1,c);
		}
		return 2*N-mcf.mincost(200,300,N);
	}
};

まとめ

この問題は何がしたかったんだろう。