Moo University - Team Tryouts(4)

稲葉さんスゴーということで、ちょっと質問メールをしてみたらソースコードばかりか丁寧な解説まで頂いた。転載も問題なしということでどどーんと公開。ほんと、ありがとうございます>稲葉さん
他のチャレンジャーも、これを参考に頑張っておくんなまし。

解説

foreach( h ) {
// 各hごとに、heightの最小が h の場合の最大チームサイズを求める
// あとでそれのさらにmaxをとれば答え

ranges =
foreach( (H,W) ) {
// 各牛について、「この牛がチームに入れるとしたら、widthの最小wは幾つか？」を考える

if( h <= H ) // 今はheightの最小がhの場合なので、それ以上の牛しかそもそもチームに入れない
if( A*(H-h) <= C ) // あんまりデカすぎる牛もそもそもチームに入れない
{
// この牛がチームに入れるとしたら、
// A*(H-h) + B*(W-w) <= C じゃなきゃいけないので、
// 式変形すると W - (C-A*(H-h))/B <= w
// よって、この牛がチームに入る条件は
// w が範囲 W-(C-A*(H-h))/B <= w <= W におさまってること

ranges ~= [W-(C-A*(H-h))/B, W]
}
}

// 例えば ranges[0] と ranges[1] に重なりがあれば、その範囲から
// 最小のwをとってくれば２頭のチームが作れる。
// ranges[0] と ranges[1] と range[2] が３つ重なってる範囲があれば、
// そこからwをとってくれば３頭のチームが作れる。
//
// … てな感じなので、最大チームサイズを求めるには、
// 一番たくさんrangesが重なってる範囲の、その重なり個数を求めればOK

// これは有名なアルゴリズムがある
// 範囲の始点終点を全部まとめてsortして
range_edge =
foreach( (begin, end) in ranges )
{range_edge ~= begin, range_edge ~= end}
range_edge.sort

// こんな風に数えればOK
kasanari=0, maxKasanari=0;
foreach( r in range_edge ) {
if( r はどれかの始点 ) kasanari++
else ( 終点 ) kasanari--

if( maxKasanari < kasanari )
maxKasanari = kasanari
}
}

ソースコード

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;
int main()

{

  int N,A,B,C; cin>>N>>A>>B>>C;

  vector<int> h, w;

  while(N--)

  {

    int ht,wt; cin>>ht>>wt;

    h.push_back(ht*A);

    w.push_back(wt*B);

  }
  int maxq = 0;

  for(int k=0; k!=h.size(); ++k)

  {

    vector<int> es;

    for(int i=0; i!=h.size(); ++i)

      if( h[k]<=h[i] && h[i]-h[k]<=C )

        es.push_back( 2*(w[i]-C+h[i]-h[k]) ),

        es.push_back( 2*w[i]+1 );

    sort( es.begin(), es.end() );
    for(int i=0,q=0; i!=es.size(); ++i)

      if( maxq < (es[i]&1?--q:++q) )

        maxq = q;

  }

  cout << maxq << endl;

}