TopCoder SRM613 DIV1 EASY/DIV2 MEDIUM - TaroFriends

Source

TopCoder SRM613 DIV1 EASY (250pt)
TopCoder SRM613 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

一次元の直線上に猫が $N$ 匹いて,それぞれの猫 $i$ の座標 $C_i$ が与えられる.複数の猫は同じ場所にいる可能性もある.
全ての猫は,左右のどちらかにちょうど $X$ だけ移動する.
移動した後の最も離れている猫の距離の最小値を求める問題.

解法

最も離れている猫の距離を短くするには,ある猫が右に移動したとした時,最初にそれより左にいた猫が左に移動するのは無意味.
よって,右から何匹かを左へ,残りを右へ移動するというパターンを全て試せば良い(全部同じ方向に行くのも忘れないようにする).
猫は,位置でソートしておいて,区切り目を全部探索する.
以下の解答では,最も離れた猫の距離は愚直にシミュレーションした後,猫の座標でソートして求めた.$O(N^2 \log N)$.
最も離れた猫の距離を調べるには,(右|左)に移動した猫のうち最も(右|左)の猫の4匹の猫にのみ着目すれば良いので,そうすると $O(N \log N)$ でも解ける.

C++によるスパゲッティなソースコード

// #includeなどは略しています
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define INF 1000000000

class TaroFriends {
public:
int getNumber(vector <int> in, int X) {
  int i, j, k, n;
  int res = INF;

  n = in.size();
  sort(in.begin(), in.end());

  rep(k,n){
    vector<int> tmp = in;
    rep(i,k) tmp[i] += X;
    REP(i,k,n) tmp[i] -= X;
    sort(tmp.begin(), tmp.end());
    res = min(res, tmp[n-1]-tmp[0]);
  }

  return res;
}

}

Current time: 2017年07月24日15時49分15秒
Last modified: 2014年03月24日13時20分29秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM613 SRM_Div1_Easy SRM_Div2_Medium Brute_Force Greedy
トップページに戻る

Logged in as: unknown user (not login)

ログイン: