naoya_t@hatenablog

いわゆるチラシノウラであります

SRM580

リハビリの為、飽きるまで1日1問解いてみようかと

Easy ("EelAndRabbit", 250)

Spaghetti Sourceの区分木(segment tree)を使って書こうと思ったらうまく行かなかった。
(半開区間で探索していた罠は躱せたがqueryで出てこないのがある)
たぶん自分の使い方が間違ってるんだと思う。

で、setとか使って書き直し。

  • 2回うなぎを捕まえに行くので、1回目で捕まえたうなぎは2回目には存在しない
  • それで最大を求めるとか面倒だし50匹しかいない(位置を100箇所調べればいいじゃん)なら全パターン見てしまえばいい
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;
typedef vector<long long> vll;
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> i_i;
#define cons(x,y) make_pair((x),(y))

class EelAndRabbit {
 public:
  int getmax(vector<int> l, vector<int> t) {
    set<int> points;
    vector<pair<int,int> > segs;

    int N = sz(l);
    rep(i, N){
      int s=t[i], e=s+l[i];
      points.insert(s);
      points.insert(e);
      segs.pb(cons(s, e));
    }

    map<int, set<int> > mp;
    int M = 0;

    vector<int> pointv(all(points));
    int P = sz(pointv);

    rep(p, P){
      int point = pointv[p];
      set<int> s;
      rep(i,N){
        if (segs[i].first <= point && point <= segs[i].second) {
          s.insert(i);
        }
      }
      mp[p] = s;
      ++M;
    }

    int smax = 0;
    for(int i=0; i<M-1; ++i) {
      for (int j=i+1; j<M; ++j) {
        set<int> s;
        tr(mp[i],it) s.insert(*it); // ここunionを求めようとしてる
        tr(mp[j],it) s.insert(*it);
        smax = max(smax, sz(s));
      }
    }
    return smax;
  }
};

unionを求めるのは

    int smax = 0;
    for(int i=0; i<M-1; ++i) {
      for (int j=i+1; j<M; ++j) {
        vector<int> u(N);
        typeof(u.end()) it = set_union(all(mp[i]), all(mp[j]), u.begin());
        smax = max(smax, (int)(it - u.begin()));
      }
    }
    return smax;

とか書けるけどね。