問題概要
出題者と回答者の二人で行う次のようなゲームをする。
- 出題者が、平面上の整数座標にいくつかの「特別な点」を設定する（特別な点は相異なる）
- 出題者は、特別な点の座標を X, Y 独立にシャッフルして回答者に提示する
- 回答者は、提示された X, Y 座標を使って同数の点を作る
- 特別な点と一致した点の数が回答者の得点となる
回答者が少なくとも得ることができる得点は何点か、求めよ。
ただし、回答者は点を作るときに以下の制約を満たさなければならない。
- 提示された X, Y 座標に含まれるそれぞれの値を過不足なく使う
- 同一の点を複数個作ってはいけない
解法
回答者が得られる最低点を求めるので、X, Y 座標をできるだけ得点が増えないように対応付ける問題であると見做せます。これは、X 座標のそれぞれの値に Y 座標の値を過不足無く対応させる問題なので、割当問題の一種です。単純な割当問題は二部グラフの重み付きマッチングなので、（ X 座標 ) <-> ( Y 座標 ) という（有向化した）二部グラフの両側に Source と Sink を追加したグラフを考えて最小費用流に帰着することで解くことができますが、そのままやってしまうと二つ目の制約（同じ点を複数個作れない）を導入できません。
グラフに於いて、片側の座標は頂点に対応し、作られる点は対応する座標を表す頂点間に張られた辺に対応します。従って、同じ点を表す辺が一本しか存在しないようにすれば制約を導入できます。これは、それぞれの片側座標にある同一の値を一つの頂点にまとめることで達成できます。このとき、Source, Sink に繋がっている辺の容量を、その座標の数とします。また、X 座標の頂点と Y 座標の頂点の間に張られる辺は、容量を 1 、コストはそれが特別な点に対応する辺であれば 1 、そうでなければ 0 とします。こうすることで、このグラフで流れる最小費用流のコストが、問題のゲームで得られる最低点となります。
まとめると、次のようにグラフを作って最小費用流を流せば、そのコストが問題の答えです。
- Source から X 座標の頂点へ、流量 = ( X 座標中の対応する値の数 )、コスト 0 の辺を張る
- X 座標の頂点から Y 座標の頂点へ、流量 1 、コスト = ( 特別な点に対応する辺なら 1 、そうでなければ 0 ) で辺を張る
- Y 座標の頂点から Sink へ、流量 = ( Y 座標中の対応する値の数 )、コスト 0 の辺を張る
コード
typedef vector<int> VI; typedef pair<int,int> PII; typedef vector<PII> VPII; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define ALL( c ) (c).begin(), (c).end() #define PB( n ) push_back( n ) #define MP( a, b ) make_pair( ( a ), ( b ) ) // 最小費用流 O( F |E| log |V| ) class MinimumCostFlow; // MinimumCostFlow( |V| ) // connect( from, to, cap, cost ) // solve( s, t, f ) : ポテンシャル付 Dijkstra // solve2( s, t, f ) : Bellman-Ford class SpecialCells { public: int guess( vector <int> x, vector <int> y ) { const int N = x.size(); VPII ps; map<int,int> cnt_x, cnt_y; ps.reserve( N ); REP( i, 0, N ) { ps.emplace_back( x[i], y[i] ); cnt_x[ x[i] ]++; cnt_y[ y[i] ]++; } sort( ALL( ps ) ); sort_unique( x ); sort_unique( y ); const int X = x.size(); const int Y = y.size(); MinimumCostFlow mcf( X + Y + 2 ); // [ 0, X ) := x coordinates // [ X, X + Y ) := y coordinates const int SRC = X + Y; const int SINK = SRC + 1; REP( i, 0, X ) { mcf.connect( SRC, i, cnt_x[ x[i] ], 0 ); } REP( i, 0, X ) { REP( j, 0, Y ) { mcf.connect( i, X + j, 1, binary_search( ALL( ps ), MP( x[i], y[j] ) ) ); } } REP( j, 0, Y ) { mcf.connect( X + j, SINK, cnt_y[ y[j] ], 0 ); } return mcf.solve( SRC, SINK, N ); } void sort_unique( VI &v ) { sort( ALL( v ) ); v.erase( unique( ALL( v ) ), v.end() ); return; } };
