AOJ PG応用(動的配列とリスト)

ベクトル

整数を保持する可変長配列A={a0,a1,...}に対して、以下の操作を行ってください。

• pushBack(x): Aの末尾に整数xを挿入する

• randomAccess(p):Aの要素apの値を出力する

• popBack(): Aの末尾の要素を削除する
  Aは0-オリジンでインデックスが付けられ、初期状態では空とします。

• input
  入力形式は以下の形で与えられる
  q
  query1
  query2
  :
  queryq
  また、各クエリは
  0 x
  または1 p
  または2
  の形式で与えられます。最初の数字0, 1, 2 は操作の種類を示し、それぞれpushBack、randomAccess、popBackを表します。空の配列に対して、randomAccess や popBack操作が行われることはありません

• output
  各randomAccess操作ごとに、apの値を１行に出力してください

AOJ.java

import java.io.*;
import java.util.ArrayList;
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());

    //可変長配列Ａ
    ArrayList<Integer>A= new ArrayList<Integer>();
    //命令分割
    
        for(int i=0;i<q;i++){
        //String型配列に命令を格納→IntegerParseInt忘れずに！
        String[] arr = br.readLine().split(" ");
        int op = Integer.parseInt(arr[0]);
            switch(op){
                case 0:
                int x = Integer.parseInt(arr[1]);
                A.add(x);
                break;
                
                case 1:
                int p = Integer.parseInt(arr[1]);
                System.out.println(A.get(p));
                break;
                
                case 2:
                A.remove(A.size()-1);
                break;
            }
        }
   
    }
}

• throws IOException は、そのメソッド（例：main）の中で、IOException（入出力例外）が発生する可能性があることを Java に伝えるための宣言
• 「そのエラーが起きたら、呼び出し元（またはOS）に処理を任せるよ！」という意味
• 入力が大きいため、標準入力の高速化を図る→鉄板は以下

ex.java

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int q = Integer.parseInt(br.readLine());

• BufferedReader→ユーザーのキーボード入力（標準入力）を、「文字列」として1行ずつ読み込めるようにする→入力値で演算等行いたい場合はInteger.parseInt
• ArrayListの要素を取り出す→list.get(インデックス) で要素を取得
• Java の ArrayList は、要素に順番がある可変長配列
  →インデックスは 0から始まり、末尾のインデックスは size() - 1
• 今回はArrayListを使ったが似ているLinkedListもおさえておくとGOOD
• LikedList→要素へのインデックスアクセスや要素の途中挿入・削除は遅いが末尾＆先頭操作ならArrayListより得意で速い！
• 要素を ランダムにアクセス（インデックス指定）したい場合はArrayList
• 要素の 追加・削除が頻繁（特に先頭）ならLinkedList

デキュー

整数を保持する可変長配列A={a0,a1,...}に対して、以下の操作を行ってください。

• push(d,x): dが0の場合、Aの先頭に整数xを挿入する。dが1の場合、末尾にxを挿入する
• randomAccess(p):Aの要素apの値を出力する
• pop(): dが0の場合、Aの先頭の要素を削除する。dが1の場合、末尾の要素を削除する
  Aは0-オリジンでインデックスが付けられ、初期状態では空とします
• input
  入力形式は以下の形で与えられる
  q
  query1
  query2
  :
  queryq
  また、各クエリは
  0 d x
  または1 p
  または2 d
  の形式で与えられます。最初の数字0, 1, 2 は操作の種類を示し、それぞれpushBack、randomAccess、popBackを表します。空の配列に対して、randomAccess や popBack操作が行われることはありません
• output
  各randomAccess操作ごとに、apの値を１行に出力してください

AOJ.java

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        // 巨大な配列に対応するため十分なサイズで初期化
        int maxSize = 800000; // 最大操作数の2倍程度
        int[] deque = new int[maxSize];
        int front = 400000; // 中央から始める
        int rear = 400000;  // 空のデックを表す（front == rear）
        
        int q = Integer.parseInt(br.readLine());
        for (int i = 0; i < q; i++) {
            String[] arr = br.readLine().split(" ");
            int op = Integer.parseInt(arr[0]);
            
            switch (op) {
                case 0: // push
                    int d1 = Integer.parseInt(arr[1]);
                    int x = Integer.parseInt(arr[2]);
                    if (d1 == 0) {
                        // 先頭に要素を追加
                        front--;
                        //そこに値xを格納
                        deque[front] = x;
                    } else {
                        // 末尾に追加
                        deque[rear] = x;
                        rear++;
                    }
                    break;
                    
                case 1: // randomAccess
                    int p = Integer.parseInt(arr[1]);
                    sb.append(deque[front + p]).append("\n");
                    break;
                    
                case 2: // pop
                    int d2 = Integer.parseInt(arr[1]);
                    if (d2 == 0) {
                        // 先頭インデックスを1つ進めて、デックの先頭要素を削除
                        front++;
                    } else {
                        // 末尾から削除
                        rear--;
                    }
                    break;
            }
        }
        
        System.out.print(sb);
    }
}

• 配列を使って二重端のデータ構造（デック）を実現している。主に、push、randomAccess、pop の操作を効率的に処理する
• 入力→BufferedReaderで受け取る
• デキューでは、データの先頭（front）と末尾（rear）の両方で、データの追加（push）や削除（pop）ができる
  →データの挿入と削除が両端で行えるため、普通のキューよりも柔軟にデータを処理できる

ex.java

// 先頭にデータを追加
deque[front] = x;
front--; // front を減らして、次に追加する位置を前に移動

// 末尾にデータを追加
deque[rear] = x;
rear++; // rear を増やして、次に追加する位置を後ろに移動

• front はデックの先頭の位置を指すので、front + p は配列内の実際の位置を計算している
• randomAccess() は「出力内容を準備する」だけのメソッドで、実際の「出力」は main メソッドの最後にまとめて行っている
• スコープについて理解が甘かったのでまとめておく

・同じブロックの中で同じ名前の変数は使えない
→一度定義したら、そのブロックの中では再定義できない
・{} ブロックの中で宣言された変数は、そのブロックの中でしか使えない
・ブロックが違えば、同じ名前でも別の変数として使える
→例えばswitch文では

switch (op) {
    case 0: {
        int d = Integer.parseInt(arr[1]);
        // d を使う処理
        break;
    }
    case 2: {
        int d = Integer.parseInt(arr[1]);
        // d を使う処理
        break;
    }
}

このようにcaseごとにブロックでかこめばどちらのケースでもdを定義して使える

別解

AOJ.java

import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main{
	public static void main(String[] args) {
        //高速入力クラス `FastScanner` を使って、最初にクエリ数 `q` を読み取る
		FastScanner fs = new FastScanner();
		int q = fs.nextInt();
        //MyQueue` という自作のデックを長さ `q`（クエリ数）に基づいて初期化
		MyQueue qu = new MyQueue(q);
		for(int i = 0; i < q; i++) {
			int query = fs.nextInt();
			if(query == 0) {
				int d = fs.nextInt();
				int v = fs.nextInt();
				if(d == 0) {
					qu.addFirst(v);;
				}else {
					qu.addLast(v);
				}
			}else if(query == 1) {
				System.out.println(qu.get(fs.nextInt()));
			}else if(query == 2){
				int d = fs.nextInt();
				if(d == 0) {
					qu.removeFirst();;
				}else {
					qu.removeLast();
				}
			}
		}
	}
    // 両端キューの自作クラス
	static class MyQueue {
    //first: 先頭要素の直前の位置
    //last: 末尾要素の直後の位置
    
	    public int[] array;
	    public int first, last;

	    public MyQueue (int n) {
        //中央からスタートすることで、前にも後ろにも挿入できるようにしている（first と last が同じ＝空の状態）
	        array = new int[n * 2];
	        this.first = n;
	        this.last = n;
	    }
	    void addFirst(int i) {
        //要素を前に追加 → first を左にずらす
	    	array[first--] = i;
	    }
	    void addLast(int i) {
	    	array[++last] = i;
	    }
	    void removeFirst() {
	    	first++;
	    }
	    void removeLast() {
	    	last--;
	    }
	    int get(int n) {
	    	return array[n + first + 1];
	    }
	}
	// 高速入力クラス
    static class FastScanner {
	    private final InputStream in = System.in;
	    private final byte[] buffer = new byte[1024];
	    private int ptr = 0;
	    private int buflen = 0;
	    private boolean hasNextByte() {
	        if (ptr < buflen) {
	            return true;
	        }else{
	            ptr = 0;
	            try {
	                buflen = in.read(buffer);
	            } catch (IOException e) {
	                e.printStackTrace();
	            }
	            if (buflen <= 0) {
	                return false;
	            }
	        }
	        return true;
	    }
	    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
	    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
	    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
	    public String next() {
	        if (!hasNext()) throw new NoSuchElementException();
	        StringBuilder sb = new StringBuilder();
	        int b = readByte();
	        while(isPrintableChar(b)) {
	            sb.appendCodePoint(b);
	            b = readByte();
	        }
	        return sb.toString();
	    }
	    public long nextLong() {
	        if (!hasNext()) throw new NoSuchElementException();
	        long n = 0;
	        boolean minus = false;
	        int b = readByte();
	        if (b == '-') {
	            minus = true;
	            b = readByte();
	        }
	        if (b < '0' || '9' < b) {
	            throw new NumberFormatException();
	        }
	        while(true){
	            if ('0' <= b && b <= '9') {
	                n *= 10;
	                n += b - '0';
	            }else if(b == -1 || !isPrintableChar(b)){
	                return minus ? -n : n;
	            }else{
	                throw new NumberFormatException();
	            }
	            b = readByte();
	        }
	    }
	    public int nextInt() {
	        long nl = nextLong();
	        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
	        return (int) nl;
	    }
	    public double nextDouble() { return Double.parseDouble(next());}
	}
}

• FastScanner クラス
  →標準入力を高速に処理するための自作クラス 。標準の Scanner よりずっと速くなるので、競技プログラミングでよく使われる。全部覚える必要はないが理解しておくとカスタムできるのでGOOD
  ただし標準ライブラリでないことからimportできない、読むのが大変なコードなので保守性・可読性が低いことからチーム開発など競プロ系以外では使わないほうがいい

リスト

整数を保持するリストLに対して、以下の操作を行ってください。Lにはその末尾を表すEND要素が常に存在し、各要素はカーソルによって指定され操作されます

• insert(x): カーソルが指す要素の直前に整数xを挿入する。操作の後、カーソルは挿入された要素を指すようになる
• move(d): 整数dが正の場合、カーソルを後方にdだけ移動する。負の場合は前方にdだけ移動する。
• erase(): カーソルが指す要素を削除する。操作の後、カーソルは削除された要素の１つ後方の要素を指すようになる。ただし、そのような要素がない場合はENDを指すようになる。初期状態でLは空であり、カーソルはENDを指しているものとします

AOJ.java

import java.io.*;
import java.util.*;

public class Main {
    static LinkedList<Integer> list = new LinkedList<>();
    static ListIterator<Integer> cursor;

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

        // ENDを最初に追加
        list.add(1000000001); // 仮のEND
        //LinkedList に対して「リスト内を移動できるカーソル（反復子）」を作成
        cursor = list.listIterator(); // 最初はENDを指す

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

        for (int i = 0; i < q; i++) {
            String[] parts = br.readLine().split(" ");
            int op = Integer.parseInt(parts[0]);

            if (op == 0) { // insert
                int x = Integer.parseInt(parts[1]);
                insert(x);
            } else if (op == 1) { // move
                int d = Integer.parseInt(parts[1]);
                move(d);
            } else if (op == 2) { // erase
                erase();
            }
        }

        // ENDを除いて出力
        for (int n : list) {
            if (n != 1000000001) {
                System.out.println(n);
            }
        }
    }

    static void insert(int x) {
        cursor.add(x);     // カーソルの前に挿入
        cursor.previous(); // 挿入された要素を指す
    }

    static void move(int d) {
        while (d > 0 && cursor.hasNext()) {
            cursor.next();
            d--;
        }
        while (d < 0 && cursor.hasPrevious()) {
            cursor.previous();
            d++;
        }
    }

    static void erase() {
        if (!cursor.hasNext()) return; // ENDを指しているなら何もしない
        cursor.next(); // 要素を取得
        cursor.remove(); // それを削除
        // 自動的に次の要素を指す（なければEND）
    }
}

• Integer.parseInt() の引数の型は StringなのでreadLine().split(" ");（＝String[]）を丸々Integer.parseIntしようとするとエラー
• LinkedList を使って整数リストを管理する
• ListIterator で「カーソル（現在位置）」を表す

初期状態
LinkedList<Integer> list = new LinkedList<>();
ListIterator<Integer> cursor = list.listIterator();

このとき
カーソルはリストの先頭（空の位置）：
↓
[]

cursor.add(5);
[5]
   ↑
カーソルは「5」の**後ろ**にいる状態

cursor.add(10);
10 をカーソル位置に挿入
カーソルは 10 の後ろに移動

状態：
[5, 10]
     ↑
  カーソルは 10 の後ろを指している

cursor.previous();
カーソルを 1つ前に戻す


状態：
[5, 10]
   ↑
  カーソルは 10 の前を指している

cursor.next();
カーソルを 1つ後ろに進める

今、カーソルは再び 10 の後ろ

状態：
[5, 10]
     ↑
  カーソルは 10 の後ろを指している

• move()→例えばd=2のときはd が 2 → 1 → 0 となるまでループする＝カーソルを2回後ろに動かすことに相当

ベクトル②

整数を保持するn個の可変長配列Ai(i=0,1,...,n−1)に対して、以下の操作を行ってください。

• pushBack(t, x): Atの末尾に整数xを挿入する
• dump(t): Atの全ての要素を出力する
• clear(t): Atを空にする。ただし、Atが空の場合は何もしない
  Aiは0-オリジンでインデックスが付けられ、初期状態では空とします。

AOJ.java

import java.io.*;
import java.util.ArrayList; //インデックスアクセスなので可変長配列としてはArrayListを用いる
import java.util.List;


public class Main{
   static List<List<Integer>> A;　//Aはリストのリスト
    public static void main(String[]args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //文字列として読み取る
        
        String[] firstLine = br.readLine().split(" ");
        int n = Integer.parseInt(firstLine[0]);
        int q = Integer.parseInt(firstLine[1]);
        A = new ArrayList<>(); // ← ここで n を使えるように main で初期化
        // 各リストを初期化
        for (int i = 0; i < n; i++) {
            A.add(new ArrayList<>());
        }
        
        //q回クエリを読み取る
        for(int i=0;i<q;i++){
        String[] arr =br.readLine().split(" ");//クエリをarrの各要素に分割
        int op =Integer.parseInt(arr[0]);
        if(op==0){
            int t = Integer.parseInt(arr[1]);
            int x = Integer.parseInt(arr[2]);
            pushBack(t,x);
        }else if(op==1){
            int t = Integer.parseInt(arr[1]);
            dump(t);
        }else{
            int t = Integer.parseInt(arr[1]);
            clear(t);
        }
        }
        
    }
    public static void pushBack(int t,int x){
        List<Integer> list = A.get(t);//Aのt番目のリスト{}
        list.add(x);
    }
   public static void dump(int t){
         List<Integer> list = A.get(t);
        for (int i = 0; i < list.size(); i++) {
            if (i > 0) {
                System.out.print(" ");
            }
            System.out.print(list.get(i));
        }
        System.out.println();  // 改行（空でも改行が必要）
    }
    public static void clear(int t){
             List<Integer> list = A.get(t);
            list.clear();
        }
}

• Aはリストのリスト
• A = new ArrayList<>();とするとA は例えば次のような構造に

A = [
  [1, 2, 3],
  [4, 5],
  [],
  [6]
];

ArrayListやLinkedListのような実装に依存する設計よりListのようなインターフェースに依存する設計のほうがい