TopCoderOpen Algorithm 2014 Round 2A MEDIUM (500pt)
Problem Statement
細長い長さ $L$ の通路の中に $N$ 人の人がいる.
座標として,通路の両端を $0$ と $L$ とする.
各人 $k$ の最初にいる場所 $A_k$ と,その人が行きたい場所 $B_k$ が与えられる.
通路内ではすれ違うことはできないが,通路の端(座標 $0$ か $L$)に行けば,その場で順番を自由に入れ替えることができる.
全員が目的地に辿り着くまでの最小の総移動距離を求める問題.
全てのパターンを試して,最小を取れば良い.
あり得るパターンは以下の通り.
一度,右端に行って,左端に行って,右端に戻るなどは無駄なので,考えなくて良い.
全てのパターン数は $O(N^3)$ で愚直に計算しても $O(N^4)$ 程度の時間計算量となる.
上のパターン2.をもっとうまく処理すれば(例えば,退避した後,左右に何人移動するかを片方だけ決めればもう片方は最終状態に移動できるように何人端から端に移動すれば良いかわかる)オーダーを落とすこともできる.
#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: 2024年03月29日16時11分31秒
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)