naoya_t@topcoder

SRM451 Div1 Medium: BaronsAndCoins

過去問, 練習 | 16:00 |

投稿コード（墜落）

• yが小さい順にソート。先頭にスタート地点(0,0)を入れる
• 後ろから見て行った
• 比べる値が間違っている: dy>1の時は、dx[0]の最大値,dx[dy-1]の最小値の両方を求め、前後と比較する必要がある
• cons,car,cdrマクロはネタ

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define forr(var,from,to) for(int var=(from);var<=(to);var++)
#define forrr(var,from,to) for(int var=(to);var>=(from);var--)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> i_i;
typedef pair<int,pair<int,int> > i_ii;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)
#define sub(p,q) make_pair(car(p)-car(q),cdr(p)-cdr(q))
#define cadr(x) (x).second.first
#define cddr(x) (x).second.second

class BaronsAndCoins {
 public:
  int getMaximum(vector <int> x, vector <int> y) {
    int N=sz(x);

    vector<i_i> p(N);
    rep(i,N) p[i]=cons(y[i],x[i]); p.pb(cons(0,0)); N++;
    
    vector<vector<i_i> > tt(N,vector<i_i>(N));
    sort(all(p)); // reverse(all(p));
    
    forr(i,0,N-2){
      forr(j,i+1,N-1){
        tt[i][j] = sub(p[j],p[i]);
      }
    }

    priority_queue<pair<int,pair<int,int> > > pq;  // j,cnt,ymax
    forr(j,1,N-1) pq.push(cons(j,cons(1,INT_MAX)));
    map<int,int> score;

    int cntmax=0;
    while(!pq.empty()){
      i_ii x = pq.top(); pq.pop();
      int j=car(x),cnt=cadr(x),last_dxmax = cddr(x);
      if (found(score,j) && score[j]>cnt) continue;
      score[j] = cnt;
      forrr(i,0,j-1){
        i_i dif = tt[i][j];
        int dy=car(dif),dx=cdr(dif); if (dy==0) continue;
        int dxmax = (dx - (dy*(dy-1)/2))/dy;
        if (dxmax <= 0 || dxmax >= last_dxmax) continue;
        if (i==0) {
          if (cnt>cntmax) cntmax = cnt;
        } else {
          pq.push(cons(i,cons(cnt+1,dxmax)));
        }
      }
    }
    return cntmax;
  }
};

最終コード (Passed System Test)

• 前からダイクストラ的に

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define FORR(var,from,to) for(int var=(to);var>=(from);var--)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> i_i;
typedef pair<int,pair<int,int> > i_ii;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)
#define cadr(x) (x).second.first
#define cddr(x) (x).second.second

class BaronsAndCoins {
  vector<i_i> p;
  vector<vector<i_i> > tt, sx;

 public:
  int getMaximum(vector <int> x, vector <int> y) {
    int N=sz(x);

    p.resize(N);
    rep(i,N) p[i]=cons(x[i],y[i]);
    p.pb(cons(0,0)); N++;
    sort(all(p));
    
    tt.resize(N);
    sx.resize(N);
    rep(i,N) {
      tt[i].resize(N);
      sx[i].resize(N);
    }
        
    FOR(i,0,N-2){
      FOR(j,i+1,N-1){
        int dx = car(p[j]) - car(p[i]);
        int dy = cdr(p[j]) - cdr(p[i]);
        if (dy==0) continue;
        
        int sx0max = (dx - (dy*(dy-1)/2))/dy;
        if (sx0max <= 0) continue;
        int sx1min = sx0max + (dy-1) + ((dx - (dy*(dy-1)/2) - sx0max*dy)?1:0);

        tt[i][j] = cons(dx,dy);
        sx[i][j] = cons(sx0max,sx1min);
      }
    }

    vector<map<int,int> > sc(N,map<int,int>());
    sc[0][0] = 0; // dmin, cnt

    int cntmax = 0;
    FOR(i,0,N-2) {
      tr(sc[i],it) {
        int dmin = car(*it), cnt = cdr(*it);
        FOR(j,i+1,N-1) {
          if (car(tt[i][j]) <= 0) continue;

          i_i s = sx[i][j];
          int smin=car(s), smax=cdr(s);
          if (dmin < smin) {
            int cnt_next = cnt + 1;
            if (found(sc[j],smax)) {
              sc[j][smax] = max(cnt_next,sc[j][smax]);
            } else {
              sc[j][smax] = cnt_next;
            }
            if (cnt_next > cntmax) cntmax = cnt_next;
          }
        }
      }
    }
    return cntmax;
  }
};