SRM549 Div1 Easy(250), Div2 Medium(500) PointyWizardHats
2部グラフの最大マッチングに帰着できる。1個目の条件は、上の円錐のほうが頂角が小さいということ。
#include <vector> using namespace std; // 最大流 int maxflow( vector<vector<int> > edge, int s=0, int t=-1 ) { int n = (int)edge.size(); if ( t<0 ) t = n-1; int f = 0; vector<vector<int> > F(n,vector<int>(n)); while(true) { vector<int> P(n,-1); P[s]=-2; vector<int> Q(1,s); while ( !Q.empty() && P[t]==-1 ) { int u = Q.back(); Q.pop_back(); for ( int v=0; v<n && P[t]==-1; v++ ) if ( P[v]==-1 && edge[u][v]-F[u][v]>0 ) P[v] = u, Q.push_back(v); } if ( P[t]==-1 ) break; int m = edge[P[t]][t]; for ( int v=P[t]; v!=s; v=P[v] ) m = min(m,edge[P[v]][v]-F[P[v]][v]); f += m; for ( int v=t; v!=s; v=P[v] ) F[P[v]][v] += m, F[v][P[v]] -= m; } return f; } // 二部グラフの最大マッチング int bipartite( vector<vector<bool> > edge ) { int n = (int)edge.size(); int m = (int)edge[0].size(); vector<vector<int> > E(n+m+2,vector<int>(n+m+2)); for ( int i=0; i<n; i++ ) E[0][i+1] = 1; for ( int i=0; i<n; i++ ) for ( int j=0; j<m; j++ ) if ( edge[i][j] ) E[i+1][j+n+1] = 1; for ( int i=0; i<m; i++ ) E[i+n+1][n+m+1] = 1; return maxflow(E); } class PointyWizardHats{public: int getNumHats( vector <int> topHeight, vector <int> topRadius, vector <int> bottomHeight, vector <int> bottomRadius ) { int n = (int)topHeight.size(); int m = (int)bottomHeight.size(); vector<vector<bool> > E(n,vector<bool>(m)); for ( int i=0;i <n; i++) for ( int j=0; j<m; j++ ) E[i][j] = topHeight[i]*bottomRadius[j]>bottomHeight[j]*topRadius[i] && topRadius[i]<bottomRadius[j]; return bipartite(E); }};