AOJ 0299 : Railroad II

問題リンク : Railroad II | Aizu Online Judge

問題概要 :
略

解法 :
累積和

駅は円状になっているが切り離して直線にし、同じものをもう一つくっつける
例えば 7駅あって0と2と6に訪れる必要があるなら、切り離してもう一つ繋げて
0 2 6 0 2 6 とする
それに対して駅と駅の間の距離の累積和を求める
先ほどの例なら
0 2 6 7 9 13 となる
スタートの駅は決まっているのでゴールの駅をループで決めてしまう
ゴールの駅を一番最後に訪れてそれ以外の買い物をする駅を全て訪れるので、
移動経路は２種類しかない
それはスタートからゴールの右隣の駅に行きそこで折り返してゴールまで向かう方法と
スタートからゴールの左隣の駅に行きそこから折り返してゴールまで向かう方法である
累積和で各駅間の移動コストはO(1)でもとまるのでO(m)で答えを求めることができる

あ、それとスタートの駅をmに混ぜておく必要があるかも ( 実装次第かもめ

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define printF printf

using namespace std;

const int IINF = INT_MAX;
const int MAX_M = 10010;
int n,m,p,d[MAX_M],sum[MAX_M*3],sp;

void fix(){
  vector<int> arr;
  rep(i,m) arr.push_back(d[i]); 
  arr.push_back(p);
  sort(arr.begin(),arr.end());
  arr.erase(unique(arr.begin(),arr.end()),arr.end());
  m = arr.size();
  rep(i,m) d[i] = arr[i];
}

void ridiculous_initer(){
  sum[0] = 0;
  REP(i,1,m) sum[i] = sum[i-1] + abs(d[i]-d[(i-1+m)%m]);
  sum[m] = sum[m-1] + abs( n - d[m-1] ) + d[0];
  REP(i,1,m) sum[m+i] = sum[m+i-1] + abs(d[i]-d[(i-1+m)%m]);
  sum[2*m] = sum[2*m-1] + abs( n - d[m-1] ) + d[0];
  REP(i,1,m) sum[2*m+i] = sum[2*m+i-1] + abs(d[i]-d[(i-1+m)%m]);
}

int getCost(int ep){
  int mini = IINF;
  int eXsp = sp + m, eXep = ep + m;
  if( ep < sp ) { ep = eXep; eXep = ep + m; }
  int cost1,cost2;
  // left side
  cost1 = sum[eXsp] - sum[ep+1];
  cost2 = sum[eXep] - sum[eXsp];
  mini = min(mini,cost1*2+cost2);
  // right side
  cost1 = sum[eXep-1] - sum[eXsp];
  cost2 = sum[eXsp] - sum[ep];
  mini = min(mini,cost1*2+cost2);
  
  return mini;
}

void compute(){
  int eXsp = sp + m;
  int mini = IINF;
  rep(ep,m) if( ep != sp ) mini = min(mini,getCost(ep));
  if( mini == IINF ) mini = 0;
  printF("%d\n",mini*100);
}

int main(){
  scanf("%d %d %d",&n,&m,&p);
  rep(i,m) scanf("%d",d+i);

  fix();
  sp = -1;
  rep(i,m) if( d[i] == p ) { sp = i; break; }
  assert( sp != -1 );
  
  ridiculous_initer();
  
  compute();

  return 0;
}