TopCoder SRM618 DIV1 HARD - MovingRooksDiv1

Source

TopCoder SRM618 DIV1 HARD (950pt)
Problem Statement

問題概要

サイズ $N \times N$ のチェスボードに，ルーク（飛車と同じ動き方）が $N$ 駒，互いに攻撃できない位置にある盤面が $2$ つ与えられる．
形式は，各行 $k$ について $R_k$ が与えられ，$k$ 行 $R_k$ 列にルークがいるという形の配列 $R_0,R_1,\ldots,R_{N-1}$ で与えられる．
$1$ つの目の盤面において，あるルークと，その右上にいるルークとを入れ替えることができる．
その操作を繰り返して，$2$ つ目の盤面と一致させたい．
一致させるような操作の列を $1$ つ求める問題．（最小手数である必要はない）
（出力の関係で，1250手以上かかるものを出力する場合は，最初の1250手のみを出力する）
不可能であればそれを指摘する．

解法

問題を言い換えると，$0,1,\ldots,N-1$ の置換が $2$ つ $A, B$ 与えられる．
$A$ のある要素と，その後ろにあるもっと小さい要素と入れ替えることができるので，$A$ を $B$ に変換せよ，ということである．
最初に，大きい要素の場所から一致させていくことを考える．（以下，要素 $k$ を動かすとする）
この際，右にしか移動できないので，$k$ がある場所が $B$ の方が左であれば不可能．
右に動かす方法として，間にある $k$ より小さいもののうち，最も大きいものとスワップするというのを繰り返していくのが最適．
何故なら，別のものを選んで動かすのは，後で大きい物は右に動かすことで実現できるから．
毎回，間にある最も大きいものを探すと $O(N^3)$ になるので，間にあるものをソートしておいて $k$ を動かし終わるまでソートされたものをなぞるなどすると $O(N^2 \log N)$ になる．
（最初に，各要素 $k$ がどこにあるかを求めておいて，$k$ を動かすとき，$k-1,k-2,\ldots$ と見ていって，それらが動かしたい区間の間にあるとスワップなどとすれば $O(N^2)$ でできる）

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

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

class MovingRooksDiv1 {
public:
vector <int> move(vector<int> A, vector<int> B) {
  int i, j, k, m, n = A.size();
  int ap, bp, now;
  pair<int,int> p[3000]; int sz;
  vector<int> res;

  for(m=n-1;m>=0;m--){
    rep(ap,n) if(A[ap]==m) break;
    rep(bp,n) if(B[bp]==m) break;
    if(ap > bp){
      res.clear();
      res.push_back(-1);
      break;
    }

    sz = 0;
    REP(i,ap+1,bp+1) if(A[i] < m) p[sz++] = make_pair(A[i],i);
    sort(p, p+sz);

    now = ap;
    for(i=sz-1;i>=0;i--){
      j = p[i].first;
      k = p[i].second;
      if(k < now) continue;
      
      if(res.size() < 2500){
        res.push_back(now);
        res.push_back(k);
      }
      swap(A[now], A[k]);
      now = k;
      if(now == bp) break;
    }
    if(now != bp){
      res.clear();
      res.push_back(-1);
      break;
    }
  }

  return res;
}

}

Current time: 2024年04月16日17時39分39秒
Last modified: 2014年04月26日06時38分41秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM618 SRM_Div1_Hard
トップページに戻る

Logged in as: unknown user (not login)

ログイン：