Google Code Jam Japan 2011 Qual A: カードシャッフル

問題概要

カードをある手順にしたがってシャッフルして、最後に特定の位置にあるカードを答える問題。

考えたこと

• (今回は時間の余裕もあるしD言語を試すことにした)
• これはよくある問題。終了状態から逆にシミュレーションして最初どこにあったのかを答えれば良い。
• これでlargeとsmallの両方書いてもいいんだけどそれだと練習にならないのでsmallは愚直にシミュレーションで書く。
• 配列のスライス書きやすくていい感じだ。

通ったコード

small

import std.stdio;

int nextInt(){
	int x;
	scanf("%d",&x);
	return x;
}

int solve(){
	int M = nextInt, C = nextInt, W = nextInt;

	int[] cards = new int[M];
	foreach(int i, ref x ; cards){
		x = i + 1;
	}

	for(auto i=0; i<C; i++){
		auto A = nextInt - 1, B = nextInt;
		cards = cards[A..A+B] ~ cards[0..A] ~ cards[A+B..$];
	}

	return cards[W-1];
}

void main(){
	for(auto c = 1, T = nextInt; c <= T; c++){
		writef("Case #%d: %d\n", c, solve());
	}
}

large

import std.stdio;

int nextInt(){
	int x;
	scanf("%d",&x);
	return x;
}

int solve(){
	int M = nextInt, C = nextInt, W = nextInt;
	int r = W;

	//処理を記憶
	int[] As, Bs;
	for(int i=0; i<C; i++){
		As ~= nextInt;
		Bs ~= nextInt;
	}

	//終了状態から初期状態へのシミュレーション
	for(auto i=C-1; i>=0; i--){
		auto A = As[i], B = Bs[i];
		if( r <= B ){
			r += A - 1;
		}
		else if( r < A + B ){
			r -= B;
		}
	}

	return r;
}

void main(){
	for(auto c = 1, T = nextInt; c <= T; c++){
		writef("Case #%d: %d\n", c, solve());
	}
}