TopCoderOpen Algorithm 2014 Round 2A MEDIUM - NarrowPassage

Source

TopCoderOpen Algorithm 2014 Round 2A MEDIUM (500pt)
Problem Statement

問題概要

細長い長さ $L$ の通路の中に $N$ 人の人がいる.
座標として,通路の両端を $0$ と $L$ とする.
各人 $k$ の最初にいる場所 $A_k$ と,その人が行きたい場所 $B_k$ が与えられる.
通路内ではすれ違うことはできないが,通路の端(座標 $0$ か $L$)に行けば,その場で順番を自由に入れ替えることができる.
全員が目的地に辿り着くまでの最小の総移動距離を求める問題.

解法

全てのパターンを試して,最小を取れば良い.
あり得るパターンは以下の通り.

  1. $1$ 人以上の人が左右の端に退避しない場合.
    退避しない人は最初に位置が連続していなければならず,退避しなかった人が移動したい場所は初期値の順番と一致してなければいけない.
    また,退避しない人の塊より,左の人は,退避しない人グループのどの目的地よりも左でなければいけないし,右も同様.
    よって,退避しないグループのパターン数は $O(N^2)$ しかないので全部試す.
    退避しない人は $|B_k-A_k|$ だけ動けば良いし,左に退避する人は $A_k+B_k$ だけ動くし,右に退避する人は $(L-A_k)+(L-B_k)$ だけ動く.
  2. 全員が左右の端に退避する場合.
    最初に左に退避する人は,右に退避する人より左にいなければいけないので,全員を退避する場合,どこで分けて左右に振り分けるかを $N+1$ 通り試す.
    また,退避した後に,左端から右端に移動,右端から左端に移動することがある.
    この時,左端から右端に移動するのは,左端に退避した人の中で,目的地が右の方にある人であるので,左右からそれぞれ何人移動するかを決めれば,誰が移動するかは判定することができる.
    よって,左右から何人が移動するかを $O(N^2)$ パターンを試す.
    ここで,移動した後,左端にいる人で最も右に行きたい人と,右端にいる人で最も左に行きたい人が交差しないならば最終状態に移動可能.

一度,右端に行って,左端に行って,右端に戻るなどは無駄なので,考えなくて良い.
全てのパターン数は $O(N^3)$ で愚直に計算しても $O(N^4)$ 程度の時間計算量となる.
上のパターン2.をもっとうまく処理すれば(例えば,退避した後,左右に何人移動するかを片方だけ決めればもう片方は最終状態に移動できるように何人端から端に移動すれば良いかわかる)オーダーを落とすこともできる.

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 INF 1050000000

void intIntSort(int d[],int m[],int s){int i=-1,j=s,k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;t=m[i];m[i]=m[j];m[j]=t;}intIntSort(d,m,i);intIntSort(d+j+1,m+j+1,s-j-1);}

class NarrowPassage {
public:
int minDist(int L, vector <int> a, vector <int> b) {
  int i, j, k, N = a.size();
  int A[100], B[100];
  int x, y, y1, y2, dame;
  int left[100], right[100], ls, rs;
  int nleft[100], nright[100], nls, nrs;
  int mn, mx;
  int res = INF, tmp, add;

  rep(i,N) A[i] = a[i], B[i] = b[i];
  intIntSort(A,B,N);

  tmp = 0;
  rep(i,N) tmp += A[i] + B[i];
  res = min(res, tmp);

  tmp = 0;
  rep(i,N) tmp += (L-A[i]) + (L-B[i]);
  res = min(res, tmp);

  rep(x,N) REP(y,x,N){
    dame = 0;
    REP(i,x+1,y+1) if(B[i-1] > B[i]){ dame=1; break; }
    rep(i,x) if(B[i] > B[x]){ dame = 1; break; }
    REP(i,y+1,N) if(B[i] < B[y]){ dame = 1; break; }
    if(dame) continue;

    tmp = 0;
    rep(i,x) tmp += A[i] + B[i];
    REP(i,x,y+1) tmp += abs(A[i]-B[i]);
    REP(i,y+1,N) tmp += (L-A[i]) + (L-B[i]);
    res = min(res, tmp);
  }

  rep(x,N){
    tmp = 0;
    rep(i,x) tmp += A[i];
    REP(i,x,N) tmp += L - A[i];

    ls = rs = 0;
    rep(i,x) left[ls++] = B[i];
    REP(i,x,N) right[rs++] = B[i];
    sort(left, left+ls);
    sort(right, right+rs);

    rep(y1,ls+1) rep(y2,rs+1){
      nls = nrs = 0;
      rep(i,ls-y1) nleft[nls++] = left[i];
      REP(i,ls-y1,ls) nright[nrs++] = left[i];
      rep(i,rs-y2) nright[nrs++] = right[rs-1-i];
      REP(i,rs-y2,rs) nleft[nls++] = right[rs-1-i];

      if(nls && nrs){
        mx = nleft[0];
        REP(i,1,nls) mx = max(mx, nleft[i]);
        mn = nright[0];
        REP(i,1,nrs) mn = min(mn, nright[i]);
        if(mx > mn) continue;
      }
      
      add = L * (y1 + y2);
      rep(i,nls) add += nleft[i];
      rep(i,nrs) add += L - nright[i];
      res = min(res, tmp + add);
    }
  }

  return res;
}

}

Current time: 2017年09月26日02時07分14秒
Last modified: 2014年05月18日19時17分26秒 (by laycrs)
Tags: Competitive_Programming TopCoder TopCoderOpen TCO_Algorithm TCO_Algorithm_2014 TCO_Algorithm_2014_2A
トップページに戻る

Logged in as: unknown user (not login)

ログイン: