2441-Arrange the Bulls
問題（外部リンク）
実装の概要
空いているところに牛を配置する問題。深さ優先探索では間に合いません。
ただ、nおよびmの最大値は大きくないのでビットDPであればで求めることができます。
具体的には、例えば1101(2進数)を1、3、4番目のスペースに既に牛が配置されているということにすれば更にそこに次の牛を配置できるかはAND演算で調べることができます。
簡単のため、牛は必ず入力された順に配置されると考えて大丈夫です。
入力例であれば、まず牛1は1および4に配置可能なのでdp[1][0]とdp[8][0]が1になります（それぞれ2^0および2^3）。
次に、牛2は1または3に配置できますが、2進数で考えたときに値の更新が必要なインデックスは5（1+2^2）、9（8+2^0）、12（8+2^2）です。場合によっては同じインデックスに複数回加算することもあります。加算する値は前の状態のものを使います。
気をつけることとして、今回の問題ではメモリの制約が若干厳しいので途中経過までメモすることができません。（更に厄介なことにローカル環境ではそれでも動いてしまいました）
そのため、そもそも次の状態を計算するには直前の状態さえ分かれば十分なので配列の使い回しを行います。この方法であればメモリの制約もクリアできます。
public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int pos[][] = new int[n][]; for(int i = 0; i < n; i++){ int tmp = sc.nextInt(); pos[i] = new int[tmp]; for(int j = 0; j < pos[i].length; j++){ pos[i][j] = sc.nextInt() - 1; } } //2のべき乗の配列を予め作っておく int powers[] = new int[21]; for(int i = 0; i <= 20; i++){ powers[i] = (int)Math.pow(2, i); } //dp[i][]: 配置がiの状態となるパターン数 //途中経過もすべて格納しようとするとMLEになるので //2列だけ用意して随時使い回す int dp[][] = new int[powers[m]][2]; //一匹目で初期化 for(int i = 0; i < pos[0].length ; i++){ dp[powers[pos[0][i]]][0] = 1; } for(int i = 1; i < n; i++){ for(int j = 0; j < dp.length; j++){ //jとなるような配置が存在するなら //（もしこれが0であるならば続ける必要がないので無視） if(dp[j][0] != 0){ for(int k = 0; k < pos[i].length ; k++){ int tmpIndex = pos[i][k]; //tmpIndexが既に配置されていないところなら if((int)(j & powers[tmpIndex]) == 0){ dp[j + powers[tmpIndex]][1] += dp[j][0]; } } } } //配列の内容の移し替えおよびクリア for(int j = 0; j < dp.length; j++){ dp[j][0] = dp[j][1]; dp[j][1] = 0; } } long result = 0; //結果は0列目の総和で求められる for(int i = 0; i < dp.length; i++){ result += dp[i][0]; } System.out.println(result); } }
2254-Fastest Route
問題（外部リンク）
実装の概要
ステージを経由する順序によってそれぞれのステージをクリアするための時間が変わるためグラフのアルゴリズムをそのまま使うことはできません。
また、要素数は少ないですが流石にですべてのパターンを網羅しようとすると時間が足りません、
そこで今回は動的計画法で考えます。例えば、ステージ1,2,3,4をクリアするとして最後をステージ4と固定したとしても6パターン有りえますが、装備1と2と3を入手（ステージ1と2と3をクリア）するのにかかる最小の時間さえ分かっていれば順番は気にする必要がありません。
上記の場合であれば、
(1,2,3をクリアするのにかかる最短時間)=MIN(装備1,2を所持して3をクリア, 装備1,3を所持して2をクリア, 装備2,3を所持して1をクリア)
となります。
最終的にはで解くことができます。
なお、最後にどのステージをクリアするのが最短であるかは改めてチェックする必要があること（N番目のステージとは限らない）、装備を使わない方が速いこともあるという点にも注意が必要です。
public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true){ int n = sc.nextInt(); if(n == 0){ break; } int matrix[][] = new int[n][n + 1]; for(int i = 0; i < n; i++){ for(int j = 0; j < n + 1; j++){ matrix[i][j] = sc.nextInt(); } } System.out.println(solve(matrix)); } } //dpで解く static int solve(int[][] matrix){ int n = matrix.length; //dp[i][j]: 装備iを所持しているとして（ビットで管理） //最後にjを訪れたときの最小コスト int dp[][] = new int[(int)Math.pow(2, n)][n]; //2のべき乗を保持するための配列 int pow[] = new int[n]; //まずは装備品無し for(int i = 0; i < n; i++){ dp[0][i] = matrix[i][0]; //ついでに武器用のべき乗計算 pow[i] = (int)Math.pow(2, i); } for(int i = 1; i < dp.length; i++){ for(int j = 0; j < n ; j++){ dp[i][j] = Integer.MAX_VALUE; int prevCost = Integer.MAX_VALUE; for(int k = 0; k < n ;k++){ //k番目の武器を持っているか if(i - pow[k] >= 0 && (int)(i & pow[k]) != 0){ prevCost = Math.min(prevCost, matrix[j][k + 1]); } } for(int k = 0; k < n; k++){ //k番目の武器を持っているか if(i - pow[k] >= 0 && (int)(i & pow[k]) != 0){ //kの次にjに着いたとする int prevIndex = i - pow[k]; //コストの更新。装備品を使わなかった場合も考慮する dp[i][j] = Math.min(dp[i][j], dp[prevIndex][k] + Math.min(matrix[j][0], prevCost)); } } } } int result = Integer.MAX_VALUE; //最後に着いたステージによってコストが変わるため //その中で最小のものを探す for(int i = 0; i < n; i++){ result = Math.min(result, dp[dp.length - pow[i] - 1][i]); } return result; } }
3368-Frequent values
問題（外部リンク）
実装の概要
指定された区間の中で最も長く同じ数字が続いた箇所の長さを求める問題です。要素数とクエリ数が多いためその都度ループを回すと間に合いません。
そこで今回はセグメント木を使います。ただし区間内の最大値を求める問題と比べると実装の際に考慮しなければならない箇所が多いと思います。
以下の実装ではセグメント木のそれぞれの要素自体に
- その区間内で同じ数字が続く最長の長さ
- 左端から同じ数字が続く最長の長さ
- 右端から同じ数字が続く最長の長さ
- 左端の数字
- 右端の数字
を保持させています。
最長の長さを求める場合等には右の区間と左の区間にまたがる可能性なども考慮しながら処理する必要があります。
今回の実装はだいぶコード長があるため、より簡潔に書く方法を思いつき次第書き直したいと思います。
public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); while(true){ String input = br.readLine(); if(input.equals("0")){ break; } String[] tmpArray = input.split(" "); int n = Integer.parseInt(tmpArray[0]); int q = Integer.parseInt(tmpArray[1]); MaxLengthSegmentTree maxseg = new MaxLengthSegmentTree(n); int array[] = new int[n]; tmpArray = br.readLine().split(" "); for(int i = 0; i < n; i++){ array[i] = Integer.parseInt(tmpArray[i]); maxseg.update(i, array[i]); } for(int i = 0; i < q; i++){ tmpArray = br.readLine().split(" "); //あえて開区間としてクエリを投げる int from = Integer.parseInt(tmpArray[0]) - 1; int to = Integer.parseInt(tmpArray[1]); System.out.println(maxseg.query(from, to)); } } } } class MaxLengthSegmentTree { protected int n; protected Node[] data; //nは要素の個数 MaxLengthSegmentTree(int n){ //要素数を2のべき乗にしておく this.n = 1; while (this.n < n){ this.n *= 2; } this.data = new Node[this.n*2 - 1]; initData(); } private void initData(){ for(int i = 0; i < this.data.length; i++){ this.data[i] = new Node(); } } //for debug void show(){ System.out.println("Data info"); for(int i = 0; i < this.data.length; i++){ System.out.println("i = "+ i + " " + this.data[i].toString()); } } void update(int k, int a){ k += n - 1; //区間長が1なら右の数字も左の数字もa data[k].leftNum = a; data[k].rightNum = a; while(k > 0){ k = (k - 1) / 2; int l = k * 2 + 1; int r = k * 2 + 2; //leftの更新 //2区間を連結可能な場合 if(data[l].leftNum == data[r].leftNum && data[l].rightNum == data[r].leftNum){ data[k].leftLen = data[l].leftLen + data[r].leftLen; } //連結できないならそのままleftLenを引き継ぐ else { data[k].leftLen = data[l].leftLen; } data[k].leftNum = data[l].leftNum; //rightの更新 if(data[r].rightNum == data[l].rightNum && data[l].rightNum == data[r].leftNum){ data[k].rightLen = data[l].rightLen + data[r].rightLen; } else { data[k].rightLen = data[r].rightLen; } data[k].rightNum = data[r].rightNum; //midの更新 //子セグメントのうち長い方 data[k].midLen = Math.max(data[l].midLen, data[r].midLen); //連結可能かつ繋げた部分の方が長い場合は更新 if(data[l].rightNum == data[r].leftNum){ data[k].midLen = Math.max(data[k].midLen, data[l].rightLen + data[r].leftLen); } } } //[a, b)までの範囲から目的の値を探す public int query(int a, int b){ return query(a, b, 0, 0, this.n).midLen; } private Node query(int a, int b, int k, int l, int r) { // [a, b)と[l, r)が交差しない if(r <= a || b <= l){ return null; } // [a, b)が[l, r)を完全に含んでいる if(a <= l && r <= b){ return data[k]; } //そうでない場合は子セグメントに再帰的に処理を行う else { Node vl = query(a, b, k*2 + 1, l, (l + r)/2); Node vr = query(a, b, k*2 + 2, (l + r) / 2, r); if(vl == null){ return vr; } else if(vr == null){ return vl; } int result = Math.max(vl.midLen, vr.midLen); int left = vl.leftLen; //連結可能な場合 if(vl.leftNum == vr.leftNum){ left = vl.leftLen + vr.leftLen; } int right = vr.rightLen; if(vl.rightNum == vr.rightNum){ right = vl.rightLen + vr.rightLen; } if(vl.rightNum == vr.leftNum){ result = Math.max(result, vl.rightLen + vr.leftLen); } return new Node(result, left, right, vl.leftNum, vr.rightNum); } } } class Node { int midLen = 1; int leftLen = 1; int rightLen = 1; int leftNum = Integer.MAX_VALUE; int rightNum = Integer.MIN_VALUE; Node(){ this(1, 1, 1, Integer.MAX_VALUE, Integer.MIN_VALUE); } Node(int mid, int ll, int rl, int ln, int rn){ this.midLen = mid; this.leftLen = ll; this.rightLen = rl; this.leftNum = ln; this.rightNum = rn; } public String toString(){ return "left "+leftLen+" mid "+midLen + " right " + rightLen + " leftNum "+ leftNum + " rightNum "+rightNum; } }
3624-Balanced Lineup
問題（外部リンク）
実装の概要
今回の問題で重要なのはある区間における最小値と最大値なので、それぞれをセグメント木で管理することで高速に処理を行うことができます。（クエリ数が多いので、その都度ループを回して区間内を探索すると間に合いません）
１つのセグメント木で両方とも管理することも可能だと思いますが、この実装ではそれぞれ別のクラスとして作成しました。
ただ、ほぼ似通った処理も多いためabstractなセグメント木のクラスを作成しそれを継承する形を採っています。
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]); int height[] = new int[n]; MinSegmentTree minseg = new MinSegmentTree(n); MaxSegmentTree maxseg = new MaxSegmentTree(n); //セグメント木の値更新 for(int i = 0; i < n; i++){ height[i] = Integer.parseInt(br.readLine()); minseg.update(i, height[i]); maxseg.update(i, height[i]); } for(int i = 0; i < q; i++){ tmpArray = br.readLine().split(" "); int from = Integer.parseInt(tmpArray[0]); int to = Integer.parseInt(tmpArray[1]); //問題が1-indexedなので1ずらす int min = minseg.query(from - 1, to); int max = maxseg.query(from - 1, to); //fromとtoが同じ場合は差はないはず if(from == to){ min = 0; max = 0; } System.out.println(max - min); } } } //抽象的なセグメント木 abstract class SegmentTree { protected int n; protected int[] data; private int initValue; //nは要素の個数、initValueは目的に応じて初期化の値を変えること SegmentTree(int n, int initValue){ this.n = 1; while (this.n < n){ this.n *= 2; } this.data = new int[this.n*2 - 1]; this.initValue = initValue; initData(); } private void initData(){ Arrays.fill(data, initValue); } void update(int k, int a){ k += n - 1; data[k] = a; while(k > 0){ k = (k - 1) / 2; data[k] = choose(data[k * 2 + 1], data[k * 2 + 2]); } } //目的に合わせて値選択のための処理を実装すること abstract protected int choose(int a, int b); //[a, b)までの範囲から目的の値を探す public int query(int a, int b){ return query(a, b, 0, 0, this.n); } private int query(int a, int b, int k, int l, int r) { if(r <= a || b <= l){ return initValue; } if(a <= l && r <= b){ return data[k]; } else { int vl = query(a, b, k*2 + 1, l, (l + r)/2); int vr = query(a, b, k*2 + 2, (l + r) / 2, r); return choose(vl, vr); } } } //最小値の管理のためのセグメント木 class MinSegmentTree extends SegmentTree { MinSegmentTree(int n) { super(n, Integer.MAX_VALUE); } @Override protected int choose(int a, int b) { return Math.min(a, b); } } //最大値の管理のためのセグメント木 class MaxSegmentTree extends SegmentTree { MaxSegmentTree(int n) { super(n, Integer.MIN_VALUE); } @Override protected int choose(int a, int b) { return Math.max(a, b); } }
2155-Matrix
問題（外部リンク）
実装の概要
A[x, y]が1か0かは、A[x, y]が何回長方形の内部に入ったかで判断することができます。
ただ、長方形内の全ての点を塗りつぶすように数え上げると間に合いません。
そこで、長方形の左上の座標に1、右上の更に1つ右に-1、左下の更に1つ下に-1、右下の更に1つ右下に1を加算します。
こうすることで（A[x,y]が長方形の内部に入った回数）=（A[1,1]からA[x,y]までの合計）となります。右下の更に右下に1を加算したのは、そうしないとそこの座標だけ2回長方形の外に出た扱いになってしまうからです。
加算の手間はで済むようになりましたが、クエリ数が多く表示の度に
もかけるわけには行きません。
そこで、これらの処理を2次元のBITで管理することでA[1,1]からA[x,y]までの総和をで計算できるようになります。具体的なBITの実装は以下を参考にしてください。
public class Main { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(br.readLine()); for(int i = 0; i < t; i++){ String str = br.readLine(); String tmpArray[] = str.split(" "); int n = Integer.parseInt(tmpArray[0]); int x = Integer.parseInt(tmpArray[1]); BIT2D bits = new BIT2D(n + 1, n + 1); for(int j = 0; j < x; j++){ tmpArray = br.readLine().split(" "); if(tmpArray[0].equals("C")){ int x1 = Integer.parseInt(tmpArray[1]) - 1; int y1 = Integer.parseInt(tmpArray[2]) - 1; int x2 = Integer.parseInt(tmpArray[3]) - 1; int y2 = Integer.parseInt(tmpArray[4]) - 1; //長方形の内部の始まり bits.add(y1, x1, 1); //長方形から外に出る bits.add(y1, x2 + 1, -1); bits.add(y2 + 1, x1, -1); //上記で2回引いてしまったので調整 bits.add(y2 + 1, x2 + 1, 1); } else { int x1 = Integer.parseInt(tmpArray[1]) - 1; int y1 = Integer.parseInt(tmpArray[2]) - 1; //長方形の中に入った回数が奇数なら1、偶数なら0 System.out.println(bits.sum(y1, x1)%2); } } //テストケース間に改行 if(i != t - 1){ System.out.println(); } } } } class BIT2D { private int n; private int m; private BIT[] bits; BIT2D(int n, int m){ this.n = n; this.m = m; bits = new BIT[n + 1]; for(int i = 1 ; i <= n ; i++){ bits[i] = new BIT(m); } } int sum(int i, int j) { int s = 0; i++; while(i > 0) { s += bits[i].sum(j); i -= i & (-i); } return s; } void add(int i, int j, int k){ i++; while(i <= n){ bits[i].add(j, k); i += i & (-i); } } } class BIT { private int n; private int[] bit; BIT(int n){ this.n = n; bit = new int[n + 1]; } int sum(int i) { int s = 0; i++; while(i > 0) { s += bit[i]; i -= i & (-i); } return s; } void add(int i, int k){ i++; while(i <= n){ bit[i] += k; i += i & (-i); } } }
ITP2_2 Basic Data Structures
A : Stack
問題（外部リンク）
実装の概要
Java.util.Stack内に必要なメソッドは既に容易されているのでこれを利用することでACできます。要素を取り出さないときはpeek()です。
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") Stack<Integer>[] stackArray = new Stack[n]; for(int i = 0; i < n; i++){ stackArray[i] = new Stack<Integer>(); } for(int i = 0; i < q; i++){ tmpArray = br.readLine().split(" "); //push if(tmpArray[0].equals("0")){ int t = Integer.parseInt(tmpArray[1]); int x = Integer.parseInt(tmpArray[2]); stackArray[t].push(x); } //top else if(tmpArray[0].equals("1")){ int t = Integer.parseInt(tmpArray[1]); if(!stackArray[t].isEmpty()){ System.out.println(stackArray[t].peek()); } } //pop else { int t = Integer.parseInt(tmpArray[1]); if(!stackArray[t].isEmpty()){ stackArray[t].pop(); } } } } }
B : Queue
問題（外部リンク）
実装の概要
Java.util.Queueはインターフェースなのでこれをそのままインスタンス化することはできませんが、ArrayListがQueueを実装しておりenqueueやdequeueなどを行うことができます。
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") ArrayList<Integer>[] queue = new ArrayList[n]; for(int i = 0; i < n; i++){ queue[i] = new ArrayList<Integer>(); } for(int i = 0; i < q; i++){ tmpArray = br.readLine().split(" "); //enqueue if(tmpArray[0].equals("0")){ int t = Integer.parseInt(tmpArray[1]); int x = Integer.parseInt(tmpArray[2]); queue[t].add(x); } //front else if(tmpArray[0].equals("1")){ int t = Integer.parseInt(tmpArray[1]); if(!queue[t].isEmpty()){ System.out.println(queue[t].get(0)); } } //dequeue else { int t = Integer.parseInt(tmpArray[1]); if(!queue[t].isEmpty()){ queue[t].remove(0); } } } } }
C : Priority Queue
問題（外部リンク）
実装の概要
Java.util.PriorityQueueを利用することで要求されている仕様を満たすことができます。
Javaの優先度付きキューはデフォルトの場合昇順になっているため、降順にしたい場合はコンストラクタにComparatorを渡してそのように設定します。
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") PriorityQueue<Integer>[] queue = new PriorityQueue[n]; for(int i = 0; i < n; i++){ //降順に設定 queue[i] = new PriorityQueue<Integer>(new Comparator<Integer >() { @Override public int compare(Integer a, Integer b) { return b - a; } }); } for(int i = 0; i < q; i++){ tmpArray = br.readLine().split(" "); //insert if(tmpArray[0].equals("0")){ int t = Integer.parseInt(tmpArray[1]); int x = Integer.parseInt(tmpArray[2]); queue[t].add(x); } //getMax else if(tmpArray[0].equals("1")){ int t = Integer.parseInt(tmpArray[1]); if(!queue[t].isEmpty()){ System.out.println(queue[t].peek()); } } //deleteMax else { int t = Integer.parseInt(tmpArray[1]); if(!queue[t].isEmpty()){ queue[t].poll(); } } } } }
D : Splice
問題（外部リンク）
実装の概要
JavaのリストにはaddAll()メソッドが存在しますが、内部的に1つずつ要素を追加しているのかあまり高速では動作しません。Collections.addAll()も同様です。
そのため、spliceを高速で行うためには自分でリストを実装し手動でリンクをつなぎ替える必要があります。
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]); MyList[] lists = new MyList[n]; for(int i = 0; i < n; i++){ lists[i] = new MyList(); } for(int i = 0; i < q; i++){ tmpArray = br.readLine().split(" "); //insert if(tmpArray[0].equals("0")){ int t = Integer.parseInt(tmpArray[1]); int x = Integer.parseInt(tmpArray[2]); lists[t].add(x); } //dump else if(tmpArray[0].equals("1")){ int t = Integer.parseInt(tmpArray[1]); lists[t].dump(); } //splice else { int s = Integer.parseInt(tmpArray[1]); int t = Integer.parseInt(tmpArray[2]); lists[t].splice(lists[s]); } } } } class MyList { MyNode head; MyNode tail; MyList (){ head = new MyNode(0, null, null); tail = new MyNode(0, head, null); head.next = tail; } void add(int data){ MyNode node = new MyNode(data, null, tail); node.prev = tail.prev; tail.prev = node; node.prev.next = node; } void dump(){ MyNode current = head.next; StringBuffer sb = new StringBuffer(); while(current.next != null){ sb.append(current.data); if(current.next != tail){ sb.append(" "); } current = current.next; } System.out.println(sb); } void splice(MyList list){ MyNode first = list.head.next; MyNode last = list.tail.prev; first.prev = this.tail.prev; this.tail.prev.next = first; last.next = this.tail; this.tail.prev = last; list.head.next = list.tail; list.tail.prev = list.head; } } class MyNode { MyNode prev; MyNode next; int data; MyNode (int data, MyNode prev, MyNode next){ this.data = data; this.prev = prev; this.next = next; } }
ITP2-1 Dynamic Arrays and List
A : Vector
問題（外部リンク）
実装の概要
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
問題（外部リンク）
実装の概要
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
問題（外部リンク）
実装の概要
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の配列を作ることで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); } }
