Codeforces Good Bye 2014 E問題 - New Year Domino

Source

Codeforces Good Bye 2014 E問題 (2750pt)
Problem description

問題概要

$1$ 次元の直線上に $N$ 個のドミノがあって,左から $k$ 個目のドミノは,場所 $P_k$ にあって,高さが $L_k$ である.
ドミノは必ず右向きに倒すとして,あるドミノが倒れたら,そのドミノから右側にあるドミノで距離が倒れたドミノの高さ以下の位置にあるドミノもすべて倒れる.
また,コストを $1$ 支払うことで,任意の $1$ つのドミノの高さを $1$ だけ高くすることができる.
クエリが $Q$ 個与えられるので,各クエリ $k$ では,$X_k$ 番目のドミノを倒した時,$Y_k$ 番目のドミノも倒れるようにするための最小コストを求める問題.

解法

厳密な計算量は見積もりにくいが以下の方法で通した.
クエリをソートしてあげて,$Y_k$ が小さい順に並べておく.
まず最初に,なんでも良いのでRange Minimum Query,$P_i+L_i, P_{i+1}+L_{i+1}, \ldots, P_j+L_j$ の最大値を $O(\log N)$ などで求められるようにしておく.
そうすると,ある区間のドミノが倒れた時,最も右まで届くドミノの位置を計算でき,次の位置のドミノを倒すための最小コストを計算できるようになる.
(考察として,次の位置のドミノを倒すと,そのドミノによって届く距離が増えるため,(次の位置のドミノを利用せず)次の次の位置のドミノを倒せるようになるまでドミノを伸ばすなどは損なので考えなくて良い)
次に前処理として,各ドミノについて,そのドミノを倒すと倒れるドミノの範囲を二分探索を用いて計算する.
その後,各クエリに対して,$X_k$ から初めて $Y_k$ が倒れるまでの最小コストを求めていくわけだが,何もせずに $Y_k$ を倒せないなら,次のドミノを倒せるまでのコストを求め,その後,そのドミノを倒した場合の $Y_k$ が倒れるまでのコストを求めるという感じで再帰的に処理をする.
その際,経路圧縮して,計算した各始点について,$Y_k$ を倒すまでの最小コストと,そのコストでどこまでのドミノが倒れるかというのをメモしていく.

他に計算量が簡単に見積もれる方法としてダブリングを行う方法がある.
各ドミノ $k$ に対して,勝手に倒れ,役に立たないドミノ($P_i+L_i < P_j+L_j,\ k \leq j < i$ なる $j$ が存在したらドミノ $i$ は役に立たない)を適宜無視して,$2^x$ 個先のドミノを倒すまでの最小コストを求めておけば良い.

C++のスパゲッティなコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define READER_BUF_SIZE 1048576
#define WRITER_BUF_SIZE 1048576
int reader_pt=READER_BUF_SIZE,reader_last;char reader_buf[READER_BUF_SIZE];
int writer_pt=0;char writer_buf[WRITER_BUF_SIZE];
#define mygc(c) {if(reader_pt==READER_BUF_SIZE)reader_pt=0,reader_last=fread(reader_buf,sizeof(char),READER_BUF_SIZE,stdin);(c)=reader_buf[reader_pt++];}
#define mypc(c) {if(writer_pt==WRITER_BUF_SIZE)writer_pt=0,fwrite(writer_buf,sizeof(char),WRITER_BUF_SIZE,stdout);writer_buf[writer_pt++]=(c);}
#define myed {fwrite(writer_buf,sizeof(char),writer_pt,stdout);writer_pt=0;}

#define ll long long

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

template<class T1, class T2, class T3> void sort(int N, T1 a[], T2 b[], T3 c[], void *mem){int i;pair<T1,pair<T2,T3> > *r=(pair<T1,pair<T2,T3> >*)mem;rep(i,N)r[i].first=a[i],r[i].second.first=b[i],r[i].second.second=c[i];sort(r,r+N);rep(i,N)a[i]=r[i].first,b[i]=r[i].second.first,c[i]=r[i].second.second;}

template<class T> void* doublingRMQBuild(T arr[], int n, int **res, void *workMemory){int i,k,h;*res=(int*)workMemory;rep(i,n)(*res)[i]=i;for(k=1;;k++){h=(1<<(k-1));if(h>=n)break;rep(i,n){(*res)[n*k+i]=(*res)[n*(k-1)+i];if(i+h<n&&arr[(*res)[n*k+i]]>arr[(*res)[n*(k-1)+i+h]])(*res)[n*k+i]=(*res)[n*(k-1)+i+h];}}return (void*)((*res)+n*k);}
template<class T> int doublingRMQQuery(T arr[], int n, int rmq[], int a, int b){int d,w=b-a+1,A,B;for(d=0;(1<<(d+1))<=w;d++);A=rmq[n*d+a];B=rmq[n*d+b-(1<<d)+1];return arr[A]>arr[B]?B:A;}

int N, Q;
int P[222222], L[222222];
int X[222222], Y[222222], ind[222222];
ll res[222222];

int go[222222]; ll cost[222222];

int reach[222222], *rmq;

ll solve(int x, int y){
  int i, j, k;
  ll tmp;
  int p;

  if(go[x] >= y) return cost[x];
  
  k = doublingRMQQuery(reach, N, rmq, x, go[x]);
  p = -reach[k];

  tmp = solve(go[x]+1, y);
  cost[x] += (P[go[x]+1] - p) + tmp;
  go[x] = go[go[x]+1];

  return cost[x];
}

int main(){
  int i, j, k;
  int x, p;
  void *mem = malloc(150000000);

  reader(&N);
  rep(i,N) reader(P+i,L+i); P[N] = 2100000000;
  reader(&Q);
  rep(i,Q) reader(X+i,Y+i), X[i]--, Y[i]--, ind[i] = i;
  sort(Q, Y, X, ind, mem);

  rep(i,N) reach[i] = -(P[i] + L[i]);
  mem = doublingRMQBuild(reach, N, &rmq, mem);
  
  rep(i,N) cost[i] = 0, go[i] = i;
  
  rep(x,N){
    p = -reach[x];
    for(;;){
      j = upper_bound(P, P+N+1, p) - P - 1;
      if(j == go[x]) break;

      go[x] = j;
      k = doublingRMQQuery(reach, N, rmq, x, go[x]);
      p = -reach[k];
    }
  }
  
  rep(i,Q){
    res[ind[i]] = solve(X[i], Y[i]);
  }
  rep(i,Q) writerLn(res[i]);

  myed;
  return 0;
}

Current time: 2017年09月21日05時00分04秒
Last modified: 2015年01月11日08時36分36秒 (by laycrs)
Tags: Competitive_Programming Codeforces Codeforces_Good_Bye_2014
トップページに戻る

Logged in as: unknown user (not login)

ログイン: