保存されている過去のバージョンの一覧

2015年01月28日23時25分18秒

dwangoプログラミングコンテスト予選 D問題 - タクシー

Source

dwangoプログラミングコンテスト予選
問題文

問題概要

長さ $L$ の円周上に，街が $N$ 個ある．
街は時計回りに $1,2,\ldots,N$ と番号がついていて，街 $1$ から時計回り方向での街 $k$ までの距離は $A_k$ である．
街 $k$ からは $B_k$ 人の参加者がいて，街 $k$ の会場の収容人数は $C_k$ 人である（会場がない場合は $C_k=0$）．
全部の街を通じての総参加人数と，全ての会場の総収容人数は等しい．
それぞれの参加者はどこかの会場に収容する．
それぞれの人の移動距離の総和の最小値を求める問題．

解法

もし，街 $1$ と街 $N$ が繋がっていない直線上であれば，まだどの会場に行くか割り当てていない最も左の街にいる参加者は，まだ開いている最も左の会場に割り当てるというふうに，貪欲法により割り当てれば良い．
今は円周上であるから，$3$ 周分ぐらいに拡張し，街 $k+N$ の位置は $A_k+L$ にある，街 $k-N$ の位置は $A_k-L$ にあるとしておく．
街 $k-N, k+N$ の参加者，会場の収容人数は 街 $k$ と同じとする．
総参加人数を $s = \sum B_k$ と書く．
ここで，会場は普通に街 $1$ から街 $N$ のを使うとした時，参加者は連続する $s$ 人の参加者（街 $k-N$ や $k+N$ の参加者も考える）を考え，貪欲に割り振れば良い．
連続する $s$ 人の参加者はどの部分から取るかを三分探索すれば良い．
時間計算量は $O(N \log s)$ 程度．

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 mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#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);}
void reader(ll *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);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}

void writer(ll x, char c){int s=0,m=0;char f[20];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');}

int N, L;
int A[111111], B[111111], C[111111];

ll dis[311111];
ll cur[311111];

ll check(ll val, ll sum){
  int i, j;
  ll k;
  ll res = 0;

  rep(i,N) cur[i] = B[i];
  rep(i,N) cur[i+N] = B[i];
  rep(i,N) cur[i+N+N] = B[i];

  j = N;
  if(val < 0) val += sum, j = 0;
  while(val > 0){
    if(cur[j] <= 0) { j++; continue; }
    k = min(cur[j], val);
    cur[j] -= k;
    val -= k;
  }
  REP(i,N,2*N){
    if(cur[i] >= 0) continue;
    while(cur[j] <= 0) j++;
    k = min(-cur[i], cur[j]);
    cur[i] += k;
    cur[j] -= k;
    res += k * max(dis[i]-dis[j], dis[j]-dis[i]);
    i--;
  }
  return res;
}

int main(){
  int i, j, k;
  ll res = 1000000000000000000LL, sum;
  ll X, Y, C1, C2, D1, D2, Z;

  reader(&N,&L);
  rep(i,N) reader(A+i,B+i,C+i), B[i] -= C[i];

  rep(i,N) dis[i] = A[i];
  rep(i,N) dis[i+N] = A[i]+L;
  rep(i,N) dis[i+N+N] = A[i]+L+L;

  sum = 0;
  rep(i,N) if(B[i] > 0) sum += B[i];

  X = -sum; Y = sum;
  while(X < Y - 10){
    C1 = (X+X+Y) / 3;
    C2 = (X+Y+Y) / 3;
    D1 = check(C1, sum);
    D2 = check(C2, sum);
    res = min(res, min(D1,D2));
    if(D1 < D2) Y = C2; else X = C1;
  }

  while(X <= Y){
    Z = check(X, sum);
    res = min(res, Z);
    X++;
  }

  writerLn(res);

  return 0;
}

Current time: 2024年04月18日18時36分59秒
Last modified: 2015年01月28日23時25分18秒 (by laycrs)
Tags: Competitive_Programming AtCoder dwango2015-prelims
トップページに戻る

Logged in as: unknown user (not login)

ログイン：