AOJ 0536 : Shuffle
問題リンク:Shuffle | Aizu Online Judge
問題概要:
1順にnまでの数字がかかれたカードの山がある
このカードをシャッフル(x,y)したとき山の上からp枚めとq枚めの間にカードの数字がr以下のものが何枚存在するか?
使用した言語:C++
解法:
nが10の9乗と大きいのでカードがシャッフル自体は5000回しかないので、カードを区間にわけてvectorにつめこみシャッフルしていった
区間を表すための構造体としてstructでPというものをつくった
Pはintのs,eという要素をもちsは区間の始まり、eは区間の終わりを表す(s,e自体も区間に含まれる)
シャッフル(X,Y)自体はPを要素とするvectorの今みている要素が区間(X,Y)とどのような関係があるのかを考えてがんばった
全部説明するとすごく大変なので
詳しくはコードを見てほしいです
シャッフル後のカウントはvectorの各要素に対してどの程度含まれているのかを加えていけば良い
ちなみにカウントも4通り場合わけしていたせいでWAだしまくった
シャッフルが悪いのか、カウントが悪いのか、どっちもわるいのか全然わからなかったので公式サイトからジャッジデータもらってきてテストしたところカウントがまずいことになっていることがわかった
そもそも4通りに場合わけする必要がないことにも気がつき、そしてそこを修正したらACでした
こういった実装が面倒系の問題がコンテストで出たらとても解ける気がしない・・・
それでも正確にかけるorジャッジデータなしでもミスに気がつける力が欲しい!!!と思いました
コード:
#include<iostream> #include<vector> #include<algorithm> #include<cassert> #include<cstdio> using namespace std; struct P { int s,e; P(int s,int e):s(s),e(e){} }; void shuffle(vector<P>& vec,int x,int y,int n) { vector<P> ins; for(int i=0;i<vec.size();i++) { if(vec[i].e <= x) { vec[i].s += (n-x),vec[i].e += (n-x); } else if(vec[i].s <= x && vec[i].e <= y) { ins.push_back(P(x+1,vec[i].e)); ins[ins.size()-1].s += (n-y)-x,ins[ins.size()-1].e += (n-y)-x; vec[i].e = x; vec[i].s += (n-x),vec[i].e += (n-x); } else if(vec[i].s <= x && vec[i].e > y) { ins.push_back(P(vec[i].s,x)); ins[ins.size()-1].s += (n-x),ins[ins.size()-1].e += (n-x); ins.push_back(P(x+1,y)); ins[ins.size()-1].s += (n-y)-x,ins[ins.size()-1].e += (n-y)-x; vec[i].s = y+1; vec[i].s -= y,vec[i].e -= y; } else if(vec[i].s > x && vec[i].e <= y) { vec[i].s += (n-y)-x,vec[i].e += (n-y)-x; } else if(vec[i].s > x && vec[i].s <= y && vec[i].e > y) { ins.push_back(P(vec[i].s,y)); ins[ins.size()-1].s += (n-y)-x, ins[ins.size()-1].e += (n-y)-x; vec[i].s = y+1; vec[i].s -= y,vec[i].e -= y; } else if(vec[i].s > y) { vec[i].s -= y,vec[i].e -= y; } else assert(false); } for(int i=0;i<ins.size();i++) vec.push_back(ins[i]); } int main() { int n; while(scanf("%d",&n),n) { int m; scanf("%d",&m); int p,q,r; scanf("%d %d %d",&p,&q,&r); vector<P> vec; vec.push_back(P(1,r)); for(int i=0;i<m;i++) { int x,y; scanf("%d %d",&x,&y); shuffle(vec,x,y,n); } int cnt = 0; for(int i=0;i<vec.size();i++) { if(vec[i].s > q || vec[i].e < p) continue; cnt += min(vec[i].e,q) - max(vec[i].s,p)+1; } cout << cnt << endl; } return 0; }