問題概要
$1$ から $M $ で番号付けられた $M $ 個のパーツを使って作られる機械がある．一つの機械は，$1$ から $M $ のパーツを一つずつ使って構成される．
パーツは，$N$ 個の店から買うことができる．各 $i$ ( $1 \leq i \leq N$ ) について，$i$ 番の店では $A_i$ 以上 $B_i$ 以下の番号のパーツを（合計で）最大 $K_i$ 個まで買うことができる．
作ることのできる機械の最大数を求めよ．
- $1 \leq N \leq 50$
- $1 \leq M \leq 10^5$
- $1 \leq K_i \leq 10^6$
- $1 \leq A_i \leq B_i \leq M $
解法
ある $k$ について，$k$ 個の機械を作ることができるとすれば，明らかに $k - 1$ 個の機械を作ることもできます．逆に，$k$ 個の機械を作ることができないならば，$k + 1$ 個の機械を作ることもできません．つまり，問題は解に関して単調性をもちます．
単調な関数についてその閾値を求める手法に二分法があります．この問題も，二分法を用いて解くことができます．
二分法のために，$\it{ check } : \mathbb Z^+ \rightarrow \{ \it{ False }, \it{ True } \}$ なる関数 $\it{ check }$ を考えます．$\it{ check }( k )$ は，与えられた条件下で $k$ 個の機械を作ることができるときに限り $\it{ True }$ となる関数とします．$\it{ check }$ をうまく（正しい値を十分高速に求められるように）設計できれば，二分法で問題を解くことができます．
$\it{ check }$ を設計するため，ある $k$ について $k$ 個の機械を作れるか否かを判定する方法を考えます．
番号の若いパーツから順に $k$ 個を調達していくと考えます．パーツ $j$ を作るときに利用できる店は $A_i \leq j \leq B_i$ を満たす店 $i$ です．この条件で候補を絞れば，利用可能な各店は区間 $[ -\infty, B_i ]$ のパーツを作ることができると考えることができます．また，番号の若いパーツから決めていく方針なので，$j$ 番のパーツに関する決定が影響を及ぼす範囲は $j$ 以上の番号のパーツのみです．このように考えると，利用可能な店の内，$B_i$ が小さい順に使う方が後の損失（過去の判断において買う個数を敢えて少なくした方が最終的な答えがよくなるなど）を抑えられることが分かります．従って，店は順序対 $( B_i, A_i )$ の辞書順比較で昇順に利用するのが最適ということになります．
というわけで，$\it{ check }( k )$ の実装では，各パーツごとに利用可能な店を列挙した上で $( B_i, A_i )$ の昇順でソートしておき，各パーツごとに優先度の高い店からGreedy にパーツを買うことで最適な買い方をシミュレートできます．この買い方で全てのパーツを $k$ 個ずつ買うことができれば $\it{ check }$ の値は $\it{ True }$ で，$k$ 個に届かないパーツが出た場合は $\it{ check }$ の値は $\it{ False }$ となります．
上記の $\it{ check }$ の実装の場合，一回のシミュレートに $O( MN )$ 時間かかります．解候補の区間幅は $O( N \max\{ K \} )$ なので，二分法の実行にかかる時間は $O( MN \log( N \max\{ K \} ) )$ 時間となります．
コード
using VI = vector< int >; using VVI = vector< vector< int > >; using VPII = vector< pair< int, int > >; #define REP2( i, n ) REP3( i, 0, n ) #define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i ) #define GET_REP( a, b, c, F, ... ) F #define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ ) #define FOR( e, c ) for ( auto &e : c ) #define ALL( c ) begin( c ), end( c ) #define SZ( v ) ( (int)( v ).size() ) #define PB push_back #define BI back_inserter #define MP make_pair class FleetFunding { public: int maxShips( int M, vector <int> K, vector <int> A, vector <int> B ) { const int N = SZ( K ); VVI can_made( M ); REP( i, N ) { REP( j, A[i] - 1, B[i] ) { can_made[j].PB( i ); } } { VPII ps; transform( ALL( A ), begin( B ), BI( ps ), []( const int a, const int b ){ return MP( b, a ); } ); for_each( ALL( can_made ), [&]( VI &row ){ sort( ALL( row ), [&]( const int i, const int j ){ return ps[i] == ps[j] ? i < j : ps[i] < ps[j]; } ); } ); } int lb = 0, ub = 1000000 * N + 1; while ( lb + 1 < ub ) { const int mid = ( lb + ub ) / 2; ( check( M, K, can_made, mid ) ? lb : ub ) = mid; } return lb; } bool check( const int M, const VI &K, const VVI &can_made, const int total ) { const int N = SZ( K ); VI used( N ); REP( t, M ) { int made = 0; FOR( s, can_made[t] ) { const int d = min( total - made, K[s] - used[s] ); made += d; used[s] += d; } if ( made < total ) { return false; } } return true; } };
