第2回 ドワンゴからの挑戦状 本選 B問題 - 道迷い

Source

第2回 ドワンゴからの挑戦状 本選（オープンコンテスト）
問題文（オープンコンテスト）

問題概要

一次元の無限に長い道があり，ニワンゴ君は今座標 $0$ にいる．
ニワンゴ君はdwangoの新しいオフィスに行きたいが，場所を忘れてしまった．
ただし，新しいオフィスの場所の候補は $N$ 個あり，座標 $X_1,X_2,\ldots,X_N$ のどこかであることがわかっている．
もし，会社には今座標 $0$ にいることがわかっており，オフィスの場所の座標が $x$ であれば，時間 $|x|$ 以内にはオフィスに着くはずだと思われている．
ニワンゴ君は一定の速度で走って，どの場所がオフィスであったとしても，時間 $|x|$ 以内にオフィスにたどり着けるようにしたい．
走る速度の最小値を求める問題．
オフィスがその位置にあるかどうかは，その位置にたどり着いた瞬間にわかる．

解法

答えに対して二分探索する．
速度 $z$ で走った場合，目的を達成できるかどうかを動的計画法で調べる．
動的計画法においては，状態を（辿り着いたオフィス候補のうちの左端のもの，辿り着いたオフィス候補の右端のもの，右端と左端のうち今どっちにいるか）というのを状態として，そのような状態を達成できる最小の時間を計算していく．
状態遷移は，辿り着いていないオフィス候補のうち，左右直近のどちらかのオフィス候補に移動することを考えれば良い．
その際，位置 $x$ にあるオフィスに対して，時間 $|x|$ 以下で辿りつけないような状態遷移は許さないようにして計算し，全てのオフィスに辿り着けるなら目的は達成できる．
答えの最大値÷要求精度を $e$ とすると，時間計算量は $O(N^2 \log e)$ 程度（$\log e$ が二分探索の回数，$N^2$ は動的計画法の計算量）．
答えの最大値はそんなに大きくならないことは試せばわかり，解説によると $9$ 以下となることが実際に示せるらしい．

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
#define ull unsigned ll

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 writer(double x, char c){printf("%.15f",x);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

template<class S, class T> inline void chmin(S &a, T b){if(a>b)a=b;}

int N, X[1200], o; double ABX[1200], lim[1200];
double dp[2][1100], nxx[2][1100];

double solve(double z){
  int i, j, k, l;
  double nx, r;

  rep(k,2) rep(i,N) dp[k][i] = 1e18;
  rep(i,N) lim[i] = z * ABX[i];
  lim[o] = 1;

  dp[0][o] = dp[1][o] = 0;
  rep(l,N){
    rep(i,N-l-1) nxx[0][i] = nxx[1][i] = 1e18;
    
    rep(i,N-l){
      j = i + l;
      if(dp[0][i] < lim[j]){
        if(j+1 <  N) chmin(nxx[0][i], dp[0][i] + (X[j+1] - X[j]));
        if(i-1 >= 0) chmin(nxx[1][i-1], dp[0][i] + (X[j] - X[i-1]));
      }
      if(dp[1][i] < lim[i]){
        if(j+1 <  N) chmin(nxx[0][i], dp[1][i] + (X[j+1] - X[i]));
        if(i-1 >= 0) chmin(nxx[1][i-1], dp[1][i] + (X[i] - X[i-1]));
      }
    }

    rep(i,N-l-1) dp[0][i] = nxx[0][i], dp[1][i] = nxx[1][i];
  }

  if(dp[0][0] < lim[N-1] || dp[1][0] < lim[0]) return 1;
  return 0;
}

int main(){
  int i, k;
  double x, y, z;

  reader(&N);
  rep(i,N) reader(X+i);

  X[N++] = 0;
  sort(X, X+N);

  rep(i,N) if(X[i]==0) o = i;
  rep(i,N) ABX[i] = max(X[i], -X[i]);

  x = 1;
  y = 9;
  while(y > x*(1+2e-9)){
    z = (x+y) / 2;
    k = solve(z);
    if(k) y = z; else x = z;
  }

  writerLn( (x+y)/2 );

  return 0;
}

Current time: 2024年04月26日04時55分37秒
Last modified: 2016年02月15日07時00分03秒 (by laycrs)
Tags: Competitive_Programming AtCoder dwango2016-finals
トップページに戻る

Logged in as: unknown user (not login)

ログイン：