AOJ0536 Shuffle

問題リンク Shuffle

• 解法

数字が連続しているカードをまとめて区間としてシャッフル毎に区間を管理するのが方針です。
最終的に意味のあるカードの山はp〜q番目の部分だけなので、この部分のみを区間の初期値とし、シャッフルを逆に辿るようにしていきます。
あるシャッフル(x, y)が行われたとき、まず次のような3つの区間に分別できます。
区間1: [1, N-y]
区間2: [N-y+1, N-x]
区間3: [N-x+1, N]
これらの区間内にあるカードは、カードの位置に
区間1: y
区間2: x+y-N
区間3: x-N
を足した場所へ移動します。複数の区間にまたがる区間があった場合は分割して処理します。
最終的に[1〜r]に所属しているカードの枚数を数えて答えとします。
が、この解法だと通りません。TLEが発生するので工夫していきます。
まず、カードの区間は1つのlongの値とします。区間を表す2つの整数L, Rはどちらもint型で表せるので
x = L<<32 | R
とすれば1つのlong値で表せます。取りだしには下位32bitが1であるようなmaskを用意して、
L = x >> 32
R = x&mask
で高速に取り出せます。
区間の集合にはArrayListを使うといいと思います。最初はLinkedListにしていたのですが、こちらはかなり遅いです。Listだと、Collections.sort()が使えるので、区間の左端でソートできるようなComparatorを用意します。
シャッフルによって区間を分割していくと、数が多くなっていますが、中には連続しているような区間があるはずです。2つの区間[s1, t1]と[s2, t2]においてt1+1 == s2だとこれらは連続しているので[s1, t2]という区間にまとめて、区間の数を減らしていきます。
これだけの工夫をすれば通るだろう、と思ったのですがわずかにTLEします。思い付く限りの最適化、チューニングを行います。
Scannerをライブラリの高速なものにする
大きさ5000の配列を2つ最初に取り、データセットごとにnew しない
ArrayListに1500の初期値を渡して内部のメモリ取りなおしの処理を回避する
区間の結合処理は毎度行うのではなく、区間数が1100個以上になったときのみ結合処理をする
これで何とか通りました。

• ソース

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

//Shuffle
public class AOJ0536 {

	class Scanner {
		int nextInt() {
			try {
				int c = System.in.read();
				while (c != '-' && (c < '0' || '9' < c))
					c = System.in.read();
				if (c == '-') return -nextInt();
				int res = 0;
				do {
					res *= 10;
					res += c - '0';
					c = System.in.read();
				} while ('0' <= c && c <= '9');
				return res;
			} catch (Exception e) {
				return -1;
			}
		}
	}

	void run(){
		Scanner sc = new Scanner();
		long mask = (1L << 32)-1;
		Comparator<Long> C = new Comparator<Long>() {
			public int compare(Long o1, Long o2) {
				return (int) ((o1>>32)-(o2>>32));
			}
		};
		int[] p = new int[5000], q = new int[5000];
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			int m = sc.nextInt(), P = sc.nextInt(), Q = sc.nextInt(), R = sc.nextInt();
			List<Long> l = new ArrayList<Long>();
			//int(32bit)を2つ並べて1つのlong(64bit)とする、2つの値は区間の左端、右端
			l.add(((long)P<<32)|Q);
			for(int i=0;i<m;i++){
				p[i] = sc.nextInt(); q[i] = sc.nextInt();
			}
			for(int i=m-1;i>=0;i--){
				long t1 = n-q[i], s2 = t1+1, t2 = n-p[i], s3 = n-p[i]+1, y = q[i];
				List<Long> next = new ArrayList<Long>(1500);
				for(int j=0;j<l.size();j++){
					long x = l.get(j);
					long s = x>>32, t = x&mask;
					if(t<=t1){
						next.add((s+y)<<32 | (t+y));
					}
					else if(t<=t2){
						if(s<=t1){
							next.add((s+y)<<32 | (t1+y));
							s = s2;
						}
						next.add((s-s2+p[i]+1)<<32 | (t-s2+p[i]+1));
					}
					else{
						if(s<=t1){
							next.add((s+y)<<32 | (t1+y));
							s = s2;
						}
						if(s<=t2){
							next.add((s-s2+p[i]+1)<<32 | (t2-s2+p[i]+1));
							s = s3;
						}
						next.add((s-s3+1)<<32 | (t-s3+1));
					}
				}
				//区間数が多くなってきたら隣り合っている区間の結合処理
				//あと最後は必ず行う
				if(i==0||1100<=next.size()){
					l = new ArrayList<Long>();
					Collections.sort(next, C);
					long ss = next.get(0)>>32, tt = next.get(0)&mask;
					for(int j=1;j<next.size();j++){
						long x = next.get(j);
						long s = x>>32, t = x&mask;
						if(tt+1==s)tt = t;
						else{
							l.add((ss<<32)|tt);
							ss = s; tt = t;
						}
					}
					l.add((ss<<32)|tt);
				}
				else{
					l = next;
				}
			}
			int res = 0;
			for(long x:l){
				long s = x>>32, t = x&mask;
				if(R<s)break;
				if(R<t)t = R;
				res+=t-s+1;
			}
			System.out.println(res);
		}
	}

	public static void main(String[] args) {
		new AOJ0536().run();
	}
}