AOJ : 0536 - シャッフル (Shuffle)

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0536&lang=jp
日本語の問題文なので説明は省略

アルゴリズム

カードを1枚1枚, 1次元配列に展開する方法だと, メモリ的にも計算時間的にもとても無理なので, データ構造を工夫します.
カードの数字が連続で並んでいるところは, 1つのクラスで置き換えてしまって, 情報量を圧縮してしまえば, メモリ使用量も計算時間も少なくて済みます.

例えば,
[1, 2, 3, 4, 5, 6, 7, 8, 9]
という山の情報は,
[1, 9]
というように, 連続する数字の最初と最後を記憶しておくだけで, 山を管理できたことになります.

この山に対して, shuffle(3,5) を行った場合は,
[1, 3] [4, 5] [7, 9]
のように3つに分割されて, シャッフル後の山は,
[ [7, 9], [4, 5], [1, 3] ]
となります.

この方法で解く場合, シャッフルの作業書くのが面倒ですが, がんばってください.

プログラム

#include <iostream>
#include <deque>
using namespace std;

class Card{
public:
  int f,t;

  Card(int from,int to){
    f = from;
    t = to;
  }
};

int n,m,p,q,r;
deque<Card> d; //カードの山

//山の1枚目からx枚目までを取り出して戻り値として返す
deque<Card> removeCard(int x){
  deque<Card> res;

  while(1){
    Card tmp = d.front(); d.pop_front();
    x -= tmp.t - tmp.f + 1;

    if(x <= 0){
      if(x != 0){
        d.push_front(Card(tmp.t + x + 1, tmp.t));
        tmp.t += x;
      }
      res.push_back(tmp);
      break;
    }
    res.push_back(tmp);
  }
  return res;
}

//シャッフル用関数
void shuffle(int x,int y){
  deque<Card> A = removeCard(x);
  deque<Card> B = removeCard(y-x);
  for(int i=0;i<B.size();i++) d.push_back(B[i]);
  for(int i=0;i<A.size();i++) d.push_back(A[i]);
}

int main(void){
  while(cin>>n,n){
    cin>>m>>p>>q>>r;
    d.clear();
    d.push_back(Card(1,n));

    while(m--){
      int x,y;
      cin>>x>>y;
      shuffle(x,y);
    }

    int ans = 0;
    removeCard(p-1); //上の(p-1)枚を取り出しておく
    deque<Card> rem = removeCard(q-p+1); //(p-q+1)枚取り出せば, p枚目からq枚目を取り出したことになる
    for(int i=0;i<rem.size();i++){
      if(rem[i].f <= r){
        ans += r - rem[i].f - (rem[i].t < r ? r-rem[i].t : 0) + 1;
      }
    }
    cout<<ans<<endl;
  }

  return 0;
}