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; }