SRM 371 500pt: ChessMatchup

問題概要

自チームと相手チームには互いにN(<50)人の選手がいる。それぞれレーティングを持っていて、レーティングの高い方が必ず勝つ(同じときは引き分け)。勝つと勝点2が貰えて引き分けると勝点1が貰える。獲得できる勝点の最大値を求める問題。

考えたこと

• 最大重み2部マッチング？それって解き方あったっけ？
• (2-勝点)をコストとして最小重み2部マッチングで解けるか。
• ライブラリコピペするだけなのもあれなので、他の解法も考えてみよう。
• しばらく考えたけど分からない。仕方ないのでライブラリ張って動かす。
• ライブラリコピペしただけなのに動かない。何で？
• 頂点数の代入してなかった。このミスが起きないように工夫しないといかんなあ。修正したのを投げたら何事も無く通った。
• この回の他の人の解法をみたら最小費用流ライブラリの参考になるかもしれない。

practiceで通ったコード

#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

struct ChessMatchup {

	int maximumScore(vector <int> us, vector <int> them) {
		const int N = us.size();

		//scouceからusへの辺を張る
		for(int i=0; i<N; i++){
			add_edge(2*N, i, 1, 0);
		}

		//themからsinkへの辺を張る
		for(int i=0; i<N; i++){
			add_edge(i+N, 2*N+1, 1, 0);
		}

		//２部グラフを構成する
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++){
				int lose_point = (us[i] > them[j]?0:us[i]==them[j]?1:2);
				add_edge(i, j+N, 1, lose_point);
			}
		}
		V = 2*N+2;

		return 2*N - min_cost_flow(2*N,2*N+1,N);
	}

};

計算量を落とす

他の人の回答をみたら、まず最初に両方ソートして、その後自チームのをrotate全通り試すだけで通る様だった。証明はできてない。