Hanafuda Shuffle(PKJ No.1978)

n枚のカードが与えられて、下から1,2,...,nの番号が振られている。
$r, p_i, c_i (1\leq i \leq r)$ が与えられて、
上の $p_i -1$ 枚とその下の $c$ 枚を入れ替えるカットという操作をr回繰り返した後の一番上のカードの数字を求める。
制約
$1 \leq n,r \leq 50$
$p+c \leq n-1$

アルゴリズム

ただシミュレートするだけ。
アレイでデッキを表現して、1要素ずつサブアレイを取り出して交換するときは、コピーする順番を気を付ける。
STLとかを使えばサブリスト?を簡単に付け加えたり、削除したりできる。

コード

begin()のところがちょいと見にくい

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

int main(){
	int n, r, p, c;
	while( cin >> n >> r ){
		if( !n && !r ) break;
		vector<int> deck(n);
		for(int i=0; i<n; ++i) deck[i] = n-i;
		while( r-- ){
			cin >> p >> c;
			deck.insert(deck.begin(), deck.begin()+p-1, deck.begin()+p-1 + c);
			deck.erase(deck.begin()+c+p-1, deck.begin()+c+p-1 + c);
		}
		cout << deck.front() << endl;
	}

	return 0;
}

javaでは、indexで指定できるのでカット操作の部分は多少すっきりしている。
C++に慣れてると、subList()で返されるリストの変更が元のリストに反映されるのが非常に気持ち悪い。

import java.util.*;
public class pku1978 {
	static Scanner stdin;
	public static void main(String[] args) {
		stdin = new Scanner(System.in);
		new pku1978();
	}
	pku1978(){
		while(true){
			int n = stdin.nextInt();
			int r = stdin.nextInt();
			if( n == 0 && r == 0 ) break;
			
			LinkedList<Integer> deck = new LinkedList<Integer>();
			for(int i=0; i<n; ++i) deck.add(n-i);

			while(r-- != 0){
				int p = stdin.nextInt();
				int c = stdin.nextInt();
				deck.addAll(0, deck.subList(p-1, p-1+c));
				deck.subList(c+p-1, c+p-1+c).clear();
			}	
			System.out.println(deck.getFirst());
		}
	}
}