Javaでプログラミングコンテストに出てみよう! (C++が書ける人向け) - mitsu_koh notebook

このページは普段C++でコンテストに出ている僕が、Javaでも問題を解けるようになりたいと作りました。
同志の人（いるかわかりませんが）の参考になればと思っています。
C++のあのデータ構造はどうやったら書けるんだとかを書いてあります（あくまで基本的なものだけですが）。

標準入出力

• java.util.Scannerを使う
• サンプルコードは下の方のPriorityQueueのやつにあります

vectorを使いたい

• ArrayListクラスを使う
• 注意として、ArrayListインスタンスを要素に持つような配列は作れない
• つまり、ArrayList<Integer> a[] = new ArrayList<Integer>[10]; とかはできない

import java.util.ArrayList;
import java.util.Iterator;

public class ArrayList_prac {
  public static void main(String[] args) {
    ArrayList<Integer> a = new ArrayList<Integer>();
    ArrayList<ArrayList<Integer>> aa = new ArrayList<ArrayList<Integer>>();
    int i, N = 10;
    for (i = 0; i < N; ++i) a.add(i);
    for (Iterator it = a.iterator(); it.hasNext(); ) System.out.printf("%d ", it.next()); System.out.println();
    for (i = 0; i < N; ++i) a.set(i, N-1-i);
    for (i = 0; i < N; ++i) System.out.printf("%d ", a.get(i)); System.out.println();
  }
}

mapを使いたい

• TreeMapクラスを使う

import java.util.Iterator;

class TreeMap_prac {
  public static void main(String[] args) {
    int N = 5;
    // TreeMap
    TreeMap<Character, Integer> map = new TreeMap<Character, Integer>();
    for (int i = 0; i < N; ++i) map.put((char)('a'+i), 'a'+i);
    for (int i = 0; i < N; ++i) {
      System.out.printf("%c:%d ", (char)('a'+i), map.get((char)('a'+i)));
    }
    System.out.println();
    for (Iterator it = map.keySet().iterator(); it.hasNext(); ) {
      Object c = it.next();
      System.out.printf("%c:%d ", c, map.get(c));
    }
    System.out.println();
  }
}

pairを使いたい

• ないので自分で作る
• 変数は修飾子がなくても同じパッケージ内からアクセスできる（pii p; p.x = 0; とかできる）ので問題ない

class pii {
  int x,y;
  pii(int x, int y) { this.x = x; this.y = y; }
}

stack, queueを使いたい

• ArrayDequeクラスを使う

import java.util.ArrayDeque;

public class StaQue {
  public static void main(String[] args) {
    int i, N = 10;
    ArrayDeque<Integer> q = new ArrayDeque<Integer>();
    // stack
    for (i = 0; i < N; ++i) q.addLast(i);
    for (i = 0; i < N; ++i) System.out.printf("%d ", q.removeLast()); System.out.println();
    // queue
    for (i = 0; i < N; ++i) q.add(i);
    for (i = 0; i < N; ++i) System.out.printf("%d ", q.remove()); System.out.println();
  }
}

• 出力は

0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

priority_queueを使いたい

• PriorityQueueクラスを使う

import java.util.Scanner;
import java.util.PriorityQueue;

public class Main {
  static int n;
  static int[] s = new int[1000];
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    while (true) {
      n = sc.nextInt();
      if (n == 0) break;
      int i;
      PriorityQueue<Integer> q = new PriorityQueue<Integer>();
      for (i = 0; i < n; ++i) q.add(sc.nextInt());
      int sum=0;
      for (i = 0; i < n; ++i) {
        int t=q.poll();
        if (i == 0 || i == n-1) continue;
        sum += t;
      }
      System.out.println(sum/(n-2));
    }
  }
}

リストをソートしたい

• Collectionsクラスを使う

import java.util.Comparator;

class area {
  int id, w, d;
  area(area a) { this(a.id, a.w, a.d); }
  area(int id, int w, int d) { this.id = id; this.w = w; this.d = d; }
}

class cmp implements Comparator<area> {
  public int compare(area a, area b) {
    if (a.id == b.id) return 0;
    if (a.id < b.id) return -1;
    return 1;
  }
}

• 上の用にコンパレータを書くとソートすることができる

ArrayList<area> a = new ArrayList<area>();
...
Collections.sort(a, new cmp());

• 組み込みの型はコンパレータがなくても、自然な順序（昇順）でソートされる

ArrayList<Integer> a = new ArrayList<Integer>();
...
Collections.sort(a);

つづく