ITP2-1 Dynamic Arrays and List

A : Vector

問題（外部リンク）

Vector | Aizu Online Judge

実装の概要

java.util.VectorでACすることが可能です。このVectorにはremoveLast()がないのでremove(vec.size() - 1)とすることで末尾を指定することができます。速度が気になるところですが制限時間には間に合います。
ArrayListなど他のCollectionクラスを使うと間に合わないので気をつけてください。

public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int q = Integer.parseInt(br.readLine());

        Vector<Integer> vec = new Vector<Integer>();
        for(int i = 0; i < q; i++){
            String[] tmpArray = br.readLine().split(" ");
 
            if(tmpArray[0].equals("0")){
                vec.add(Integer.parseInt(tmpArray[1]));
            }
            else if(tmpArray[0].equals("1")){
                System.out.println(vec.get(Integer.parseInt(tmpArray[1])));
            }
            else {
                vec.remove(vec.size() - 1);
            }
        }
    }
}

B : Deque

問題（外部リンク）

Deque | Aizu Online Judge

実装の概要

JavaにもDequeインターフェースを実装したサブクラスは存在しますが、C++のそれとは異なりランダムアクセスをサポートしていません。Iteratorも前進することしかできないためどうしてもそこがボトルネックになってしまいます。
そのため今回の問題ではDequeを自力で実装します。概要としては「巨大な配列をあらかじめ用意する」「中心から始めて、適宜前と後ろに伸ばしていく」というものです。
これによりpush, randomAccess, popをそれぞれO(1)でできるようになり速度が大幅に上昇します。
ただし、ACはできますが「メモリの使用量が最大クエリ数に依存する」「エラー処理が全く無い」など色々と問題のある実装なので、実用化のためには改良が必要です。

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


		int q = Integer.parseInt(br.readLine());

		MyDeque deque = new MyDeque(400000);
		for(int i = 0; i < q; i++){
			String[] tmpArray = br.readLine().split(" ");

			if(tmpArray[0].equals("0")){
				if(tmpArray[1].equals("0")){
					deque.push(Integer.parseInt(tmpArray[2]));

				}
				else{
					deque.add(Integer.parseInt(tmpArray[2]));
				}
			}
			else if(tmpArray[0].equals("1")){
				System.out.println(deque.get(Integer.parseInt(tmpArray[1])));
			}
			else {
				if(tmpArray[1].equals("0")){
					deque.removeFirst();
				}
				else {
					deque.removeLast();
				}
			}

		}
    }
}

class MyDeque {
	//firstは先頭、lastは末尾の要素の直後を指す
	private int first, last;
	private int[] data;

	//先頭追加および末尾追加の上限をlimitに設定してDequeを生成
	MyDeque(int limit){
		data = new int [limit * 2 + 1];
		first = limit;
		last = limit;
	}

	void push(int x){
		data[--first] = x;
	}

	void add(int x){
		data[last++] = x;
	}

	int get(int index){
		return data[first + index];
	}

	int removeFirst(){
		int result = data[first++];
		return result;
	}

	int removeLast(){
		last--;

		return data[last];
	}
}

C : List

問題（外部リンク）

List | Aizu Online Judge

実装の概要

Java.util.*にはいくつかの種類のリストがありますが、途中の要素の削除が多い場合はArrayListよりもLinkedListの方が高速に動作します。
要素へのアクセスにはListIteratorを使います。通常のIteratorには前に戻るためのメソッドがないためです。
なお、ListIteratorのメソッドが指し示す要素の場所ですが、そのままだと問題の要求を満たすことができないため適宜前後に移動させます。

public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        //途中削除が多いのでLinkedListが適している
        LinkedList<Integer> list = new LinkedList<Integer>();
        ListIterator<Integer> it = list.listIterator();
        for(int i = 0; i < n; i++){
        	String[] tmpArray = br.readLine().split(" ");
        	
        	//insert
        	if(tmpArray[0].equals("0")){
        		it.add(Integer.parseInt(tmpArray[1]));
        		//add後にカーソルを前に戻す必要がある
        		it.previous();
        	}
        	//move
        	else if(tmpArray[0].equals("1")){
        		int x = Integer.parseInt(tmpArray[1]);
        		
        		if(x > 0){
        			for(int j = 0; j < x; j++){
        				it.next();
        			}
        		}
        		else {
        			for(int j = 0; j < -x; j++){
        				it.previous();
        			}
        		}
        	}
        	//remove
        	else {
        		//remove前にnextを1回実行する必要がある
        		it.next();
        		it.remove();
        	}
        }
        
        printList(list);
    }
    
    static void printList(List list){
    	Iterator it = list.listIterator(0);
        
        while(it.hasNext()){
        	System.out.println(it.next());
        }
    }
    
}

D : Vector II

問題（外部リンク）

Vector II | Aizu Online Judge

実装の概要

こちらは素直にVectorの配列を作ることでACできます（宣言の仕方には注意が必要です）。
この実装ではdumpでIteratorを使った上で一旦StringBufferに入れてからまとめて出力を行いました。各要素ごとにSystem.out.print()をしていると間に合わない可能性があります（試してはいません）

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmpArray = br.readLine().split(" ");
		int n = Integer.parseInt(tmpArray[0]);
		int q = Integer.parseInt(tmpArray[1]);

		@SuppressWarnings("unchecked")
		Vector<Integer>[] vecArray = new Vector[n];
		for(int i = 0; i < n; i++){
			vecArray[i] = new Vector<Integer>();
		}

		for(int i = 0; i < q; i++){
			tmpArray = br.readLine().split(" ");

			//pushBack
			if(tmpArray[0].equals("0")){
				int t = Integer.parseInt(tmpArray[1]);
				int x = Integer.parseInt(tmpArray[2]);

				vecArray[t].add(x);
			}
			//dump
			else if(tmpArray[0].equals("1")){
				int t = Integer.parseInt(tmpArray[1]);

				printVec(vecArray[t]);
			}
			//clear
			else {
				int t = Integer.parseInt(tmpArray[1]);

				vecArray[t] = new Vector<Integer>();
			}
		}

	}
	
	static void printVec(Vector vec){
		Iterator it = vec.iterator();

		StringBuffer sb = new StringBuffer();
		while(it.hasNext()){
			sb.append(it.next());

			if(it.hasNext()){
				sb.append(" ");
			}
		}
		System.out.println(sb);
	}
}