GCJに向けて本気で問題を解説してみる 第1回 (Hanafuda Shuffle)
どうもtatsyです。
GCJのQualification Roundが2週間後に迫ったということで、
http://www.deqnotes.net/acmicpc/
のページに書かれているACM/ICPC国内予選突破の手引きにある問題を僕なりの全力で解説してみたいと思います。
第1回の今回は「Hanafuda Shuffle」という問題です。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1129
この問題は特定枚数与えられている数字が書かれたカードをシャッフルしたときに一番上のカードが何かを出力するプログラムを書く、という問題です。この問題の簡単なところは、入力されるカードの枚数が高々50枚であるというところです。
すなわち50枚であればカードのデータをすべて持っておいて、シャッフルの操作をそのままシミュレーションするだけで答えを導き出すことができるからです。
ですが、この問題、実はカードの枚数が10000枚だろうが2^31-1枚だろうが解くことができます。というのも、この問題で答えなくてはならないのは「一番上のカード」だけだからです。つまり最終状態において一番上にあるカードをシャッフルの逆シミュレーションをしながら追いかけていけば、最終状態において1番上にあったカードがシャッフルの過程において何番目にあるのかを保存しておくだけで解くことができてしまうのです。
なので、多倍長整数とかを使うことを考えなければ一応2^64-1枚までだったらカードのデッキが増えても大丈夫です。
答えのコードは以下のようになります。
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <string>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define repa(i,s,e) for(int i=s; i<=e; i++)
#define repd(i,s,e) for(int i=s; i>=e; i--)
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
int n, r;
struct opt {
int p, c;
};
vector<opt> V;
int main() {
while(cin >> n >> r, n | r) {
V.clear();
rep(i, r) {
opt o;
cin >> o.p >> o.c;
V.push_back(o);
}
int a = 1;
repd(i,V.size()-1,0) {
if(a <= V[i].c) {
a += V[i].p-1;
} else {
if(a - V[i].c <= V[i].p - 1) {
a = a - V[i].c;
}
}
}
printf("%d\n", n-a+1);
}
}