Hatena::Grouptopcoder

Wrong Answer -- japlj このページをアンテナに追加 RSSフィード

 | 

2011-01-20

PKU 3266 -- Cow School

| 02:29 | PKU 3266 -- Cow School - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3266 -- Cow School - Wrong Answer -- japlj PKU 3266 -- Cow School - Wrong Answer -- japlj のブックマークコメント

前準備

全ての組 (t[i], p[i]) を t / p の順にソートする。

t[1]/p[1] < t[2]/p[2] < ... < t[n]/p[n]

それで、先生メソッドによる点数を全ての D について先に計算しておく。

T[d] = sum(t[D+1 .. n]) / sum(p[D+1 .. n])

問題の変換

いま、ある D(dとする) について先生メソッドより良い選択の方法が存在して、その選択の方法を B ⊆ {1, 2, ... , n} とする。このBは次の式を満たす。

変形して

こうなる。

上の式に基づいて (t, p) をソートして大きいほうから順に使うことで、 (tの和) / (pの和) を最大にできる組み合わせが見つかり、それをすべてのDについて繰り返せば答えが出る。ただしこれは一回一回ソートが必要なので計算時間は O(N2 log N) となり、間に合わない。

そこで各組 (t[i], p[i]) について、上の式に基づいて直線

y = t[i] - p[i]*x

を考える。

こうすると、各直線について x = T[d] のときの y の値を考えて、その y の値が大きいほうから順に使うと (tの和) / (pの和) を最大にできる組み合わせが見つかるが、これはさっきの O(N2 log N) の言い換えに過ぎないので、これでも間に合わない。

ここで先生メソッドよりも良い選択の方法が存在するとはどういうことか考える。

先生メソッドにより選択されている直線の集合において、 x = T[d] のときの y の値が最も小さいものを y_min とする。また先生メソッドにより選択されていない直線の集合において、 x = T[d] のときの y の値が最も大きい物を y_max とする。

このとき y_min < y_max が成り立てば、y_min を与える直線のかわりに y_max を与える直線を選択することで (tの和) / (pの和) をより大きくすることができるので、先生メソッドより良い選択の方法が存在することがわかる。

そうすると問題は各 d について x = T[d] の時点で、先生メソッドにより選択されている直線のうち最も下のほうにあるものと、選択されていない直線のうち最も上にあるものを探すことに帰着される。

解く

直線の集合のうち最も上あるいは下のものを求めるときは、それぞれ集合の上側エンベロープ(一番上の部分だけをつなげたもの)と下側エンベロープ(一番下の以下略)を考えるとよい。

ここではエンベロープを2分木で管理することにする。各ノードは現在エンベロープに含まれている直線であり、比較のためのキーは直線の傾きを用いる。

直線を追加するときは、その直線とエンベロープとの交点に挟まれる直線を2分木からすべて削除する必要がある。すべての直線は高々1回2分木に挿入され、高々1回削除されるので全体でもコストは O(N log N) で済む。

また、ある x におけるエンベロープの y座標を求めるときは単に2分木を辿ればよいので O(log N) である。

先生メソッドに含まれていない集合の場合をまず考えると、d = 1 から N まで回して、その都度先生メソッドによる集合から省かれる直線を2分木に追加していき、同時に x = T[d] における y座標も計算しておく。

先生メソッドに含まれる集合の場合は、逆に d = N から 1 まで回して、その都度先生メソッドによる集合に取り入れられる直線を2分木に追加していき、同時に x = T[d] におけるy座標が含まれない集合のエンベロープの y座標より小さい場合は d を解に加える。

以上で O(N log N) の解法が完成。

というかこの問題、出典がUSACOでinputに "N (1 ≤ N ≤ 5000 -- except one case where 1 ≤ N ≤ 50,000)" って書いてあるので O(N2 log N) でも9割とか取れるんだよね、たぶん。10点のためにこの努力というのを考えると、コンテスト中にはよっぽど時間が余らない限りは N <= 5000 で満足するべきかなあ。


#include<cstdio>
#include<set>
#include<algorithm>
#include<vector>

using namespace std;

const double EPS = 1e-9, INF = 1e9;

struct pt { int t, p; };
bool operator < (const pt& p, const pt& q) {
  return p.t*q.p < q.t*p.p;
}

struct line {
  int a, b;
  line(int a=0, int b=0) : a(a), b(b) { }
  double y(double x) const { return a*x+b; }
  double intx(const line o) const { return (b-o.b)/double(o.a-a); }
};
bool operator < (const line& p, const line& q) {
  return p.a < q.a;
}

struct bst {
  set<line> s;
  line last;
  double lastx;
  typedef set<line>::iterator iter;
  void insert(const line& p) {
    while(true) {
      iter a = s.lower_bound(p), b = a;
      if(a==s.end()) break;
      if(a->a == p.a) {
	if(a->b <= p.b) { s.erase(a); continue; }
	return;
      }
      if((++b)==s.end()) break;
      double x = a->intx(*b);
      if(p.y(x) < a->y(x)-EPS) break;
      s.erase(a);
    }
    while(true) {
      iter a = s.upper_bound(p), b;
      if(a==s.begin()) break;
      if(a->a == p.a) {
	if(a->b <= p.b) { s.erase(a); continue; }
	return;
      }
      if((b=--a)==s.begin()) break;
      double x = a->intx(*--b);
      if(p.y(x) < a->y(x)-EPS) break;
      s.erase(a);
    }
    iter a = s.lower_bound(p), b = a;
    if(a!=s.end() && a!=s.begin()) {
      double x = a->intx(*--b);
      if(p.y(x) <= a->y(x)+EPS) return;
    }
    s.insert(p);
    if(s.size()==1) last=p, lastx=-INF;
    else if(s.find(last)==s.end() || last.y(lastx)<p.y(lastx)) last=p;
  }
  double upper(double x) {
    double ret = -INF;
    iter p = s.find(last);
    while(p!=s.end() && p->y(x)>ret) ret=p->y(x), p++;
    lastx = x;
    last = *--p;
    return ret;
  }
};

pt P[50000];
double T[50000], upper[50000];

int main()
{
  int N;
  scanf("%d", &N);
  for(int i=0; i<N; ++i)
    scanf("%d%d", &P[i].t, &P[i].p);
  sort(P, P+N);
  for(int i=N-1, t=0, p=0; i>=0; --i) {
    t += P[i].t;
    p += P[i].p;
    T[i] = (double)t/p;
  }
  bst up, lo;
  for(int i=0; i<N-1; ++i) {
    up.insert(line(-P[i].p, P[i].t));
    upper[i+1] = up.upper(T[i+1]);
  }
  vector<int> sol;
  for(int i=N-1; i>=1; --i) {
    lo.insert(line(-P[i].p, -P[i].t));
    if(-lo.upper(-T[i]) < upper[i]-EPS) sol.push_back(i);
  }
  printf("%d\n", sol.size());
  for(int i=(int)sol.size()-1; i>=0; --i)
    printf("%d\n", sol[i]);
  return 0;
}

PKU 2893 -- M × N Puzzle

| 22:35 | PKU 2893 -- M × N Puzzle - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 2893 -- M × N Puzzle - Wrong Answer -- japlj PKU 2893 -- M × N Puzzle - Wrong Answer -- japlj のブックマークコメント

転倒数が目指す配置とmod2で同じか調べるだけ。


#include<cstdio>
#include<cstring>

using namespace std;

int bit[1<<20], seq[1<<20], M, N;
int sum(int x) {
  int ret = 0;
  while(x>0) ret^=bit[x], x-=x&-x;
  return ret;
}
void inc(int x) {
  while(x<M*N) bit[x]^=1, x+=x&-x;
}

int main()
{
  while(scanf("%d%d", &M, &N), M||N) {
    for(int i=0; i<M; ++i)
      for(int j=(i&1)*(N-1); 0<=j&&j<N; j+=(i&1)?-1:1)
	scanf("%d", &seq[i*N+j]);
    memset(bit, 0, sizeof(bit));
    int inv = 0;
    for(int i=1; i<M; i+=2)
      inv ^= (i==M-1 ? (N-1)*(N-2)/2 : N*(N-1)/2) & 1;
    for(int i=M*N-1; i>=0; --i)
      if(seq[i]) inv^=sum(seq[i]-1), inc(seq[i]);
    puts(inv ? "NO" : "YES");
  }
  return 0;
}
 |