JOI春合宿2012 Day1 - Algorithmer’s note

多分 JOI 史上最難問セット。
満点取りに行こうとしましたが、90+100+100だったので（かつ他の人より高い点が得られたので）よしとします。

Building 2

頂点数が高々 100,000 の木が与えられる。木の頂点間のパスについて、部分単調増加列を考える時、最長の長さを求めよ。

史上最難問といっても過言ではない問題。
木 DP をして、適当にマージすると O(N log^2 N) で解けるらしい。
下のコードでは、重心分解を用いて O(N log^2 N) で解いているが、定数倍が 10 倍ぐらい違うので TLE。90点

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

#define debug fprintf(stderr, "line: %d\n", __LINE__); fflush(stdout)

struct queue2
{
  pair<int, int> val[100000];
  int qFirst, qLast;
  queue2()
  {
    qFirst = qLast = 0;
  }
  void push(pair<int, int> v)
  {
    val[qLast++] = v;
  }
  pair<int, int> front()
  {
    return val[qFirst];
  }
  void pop()
  {
    if(++qFirst == qLast){
      qFirst = qLast = 0;
    }
  }
  bool empty(){ return qFirst == qLast; }
};

inline int max_(int a, int b)
{
  return (a>b) ? a : b;
}

struct seg_tree
{
  //point-set, range-maximum segment tree
  static const int SZ = 1<<17;
  int data[SZ*2];

  seg_tree()
  {
    clear(SZ);
  }

  void clear(int cSize)
  {
    int left=SZ, right=cSize+SZ;
    while(left){
      for(int i=left;i<right;i++) data[i] = 0;
      left >>= 1;
      right = (right+1) >> 1;
    }
  }

  void set(int p, int v)
  {
    p += SZ;
    data[p] = v;
    p >>= 1;
    while(p){
      data[p] = max(data[p*2], data[p*2+1]);
      p >>= 1;
    }
  }

  int query(int L, int R)
  {
    L += SZ; R += SZ;
    int ret = 0;
    while(L != R){
      //if(L&1) ret = max(ret, data[L++]);
      ret = max(ret, (L&1) * data[L++]);
      //if(R&1) ret = max(ret, data[--R]);
      ret = max(ret, (R&1) * data[R-1]);
      L >>= 1; R >>= 1;
    }
    return ret;
  }

  int excl(int p){ return max(query(0, p), query(p+1, SZ)); }
  int at(int p){ return data[p+SZ]; }
};

struct node
{
  node *back, *next, *rev;
  int src, dest;
};

int N, H[100000], ret=0;
node *con[100000], pool[400000]; int pLast=0;
pair<int, int> sorter[100010]; int idx[100000];
int lval[100000];

node* _add_edge(int s, int d)
{
  node *ret = &(pool[pLast++]);
  ret->back = con[s];
  ret->next = con[s]->next;
  if(ret->next) ret->next->back = ret;
  ret->back->next = ret;
  ret->src = s; ret->dest = d;
  return ret;
}

void add_edge(int s, int d)
{
  node *e1 = _add_edge(s, d), *e2 = _add_edge(d, s);
  e1->rev = e2;
  e2->rev = e1;
}

void remove_edge(node* nd)
{
  nd->back->next = nd->next;
  if(nd->next) nd->next->back = nd->back;
}

pair<int, int> cent; int tSize;

int find_size(int p, int back)
{
  int ret = 1;
  for(node* nd=con[p]->next; nd!=NULL; nd=nd->next){
    if(nd->dest != back) ret += find_size(nd->dest, p);
  }
  return ret;
}

int find_centroid(int p, int back)
{
  int tmp=0, sum=1;
  for(node* nd=con[p]->next; nd!=NULL; nd=nd->next){
    if(nd->dest != back){
      int val = find_centroid(nd->dest, p);
      tmp = max(tmp, val);
      sum += val;
    }
  }
  tmp = max(tmp, tSize - sum);
  cent = min(cent, make_pair(tmp, p));

  return sum;
}

int eLeft[100000], eRight[100000], ePos;
pair<int, int> vPos[100000]; int vLast;

void euler_tour(int p, int back)
{
  eLeft[p] = ePos++;
  vPos[vLast++] = make_pair(H[p], p);
  for(node* nd=con[p]->next; nd!=NULL; nd=nd->next){
    if(nd->dest != back){
      euler_tour(nd->dest, p);
    }
  }
  eRight[p] = ePos;
}

seg_tree sIncl, sDecl;
seg_tree inclC;

void add_inclC(int p, int back)
{
  if(back != -1){
    inclC.set(idx[p], sDecl.at(eLeft[p]));
    //printf("  %d %d: %d\n", p, H[p], sDecl.at(eLeft[p]));
  }
  for(node* nd=con[p]->next; nd!=NULL; nd=nd->next){
    if(nd->dest != back) add_inclC(nd->dest, p);
  }
}

void rem_inclC(int p, int back)
{
  inclC.set(idx[p], 0);
  for(node* nd=con[p]->next; nd!=NULL; nd=nd->next){
    if(nd->dest != back) rem_inclC(nd->dest, p);
  }
}

void find_best(int p, int back)
{
  //ret = max(ret, sIncl.at(eLeft[p]) + inclC.query(idx[lower_bound(sorter, sorter+N+1, make_pair(H[p]+1, -1))->second], N))
  ret = max(ret, sIncl.at(eLeft[p]) + inclC.query(lval[p], N));
  for(node* nd=con[p]->next; nd!=NULL; nd=nd->next){
    if(nd->dest != back) find_best(nd->dest, p);
  }
}

seg_tree p_selfA, p_selfB;

void find_pself(int p, int back, int pval, int root)
{
  if(H[p] < pval){
    p_selfA.set(root, max(p_selfA.at(root), sIncl.at(eLeft[p])));
  }
  if(H[p] > pval){
    p_selfB.set(root, max(p_selfB.at(root), sDecl.at(eLeft[p])));
  }

  for(node* nd=con[p]->next; nd!=NULL; nd=nd->next){
    if(nd->dest != back) find_pself(nd->dest, p, pval, root);
  }
}

void find_best_pself(int p, int back, int pval, int root)
{
  ret = max(ret, sIncl.at(eLeft[p]) + inclC.query(lval[p], N));
  if(H[p] < pval){
    p_selfA.set(root, max(p_selfA.at(root), sIncl.at(eLeft[p])));
  }
  if(H[p] > pval){
    p_selfB.set(root, max(p_selfB.at(root), sDecl.at(eLeft[p])));
  }

  for(node* nd=con[p]->next; nd!=NULL; nd=nd->next){
    if(nd->dest != back) find_best_pself(nd->dest, p, pval, root);
  }
}

queue2 mQ;

void solve(int _p)
{
  cent = make_pair(1000000, 0);
  tSize = find_size(_p, -1);
  if(tSize == 1) return;
  if(tSize < ret) return;
  find_centroid(_p, -1);

  int p = cent.second;
  //solve;
  ePos = 0; vLast = 0;
  euler_tour(p, -1);
  sort(vPos, vPos + tSize);

  //about sIncl
  //queue<pair<int, int> > mQ;
  for(int i=0;i<=tSize;i++){
    if(i==tSize || (i>0 && vPos[i].first != vPos[i-1].first)){
      while(!mQ.empty()){
	sIncl.set(mQ.front().first, mQ.front().second + 1);
	mQ.pop();
      }
    }
    if(i<tSize){
      mQ.push(make_pair(eLeft[vPos[i].second],
			sIncl.query(eLeft[vPos[i].second], eRight[vPos[i].second])));
    }
  }
  //about sDecl
  for(int i=tSize-1;i>=-1;i--){
    if(i==-1 || (i<tSize-1 && vPos[i].first != vPos[i+1].first)){
      while(!mQ.empty()){
	sDecl.set(mQ.front().first, mQ.front().second+1);
	mQ.pop();
      }
    }
    if(i>=0){
      mQ.push(make_pair(eLeft[vPos[i].second],
			sDecl.query(eLeft[vPos[i].second], eRight[vPos[i].second])));
    }
  }

  //printf("%d:\n", p);
  //find best solution
  add_inclC(p, -1);
  for(node* nd=con[p]->next; nd!=NULL; nd=nd->next){
    //printf("%d %d\n", nd->dest, p);
    rem_inclC(nd->dest, p);
    //find_best(nd->dest, p);
    find_best_pself(nd->dest, p, H[p], nd->dest);
    add_inclC(nd->dest, p);

    //p itself
    //find_pself(nd->dest, p, H[p], nd->dest);
  }

  for(node* nd=con[p]->next; nd!=NULL; nd=nd->next){
    ret = max(ret, p_selfA.at(nd->dest) + p_selfB.excl(nd->dest) + 1);
    ret = max(ret, p_selfB.at(nd->dest) + p_selfA.excl(nd->dest) + 1);
  }
  for(node* nd=con[p]->next; nd!=NULL; nd=nd->next){
    p_selfA.set(nd->dest, 0);
    p_selfB.set(nd->dest, 0);
  }

  rem_inclC(p, -1);

  //next
  sIncl.clear(tSize);
  sDecl.clear(tSize);
  for(node* nd=con[p]->next; nd!=NULL; nd=nd->next){
    remove_edge(nd);
    remove_edge(nd->rev);
    solve(nd->dest);
  }
}

int main()
{
  int x, y;
  scanf("%d", &N);
  for(int i=0;i<N;i++) scanf("%d", H+i);
  for(int i=0;i<N;i++){
    con[i] = &(pool[pLast++]);
    con[i]->back = con[i]->next = NULL;
    sorter[i] = make_pair(H[i], i);
  }
  sort(sorter, sorter + N);
  sorter[N] = make_pair(2100000000, N);
  idx[N] = N;
  for(int i=0;i<N;i++) idx[sorter[i].second] = i;
  for(int i=0;i<N;i++){
    lval[i] = idx[lower_bound(sorter, sorter+N+1, make_pair(H[i]+1, -1))->second];
  }

  for(int i=0;i<N-1;i++){
    scanf("%d%d", &x, &y);
    --x; --y;

    add_edge(x, y);
  }

  solve(0);

  printf("%d\n", ret);

  return 0;
}

Fish

赤青緑の三種の魚がたくさんいる。魚を何匹か選んで、水槽に入れる。ただし、魚は自分の体長の半分以下の魚を食べるので、そのような魚を混ぜてはいけない。水槽に 1 匹以上の魚を入れる時、赤青緑の魚の組み合わせは何通り考えられるか求めよ。

尺取り法で、直方体を組み合わせた図形の全体の体積を求める問題に還元できる。これは適当にがんばると O(N log N) で解ける。

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

#define debug fprintf(stderr, "line %d\n", __LINE__); fflush(stderr)
typedef long long i64;
using namespace std;

struct seg_tree
{
  static const int SZ=1<<19;
  int data[SZ*2];
  i64 sum[SZ*2];

  seg_tree()
  {
    for(int i=0;i<SZ*2;i++){
      data[i] = -1;
      sum[i] = 0;
    }
  }

  void apply(int pL, int pR, int qL, int qR, int value, int depth)
  {
    if(qR <= (pL << depth) || (pR << depth) <= qL) return;
    if(qL <= (pL << depth) && (pR << depth) <= qR){
      data[pL] = value;
      sum[pL] = (i64)value * (1 << depth);
      return;
    }
    if(data[pL]!=-1){
      data[pL*2] = data[pL*2+1] = data[pL];
      sum[pL*2] = sum[pL*2+1] = sum[pL] / 2;
    }
    data[pL] = -1;
    apply(pL<<1, (pL<<1)+1, qL, qR, value, depth-1);
    apply((pL<<1)+1, pR<<1, qL, qR, value, depth-1);
    sum[pL] = sum[pL*2] + sum[pL*2+1];
  }

  void apply(int qL, int qR, int value)
  {
    apply(1, 2, qL+SZ, qR+SZ, value, 19);
  }

  i64 query(int pL, int pR, int qL, int qR, int depth)
  {
    if(qR <= (pL << depth) || (pR << depth) <= qL) return 0;
    if(qL <= (pL << depth) && (pR << depth) <= qR){
      return sum[pL];
    }
    if(data[pL]!=-1){
      return (i64)data[pL] * (min(pR<<depth, qR) - max(pL<<depth, qL));
    }
    return query(pL<<1, (pL<<1)+1, qL, qR, depth-1) + 
      query((pL<<1)+1, pR<<1, qL, qR, depth-1);  
  }

  i64 query(int qL, int qR)
  {
    return query(1, 2, qL+SZ, qR+SZ, 19);
  }
};

struct seg_tree2
{
  static const int SZ=1<<19;
  int data[SZ*2];

  seg_tree2()
  {
    for(int i=0;i<SZ*2;i++) data[i] = 0;
  }

  void set(int p, int v)
  {
    p += SZ;
    while(p){
      data[p] = max(data[p], v);
      p >>= 1;
    }
  }

  int find(int v)
  {
    int p=1;
    while(p<SZ){
      if(data[p*2+1]>v) p = p*2+1;
      else p = p*2;
    }
    return p-SZ;
  }

  int at(int p){ return data[p+SZ]; }
};

int N;
pair<int, int> fish[500010];
pair<int, pair<int, int> > query[500010];

seg_tree seg1;
seg_tree2 seg2;

void test()
{
  seg1.apply(0, 2, 5);
  printf("%lld\n", seg1.query(0, 2));
}

int main()
{
  //test();
  //return 0;
  int l; char in[5];
  scanf("%d", &N);
  for(int i=0;i<N;i++){
    scanf("%d%s", &l, in);
    if(in[0]=='R') fish[i] = make_pair(l, 0);
    if(in[0]=='G') fish[i] = make_pair(l, 1);
    if(in[0]=='B') fish[i] = make_pair(l, 2);
  }
  sort(fish, fish+N);
  reverse(fish, fish+N);

  //making query;
  int rg=0, cnt[3];
  for(int i=0;i<3;i++) cnt[i] = 0;
  for(int i=0;i<N;i++){
    while(rg<N && fish[i].first < fish[rg].first*2){
      cnt[fish[rg++].second]++;
    }
    //add query;

    query[i] = make_pair(cnt[0], make_pair(cnt[1]+1, cnt[2]+1));
    //printf("%d--%d,%d\n", cnt[0], cnt[1]+1, cnt[2]+1);
    cnt[fish[i].second]--;
  }

  sort(query, query+N);
  i64 total=0, ret=0; int qp=N-1;
  for(int i=500000;i>=0;i--){
    while(qp>=0 && query[qp].first==i){
      //make range[0, q.second.first) :max= q.second.second;
      int lp=seg2.find(query[qp].second.second);
      if(seg2.at(lp) > query[qp].second.second) ++lp;
      //printf("%d %d\n", lp, query[qp].second.first);
      //printf("%d,%d: %d\n", query[qp].second.first, query[qp].second.second, lp);
      if(query[qp].second.first > lp){
	total += (i64)query[qp].second.second * (query[qp].second.first - lp);
	total -= seg1.query(lp, query[qp].second.first);
	seg1.apply(lp, query[qp].second.first, query[qp].second.second);
	seg2.set(query[qp].second.first-1, query[qp].second.second);
      }
      --qp;
    }

    //if(total) printf("%d: %lld\n", i, total);
    ret += total;
  }

  printf("%lld\n", ret-1);

  return 0;
}

JOI Flag

2^K × 2^K の盤面にJOI旗を作る。大きさ 2^0 × 2^0 の JOI 旗は J, O, I の 1 文字からなる。2^K × 2^K の JOI 旗は、盤面を 4 つに分けた時に、4 つの部分が「Jだけ」「Oだけ」「Iだけ」「小さい JOI 旗」になるものとして定義される。全体を JOI 旗にするのに必要な操作のコストを求めよ。文字が書いてないマスにはコスト 0 で文字を書けるが、文字の変更コストは 1 である。文字は N 箇所に書いてある。

Trie のようなものを作って DP すると O(NK) で解ける。

#include<cstdio>
#include<algorithm>

using namespace std;

struct node
{
  node* child[4];
  int dp[4];
};

node *root, pool[100000];
int pLast=0;

node* alloc()
{
  node* ret = &(pool[pLast++]);
  for(int i=0;i<4;i++) ret->child[i] = NULL;
  for(int i=0;i<4;i++) ret->dp[i] = -1;
  return ret;
}

void solve(node* nd)
{
  if(nd->dp[0]!=-1) return;
  for(int i=0;i<4;i++) if(nd->child[i]) solve(nd->child[i]);

  for(int i=0;i<3;i++){
    nd->dp[i] = 0;
    for(int j=0;j<4;j++)
      if(nd->child[j]) nd->dp[i] += nd->child[j]->dp[i];
  }

  int perm[4] = {0, 1, 2, 3};
  int tmp = 1000000;
  do{
    int scr = 0;
    for(int i=0;i<4;i++)
      if(nd->child[i]) scr += nd->child[i]->dp[perm[i]];
    tmp = min(tmp, scr);
  }while(next_permutation(perm, perm+4));
  nd->dp[3] = tmp;
}

int K, N;

void add(int x, int y, int v)
{
  int depth = K;
  node* now = root;
  while(depth){
    int nx=0, bas=1<<(depth-1);
    if(x<bas && y<bas){
      nx = 0;
    }else if(x>=bas && y<bas){
      x -= bas;
      nx = 1;
    }else if(x<bas && y>=bas){
      y -= bas;
      nx = 2;
    }else if(x>=bas && y>=bas){
      x -= bas;
      y -= bas;
      nx = 3;
    }
    if(now->child[nx]==NULL) now->child[nx] = alloc();
    now = now->child[nx];
    --depth;
  }
  now->dp[0] = now->dp[1] = now->dp[2] = 1;
  now->dp[v] = 0;
  now->dp[3] = 0;
}

int main()
{
  int x, y; char c[5];
  scanf("%d%d", &K, &N);

  root = alloc();
  for(;N--;){
    scanf("%d%d%s", &x, &y, c);
    --x; --y;
    if(c[0]=='J') add(x, y, 0);
    if(c[0]=='O') add(x, y, 1);
    if(c[0]=='I') add(x, y, 2);
  }

  solve(root);

  printf("%d\n", root->dp[3]);
  return 0;
}