Java向け競プロライブラリ(ランレングス)

Java 競プロライブラリ

文字列をランレングス圧縮すると解きやすい問題向けのライブラリです。なお、本記事では自前ライブラリのPairを利用しています（以下参照）。

Java向け競プロライブラリ(ペア) - JunKobayashi’s diary

 

例えば以下の問題で役に立ちます。

AtCoder Beginner Contest 299 C - Dango

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public final class RunLength {

	public static final List<Pair<Character, Integer>> getRunLengthOf(String s) {
		var res = new ArrayList<Pair<Character, Integer>>();
		for (int i = 0, len = 0, prevChar = s.charAt(0), n = s.length(); i < n; ++i) {
			if (s.charAt(i) == prevChar) {
				++len;
			} else {
				var p = new Pair<Character, Integer>((char) prevChar, len);
				res.add(p);
				len = 1;
				prevChar = s.charAt(i);
			}

			if (i == n - 1) {
				var p = new Pair<Character, Integer>((char) prevChar, len);
				res.add(p);
			}
		}
		return res;
	}

}

Java向け競プロライブラリ（順列）

Java 競プロライブラリ

まずは、1つの順列のみを必要とする問題で使用するクラス（ただし、

\begin{align} 10! &= 3628800 < 3.7\times 10^6\\ 11! &= 39916800 < 4\times 10^7\\ 12! &= 479001600 > 4.7\times 10^8 \end{align}

を考慮すると、探索範囲の大きさが1つの順列のみによって定まる場合、使用可能なのはせいぜい順列の長さが11までか）です。例えば以下の問題で役に立ちます。

AtCoder Beginner Contest 319 C - False Hope

AtCoder Beginner Contest 320 C - Slot Strategy 2 (Easy)

※以下、どのクラスでもpermフィールドがprivateになっていませんが、Mainクラスからは読み出しのみ行い、競プロ向けの個人的利用のみを前提としているため良しとしています。また、探索実行のためにはbuildToSearchメソッドを呼び出します。

import java.util.stream.IntStream;

/**
 * 1つの順列を用いて全探索する
 */
final class SinglePermutation {

	private int[] init;
	int[] perm;
	private boolean[] used;

	private void process() {
		// 順列生成完了後に実行したい処理をここに書く
	}

	/**
	 * 順列の長さをもとにインスタンスを生成する
	 * @param size 順列の長さ
	 * @return 引数で指定した長さを持つ順列全探索用インスタンス
	 * @throws IllegalArgumentException （{@code size < 1} の場合）
	 */
	public static SinglePermutation instantiateWithSizeOf(int size) {
		if (size < 1) {
			throw new IllegalArgumentException();
		}
		return new SinglePermutation(size);
	}

	/**
	 * 必要となる順列を全て生成し、それぞれに対して所望の探索処理を実行する
	 */
	public void buildToSearch() {
		build(0);
	}

	/**
	 * 順列の転倒数を求める。
	 * @return 順列の転倒数
	 */
	public int findInversionNumber() {
		int res = 0;

		for (int i = 0; i < this.perm.length; ++i) {
			for (int j = i + 1; j < this.perm.length; ++j) {
				if (this.perm[i] > this.perm[j]) {
					res += 1;
				}
			}
		}

		return res;
	}

	private SinglePermutation(int size) {
		this.init = IntStream.range(0, size).toArray();
		this.perm = new int[size];
		this.used = new boolean[size];
	}

	private void build(int depth) {
		if (depth == this.init.length) {
			process();
			return;
		}

		for (int i = 0; i < this.init.length; ++i) {
			if (this.used[i]) {
				continue;
			}

			this.perm[depth] = this.init[i];
			this.used[i] = true;
			build(depth + 1);
			this.used[i] = false;
		}
	}

}

 

次は、等しい長さを持つ複数の順列を探索対象とする問題で使用するクラスです。

import java.util.stream.IntStream;

/**
 * 0から{@code n - 1}までの整数を各要素とする等しい長さの2つ以上の順列たちにより全探索を行う
 */
final class FixedLengthMultiPermutations {

	private int numOfPerm;
	private int[] init;
	int[][] perm;
	private boolean[][] used;

	private void process() {
		// 順列生成完了後に実行したい処理をここに書く
	}

	/**
	 * 必要となる順列を全て生成し、それぞれに対して所望の探索処理を実行する
	 */
	public void buildToSearch() {
		build(0, 0);
	}

	/**
	 * 指定した順列の転倒数を求める。
	 * @param r 対象となる順列の番号（0-indexed）
	 * @return 対象とした順列の転倒数
	 */
	public int findInversionNumberOf(int r) {
		final int[] targetPerm = this.perm[r];
		int res = 0;

		for (int i = 0; i < targetPerm.length; ++i) {
			for (int j = i + 1; j < targetPerm.length; ++j) {
				if (targetPerm[i] > targetPerm[j]) {
					res += 1;
				}
			}
		}

		return res;
	}

	/**
	 * 順列の転倒数の合計を求める。
	 * @return 転倒数の合計
	 */
	public int findSumOfInversionNumber() {
		int res = 0;
		for (int i = 0; i < this.numOfPerm; ++i) {
			res += findInversionNumberOf(i);
		}
		return res;
	}

	/**
	 * 順列の個数と各順列の長さから順列全探索用インスタンスを生成するビルダー<br>
	 * （デフォルトでは長さが3の順列を2個持つ）
	 */
	public static class Builder {

		private int numOfPerm = 2;
		private int size = 3;

		/**
		 * 順列の個数を設定する
		 * @param numOfPerm 順列の個数
		 * @return このビルダー自身への参照
		 * @throws {@code numOfPerm < 2} の場合
		 */
		public Builder setNumOfPerm(int numOfPerm) {
			if (numOfPerm < 2) {
				throw new IllegalArgumentException();
			}
			this.numOfPerm = numOfPerm;
			return this;
		}

		/**
		 * 各順列の長さを設定する
		 * @param size 各順列の長さ
		 * @return このビルダー自身への参照
		 * @throws {@code size < 1} の場合
		 */
		public Builder setSize(int size) {
			if (size < 1) {
				throw new IllegalArgumentException();
			}
			this.size = size;
			return this;
		}

		/**
		 * 順列の個数と各順列の長さから順列全探索用インスタンスを生成する
		 * @return 順列の個数と各順列の長さから生成される順列全探索用インスタンス
		 */
		public FixedLengthMultiPermutations build() {
			return new FixedLengthMultiPermutations(this.numOfPerm, this.size);
		}

	}

	private FixedLengthMultiPermutations(int numOfPerm, int size) {
		this.numOfPerm = numOfPerm;
		this.init = IntStream.range(0, size).toArray();
		this.perm = new int[numOfPerm][size];
		this.used = new boolean[numOfPerm][size];
	}

	private void build(int permIdx, int depth) {
		if (permIdx == this.numOfPerm) {
			process();
			return;
		}

		if (depth == this.init.length) {
			build(permIdx + 1, 0);
			return;
		}

		for (int i = 0, f = this.init.length; i < f; ++i) {
			if (this.used[permIdx][i]) {
				continue;
			}

			this.perm[permIdx][depth] = this.init[i];
			this.used[permIdx][i] = true;
			build(permIdx, depth + 1);
			this.used[permIdx][i] = false;
		}
	}

}

 

最後に、それぞれが異なる長さを持ち得るような複数の順列たちを探索対象とする問題で使用するクラスです。

import java.util.stream.IntStream;

/**
 * 異なる長さを持つ2つ以上の順列たちにより全探索を実行する
 */
final class VariableLengthMultiPermutations {

	private int numOfPerm;
	private int[][] init;
	int[][] perm;
	private boolean[][] used;

	private void process() {
		// 順列を生成した後に行いたい処理をここに書く
	}

	/**
	 * それぞれの順列の長さをもとにインスタンスを生成する
	 * @param sizes それぞれの順列の長さ
	 * @return それぞれの引数で指定した長さを持つ順列全探索用インスタンス
	 * @throws （{@code sizes.length < 2 || sizes[i] < 1}） の場合
	 */
	public static VariableLengthMultiPermutations instantiateWithSizesOf(int... sizes) {
		if (sizes.length < 2) {
			throw new IllegalArgumentException();
		}

		for (int i = 0; i < sizes.length; ++i) {
			if (sizes[i] < 1) {
				throw new IllegalArgumentException();
			}
		}

		return new VariableLengthMultiPermutations(sizes);
	}

	/**
	 * 必要となる順列を全て生成し、それぞれに対して所望の探索処理を実行する
	 */
	public void buildToSearch() {
		build(0, 0);
	}

	/**
	 * 指定した順列の転倒数を求める。
	 * @param r 対象となる順列の番号（0-indexed）
	 * @return 対象とした順列の転倒数
	 */
	public int findInversionNumberOf(int r) {
		final int[] targetPerm = this.perm[r];
		int res = 0;

		for (int i = 0; i < targetPerm.length; ++i) {
			for (int j = i + 1; j < targetPerm.length; ++j) {
				if (targetPerm[i] > targetPerm[j]) {
					res += 1;
				}
			}
		}

		return res;
	}

	/**
	 * 順列の転倒数の合計を求める。
	 * @return 転倒数の合計
	 */
	public int findSumOfInversionNumber() {
		int res = 0;
		for (int i = 0; i < this.numOfPerm; ++i) {
			res += findInversionNumberOf(i);
		}
		return res;
	}

	private VariableLengthMultiPermutations(int... sizes) {
		this.numOfPerm = sizes.length;
		this.init = new int[this.numOfPerm][];
		this.perm = new int[this.numOfPerm][];
		this.used = new boolean[this.numOfPerm][];
		for (int i = 0; i < this.numOfPerm; ++i) {
			this.init[i] = IntStream.range(0, sizes[i]).toArray();
			this.perm[i] = new int[sizes[i]];
			this.used[i] = new boolean[sizes[i]];
		}
	}

	private void build(int permIdx, int depth) {
		if (permIdx == this.numOfPerm) {
			process();
			return;
		}

		if (depth == this.init[permIdx].length) {
			build(permIdx + 1, 0);
			return;
		}

		for (int i = 0, f = this.init[permIdx].length; i < f; ++i) {
			if (this.used[permIdx][i]) {
				continue;
			}

			this.perm[permIdx][depth] = this.init[permIdx][i];
			this.used[permIdx][i] = true;
			build(permIdx, depth + 1);
			this.used[permIdx][i] = false;
		}
	}

}

Java SE 11 Gold 自分用メモ(3)

Java 資格

  1. 並行処理：シングルコアのCPUで見られる。実行すべき複数の処理が存在する時、一定の時間(0.1秒とか0.01秒とか)が経過するごとに実行する処理を切り替えることにより実現する(ある瞬間だけを切り取ると実行している処理は当然1つのみ)
  2. 並列処理：マルチコアのCPUで見られる。実行すべき複数の処理について、それぞれのコアで別々に処理を行うことにより実現する(ある瞬間だけを切り取っても当然複数の処理を実行している)
  3. Javaにおけるスレッドとは、プログラムを実際に走らせた際、実行するメソッドの情報がメモリのスタック領域に出入りする一連の流れのこと(複数のスタックが並行処理を行うのがマルチスレッド)
  4. 別のスレッドを生成したい場合はjava.lang.Thread(またはそのサブクラス)のstartメソッドを利用する(startメソッドの処理は重く、新しいスタックが完成するまでにstartメソッドを呼び出している側の処理が進行する場合が多い。ただし必ずしもそうなるわけではなく、新しいスレッドの方が早く処理を進行させる場合もある。これはJVMの実装やCPUのタイミングなどによるため、プログラム自体で制御させることはできない)
  5. Threadのstartメソッドを使うサンプル(startメソッドを呼び出すとスレッドを新しく作り、そのスレッドでrunメソッドを実行) 
    System.out.println("main thread started");
Thread th = new Thread() {
	@Override
	public void run() {
		System.out.println("a new thread started");
	}
};
th.start();
System.out.println("main thread finished");
    プログラム以外の条件により、出力順が以下の2パターンのどちらかになる 
    main thread started
main thread finished
a new thread started
    main thread started
a new thread started
main thread finished
  6. java.lang.Runnableインタフェース(新しいスレッドで実行するrunメソッドのみを持つ)を実現したクラスをThreadのコンストラクタに渡すことによっても新しいスレッドを作ることができる 
    System.out.println("main thread started");
Thread th = new Thread(() -> System.out.println("th started"));
th.start();
Thread thh = new Thread(() -> {
	System.out.println("thh started");
	System.out.println("thh thh thh");
});
thh.start();
System.out.println("main thread finished");
  7. 新しく生成するスレッドの数が多くなりすぎると、既に処理を終えているスレッドがあるにもかかわらずまた新しくスレッドを生成するなど、かえってパフォーマンスを悪化させる場合がある
  8. スレッドプール：あらかじめ一定数空のスレッドを用意しておき、処理を終えて次のタスク待ちになっているものを使い回す仕組み
  9. スレッドプールを実現したうえで新しくスレッドを生成するための、java.util.concurrent.Executorsクラスのメソッドの使い方は以下の通り(いずれもjava.util.concurrent.ExecutorServiceで返される)
    1. newSingleThreadExecutor：プール内に1スレッドのみ
    2. newFixedThreadPool：引数で指定した個数のスレッドをプール内に生成
    3. newCachedThreadPool：必要に応じてプール内のスレッド数が増減する(60秒以上使用されないスレッドは破棄され、60秒未満であれば再利用)
    newFixedThreadExecutorを利用して3スレッドをプール内に生成する例 
    ExecutorService es = Executors.newFixedThreadPool(3);
for (int i = 0; i < 10; ++i) {
	es.submit(() -> System.out.println(Thread.currentThread().getId()));
	// submitメソッドに与えたRunnableインタフェースの実装に従いプール内のスレッドがタスク実行
}
  10. java.util.concurrent.ScheduledExecutorServiceは、ExecutorServiceを拡張したインタフェースで、submitメソッドではなくscheduleメソッド(引数は3つ：処理内容Runnable, 遅延させる時間long, 時間の単位java.util.concurrent.TimeUnit)を使うことにより引数で指定した処理を指定した時間だけ遅延させて実行可能
  11. ScheduledExecutorServiceのメソッドscheduleAtFixedRate(引数4つ：処理内容, 最初の処理までの遅延時間, 処理同士の時間間隔, 時間の単位)を使うことにより、指定した処理を繰り返し実行可能(処理が始まってから終わるまでの時間が、指定した間隔よりも長くなる場合、処理が終わってから次回の処理が始まる。それに対し、処理時間が指定した間隔よりも短くなる場合、指定した時間間隔が経過するまで次の処理は行われない)
  12. ScheduledExecutorServiceのメソッドscheduleWithFixedDelay(引数のパターンはscheduleAtFixedRateと同じ)を使うことにより、指定した処理が完了した瞬間から一定時間だけ間隔をあけて繰り返し同じ処理を行うことが可能
  13. ExecutorsクラスのメソッドnewScheduledThreadPool(1つの引数：スレッド数)により、複数のScheduledExecutorServiceをスレッドプールとして扱うことが可能(以下使用例参照) 
    public static final void main(String[] args) throws InterruptedException {
	ScheduledExecutorService ses = Executors.newScheduledThreadPool(2);
	ses.scheduleWithFixedDelay(() -> System.out.print("A"), 0, 1, TimeUnit.SECONDS);
	ses.scheduleWithFixedDelay(() -> System.out.print("B"), 1, 1, TimeUnit.SECONDS);
	Thread.sleep(10000L);
	ses.shutdown();
	// ABABABABABABABABABAと出力される
}
  14. java.util.concurrent.Futureインタフェースを使うことにより(ここでのfutureは「見込み」程度の意味)、スレッドを生成した側のメソッドが、新しく作ったスレッドの実行結果を知ることができる(以下使用例参照) 
    public static final void main(String[] args) throws Exception {
	ExecutorService es = Executors.newSingleThreadExecutor();
	// Runnableは値を受け取らず、返しもしない
	Future f = es.submit(() -> System.out.println("thread f"));
	if (f.get() == null) {
		System.out.println("thread f successfully finished");
	}
	// submitの第2引数でスレッド完了時の値を指定可能
	Future<Integer> g = es.submit(() -> System.out.println("thread g"), 0);
	if (g.get() == 0) {
		System.out.println("thread f successfully finished");
	}
	es.shutdown();
}
  15. Runnableとjava.util.concurrent.Callableは構造がよく似た関数型インタフェースなので混同しないようにする：Runnableのメソッドrunは引数・返り値ともにないのに対し、Callableのメソッドcallは引数なし・返り値(型はCallableに与えたジェネリクスと同じ)あり・throws Exceptionとなる(ExecutorService#submitにCallableを渡して返り値および例外に関して制御する以下の使用例を参照) 
    public static final void main(String[] args) throws InterruptedException {
	int[] arr = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3 };
	ExecutorService es = Executors.newSingleThreadExecutor();
	List<Future<Boolean>> futures = new ArrayList<Future<Boolean>>();
	for (int i = 0; i < 10; ++i) {
		final int idx = i;
		// submitにCallableを渡すことにより、例外の場合も含めてFutureに保存可能
		futures.add(es.submit(() -> {
			if (arr[idx] > 5) {
				throw new Exception(arr[idx] + " is greater than 5");
			}
			return true;
		}));
	}
	int c = 0;
	for (Future<Boolean> f : futures) {
		try {
			if (f.get()) {
				++c;
			}
			System.out.println("valid");
		} catch (ExecutionException e) {
			// 生成したスレッドで発生した例外はExecutionExceptionとしてcatch
			System.out.println(e.getCause());
		}
	}
	es.shutdown();
	System.out.println(c);
}
  16. 同期化：複数のスレッドが並行して進行しているときに処理の順序を制御すること。
  17. java.util.concurrent.CyclicBarrierクラスにより同期化を実現可能：特定の待機ポイント(バリア)に全スレッドが到達するとバリアアクションを行い順序を制御する 
    new CyclicBarrier(int numOfThreads, Runnable barrierAction)
  18. 競合：複数のスレッド間で共有されているインスタンスのフィールド値を、あるスレッドが読み出してから変更するまでの間に、別のスレッドが変更すること
  19. 排他制御：複数のスレッド間で共有されるインスタンスに対し、あるスレッドが処理を実行している間は別のスレッドが処理を加えられないようにすること 
    // someメソッドが複数のスレッドから同時には呼び出されなくなる
public synchronized void some() {
	System.out.println("Java");
}
  20. デッドロック：複数の共有インスタンスに対して排他制御を行った結果、それぞれのインスタンスが連携することで発生(例えば2インスタンスa/bが2スレッドA/B間で共有されている場合、Aがa､bの順に、Bがb､aの順にロックしようとすると、A/Bが互いに相手のリソース開放を永久に待ち続けることになり発生する。回避策：スレッドどうしが同じ順序でリソースをロックするように変更する) 
    public static final void main(String[] args) {
	Deque<Integer> a = new ArrayDeque<Integer>();
	a.addLast(7);
	Deque<Integer> b = new ArrayDeque<Integer>();
	b.addLast(11);

	ExecutorService es = Executors.newFixedThreadPool(2);
	es.submit(() -> {
		synchronized (a) {
			System.out.println("a poll");
			int aFirst = a.pollFirst();
			synchronized (b) {
				System.out.println("b add");
				b.addLast(aFirst);
			}
		}
	});

	es.submit(() -> {
		synchronized (b) {
			System.out.println("b poll");
			int bFirst = b.pollFirst();
			synchronized (a) {
				System.out.println("a add");
				a.addLast(bFirst);
			}
		}
	});
}
  21. ライブロック：2つのスレッドが互いにデッドロックを回避しようとした結果としてロック状態に陥ること
  22. 原子性：一連の処理が完全に終わる、または全く実行されないのどちらかにしかなりえない性質(java.util.concurrent.atomicパッケージのクラスが持つxxxAndGetメソッドにより、読み出しから値の変更までの一連の処理の間に別スレッドが割り込んで処理を行わないようにできる) 
    AtomicInteger n = new AtomicInteger(3);
ExecutorService es = Executors.newFixedThreadPool(2);
es.submit(() -> {
	System.out.println("あ");
	n.addAndGet(100);
});
es.submit(() -> {
	System.out.println("い");
	n.addAndGet(100);
});
Thread.sleep(2000);
// 必ず203を表示
System.out.println(n);

Java SE 11 Gold 自分用メモ(2)

Java 資格

  1. java.util.functionパッケージの関数型インタフェースのうち、名前が「Bi」で始まっているものは、「Bi」を取り去った名前の関数型インタフェースが、引数を2つ受け取り、それらを処理に使用するように変わったもの(命名パターンに関しての例外：UnaryOperatorとBinaryOperator)
  2. 関数型インタフェースjava.util.function.Supplierを使用する例 
    Supplier<List<String>> sup = () -> new ArrayList<String>();
List<String> s = sup.get();
    1行目はメソッド参照を使って以下のように書くことも可能 
    Supplier<List<String>> sup = ArrayList<String>::new;
  3. 関数型インタフェースjava.util.function.Consumerを使用する例 
    Consumer<String> con = (str) -> {
	System.out.println("Consumer is processing");
	System.out.println(str);
	System.out.println("Consumer finished processing");
};
con.accept("Hello, world");
  4. 関数型インタフェースjava.util.function.Predicateを使用する例(predicateは「断定する」の意) 
    Predicate<String> pre = str -> {
	return str.length() > 10;
};
boolean b = pre.test("internationalization");
  5. 関数型インタフェースjava.util.function.Predicateのデフォルトメソッドorとandにより、testメソッドで与えた引数に対して複雑な論理演算を実行可能 
    Predicate<Integer> isMultipleOf7 = n -> n % 7 == 0;
Predicate<Integer> isEven = n -> n % 2 == 0;
Predicate<Integer> isLessThan5 = n -> n > 5;
boolean res = isMultipleOf7.or(isEven.and(isLessThan5)).test(4);
// 7の倍数である || (偶数である && 5未満である)
  6. 関数型インタフェースjava.util.function.Functionを使用する例 
    Function<Long, String> fun = (num) -> num + " yen";
String price = fun.apply(360L);
  7. 関数型インタフェースjava.util.function.FunctionのデフォルトメソッドandThenとcomposeにより、applyメソッドで与えた引数に対して複数の処理をまとめて実行可能(andThenが順次、composeが逆順) 
    Function<Integer, Integer> f = (num) -> num + 1;
Function<Integer, Integer> g = (num) -> num * 2;
System.out.println(f.andThen(g).apply(5));
// 5 + 1 を実行後、 6 * 2 ゆえ12
System.out.println(f.compose(g).apply(5));
// 5 * 2 を実行後、 10 + 1 ゆえ11
  8. java.util.function.UnaryOperatorインタフェースはFunctionを継承したもので、applyメソッドの引数と返り値を同じ型にしたい場合に使用する(BinaryOperatorとBiFunctionの関係も同様で、applyメソッドが受け取る2つの引数と返り値の型が全て同じである場合に使用、ただしBinaryOperatorが受け取る型ジェネリクスは1つだけを指定するので注意)
  9. java.util.Listをはじめとするコレクション型の要素1つ1つに対し、型を変えることのない同一の処理を行いたい場合にUnaryOperatorが役立つ(以下サンプル参照) 
    List<String> l = new ArrayList<String>();
l.add("alice");
l.add("bob");
l.add("charles");
l.replaceAll(str -> str.toUpperCase());
// replaceAllメソッドにUnaryOperatorを渡す
System.out.println(l);
// [ALICE, BOB, CHARLES]

Java SE 11 Gold 自分用メモ(1)

Java 資格

  1. インナークラス・staticインナークラスともに、全アクセス修飾子(public/protected/private)、final、abstract付与可能
  2. ローカルクラス(メソッド内で一時的に定義されるクラス)はfinalとabstractのみ付与可能、匿名クラスはアクセス修飾子、final、abstract、staticいずれも付与不可能
  3. OuterクラスのインナークラスInnerをインスタンス化したい場合の書式は
    new Outer().new Inner()
  4. OuterクラスのstaticインナークラスStaticInnerをインスタンス化したい場合の書式は
    new StaticInner()
  5. Outerクラスが持つメンバーmがprivateであってもインナークラスInnerから参照可能(ただしstaticインナークラスStaticInnerから参照したい場合はmもstaticでなければ参照不可能)
  6. 非staticのインナークラスにはstaticメンバを定義不可能
  7. ローカルクラスがローカル変数を参照する場合、必ずローカルクラスが定義される行よりも上の行でローカル変数が定義されていなければならず、そのローカル変数の値を変更しようとするとコンパイルエラーとなる
  8. 匿名クラスの定義方法：インタフェースを実装したクラスとするか、(具象か抽象かを問わず)別クラスのサブクラスとするかのどちらかの形で実装のみを定義する
  9. 匿名クラスには元クラスに存在しないメソッドを独自に定義することも可能(匿名クラスの内部にコンストラクタを定義することはできない)
  10. 元クラスOriginにはないメソッドmetを持つ匿名クラス型インスタンスへの参照を変数aに持たせたい場合、Java SE 10以降で使用可能となったvarによる型推論を使用し以下のように書く
    var a = new Origin() {
  public void met() {
    System.out.println("yahoo");
  }
};
  11. Java SE 8からはインタフェースにstaticメソッドを定義可能となった(ただし呼び出す時にはそのインタフェース名を指定せねばならず、サブインタフェースや実現クラスの名前では呼び出すことができない)
  12. クラスまたはインタフェースに定義したstaticメソッドはオーバーライド不可能(全く同一のシグネチャであるstaticメソッドに対して@Overrideアノテーションをつけるとコンパイルエラーになり、つけない場合はコンパイル成功する)
  13. インタフェースAのデフォルトメソッドをサブインタフェースや実現クラスでオーバーライドし、オーバーライドしている側がAのデフォルトメソッドを呼び出す場合、サブインタフェースや実現クラスはAと直接の関係を持たねばならず、以下のように書く 
    A.super.defaultMethod()
  14. インタフェースAを実現するとともにクラスBを継承するクラスCがあり、Aのメソッドと全く同一のシグネチャであるメソッドをBが持つ場合、Cのインスタンスがそのメソッドを呼び出すとクラスBでの定義が優先される(Bのソースでメソッドにpublic以外のアクセス修飾子が付いている場合はコンパイルエラーになる)
  15. Java SE 9以降ではインタフェースにもprivateメソッドを定義可能(ただし具象メソッドのみで、defaultをつけずに書く)
  16. 独自の列挙型MyEnumを定義すると、以下の2メソッドがコンパイラにより自動で追加される
    public T[] values();
public T valueOf(String name);
  17. 定義した列挙型が初めて利用される時に各列挙子がインスタンス化され、それ以降列挙子のインスタンス化は二度と行われず常に同じ参照(以下のbはtrue)となる
    MyEnum me = MyEnum.STAR;
boolean b = MyEnum.STAR == me;
  18. 列挙型のtoStringメソッドはデフォルトでは列挙子の名前をそのまま返す
  19. 列挙型にコンストラクタを明示的に定義したい場合は必ずアクセス修飾子privateをつける

 

※列挙型のサンプルコード

public enum Status {
  OK(200), BAD_REQUEST(400), INTERNAL_SERVER_ERROR(500);
  private int code;
  private Status(int code) {
    this.code = code;
  }
  @Override
  public String toString() {
    return String.valueOf(this.code);
  }
}

Eclipse・GitHub間の連携手順(新規プロジェクトの初回プッシュ)

Eclipse 環境構築 Git GitHub 備忘録

いろいろな設定を噛み合わせるのにかなり苦労したため、途中でつまずいた点も併せて備忘録として残しておきます(ここで使っているEclipseのバージョンは2020-12 Rです)。

  1. 新しく作成したGitHubのリモートリポジトリに向けて初回プッシュするまで
  2. Eclipseで認証情報を入力する際の注意点
  3. 参考記事

 

  1. 新しく作成したGitHubのリモートリポジトリに向けて初回プッシュするまで

    新規作成したリモートリポジトリusageLearningに向けて、自分のローカルに作成したワークスペースlearnGit下にある新規プロジェクトsampleを初回プッシュするまでの手順を記載します(各リポジトリやワークスペースの名前、ディレクトリ構造などは適宜自分の環境に適合するように読み替えてください、また、紫色の四角はマスキングです)。

     

    1. 空のリモートリポジトリusageLearningを作成

    2. 自分のローカルにsampleプロジェクトを作成

    3. ローカルでsampleプロジェクトを共用化

      Eclipseの画面で「sampleプロジェクトを右クリック→チーム→プロジェクトの共用」と進み、「Git」を選択して「次へ」を押す。

    4. ローカルリポジトリを作成し共用化完了

      「プロジェクトの親フォルダ内のリポジトリーを使用または作成」にチェックを入れ、sampleプロジェクトをクリックした状態で「リポジトリの作成」(右隣にあるディレクトリ入力欄はデフォルトでOK)「完了」を押す。

    5. Eclipseの画面でアイコンが以下の画像のように変わったことを確認

    6. リモートリポジトリへプッシュ

      EclipseでGitパースペクティブを開き、Gitステージングのタブを開く。「ステージされていない変更」の全ファイルを選択し、「ステージされた変更」へドラッグアンドドロップする。何でもいいのでコミットメッセージを入力し、「コミットおよびプッシュ」を押す。


      「ブランチのプッシュ」ダイアログが出てきたら「ロケーション」の「URI」にGitHubの「Quick setup ---- if you've done this kind of thing before」のところにあったURIをコピペする(「ホスト」「リポジトリ・パス」の欄はその直後に自動入力される)。その後、「認証」の2項目を入力して「プレビュー」を押す。

      ※ここで入力すべき情報についての詳細は「Eclipseで認証情報を入力する際の注意点」を参照。

      さらに2つのダイアログが出てくるが、特に設定値をデフォルトから変更せずに淡々と進めてOK。

    7. GitHubのリモートリポジトリにプッシュされたことを確認

  2. Eclipseで認証情報を入力する際の注意点

    上記vi.の手順において、GitHubの認証情報を入力するように要求されるが、ここで入力しなければならない情報は「GitHubにサインインするユーザIDとパスワード」の組ではないことに注意。正しくは「GitHubにサインインするユーザIDと、以下の手順で取得できる個人アクセストークン」の組(ぶっちゃけここは罠と言っても差し支えないほど混乱を招くポイントだと個人的には思う、まったく別のパラメータを入れるのだから「パスワード」という名前にしないでほしいという思いで溢れかえっているが、新しいバージョンのEclipseでは修正されているのかもしれない)。

    1. GitHubのページ右上端にある自分のユーザアイコンをクリックし、「Settings」を押す
    2. 左カラムの一番下にある「Developer settings」をクリック
    3. 左カラムの一番下にある「Personal access tokens」をクリック
    4. 右上の方にある「Generate new token」をクリックし、有効期限やリモートリポジトリに対して行える操作の権限などを適切に設定して個人アクセストークンを発行(※Noteが空欄になっていると発行できない点に注意、リポジトリ操作が目的ならばSelect scopesではrepoにチェックをつければ基本的にOK)

  3. 参考記事

    1. eclipseユーザーのためのgithub講座

    2. EclipseのGitで「Can’t connect to any repository: https://XXXXX.git (https://XXXXX.git: 未認証) と出た時の解決方法 | よぼろぐ よの冒険記

    3. GitHub – アクセストークンの作成・取得方法とgit操作での使い方 | Howpon[ハウポン]

Java向け競プロライブラリ(ペア)

Java 競プロライブラリ

ソート可能なペアとして入力値を取り扱うと解きやすい問題向けのライブラリです。必要ならば、問題の条件に適合するようにソート条件を変更して使います。

例えば以下の問題で役に立ちます。

AtCoder Beginner Contest 256 D - Union of Interval

2023/09/18追記：HashSetなどで取り扱う際に所望通りの挙動をしなかったためhashCodeメソッドを追加、およびequalsメソッドのキャスト例外握り潰しを廃止

import java.util.Objects;

public final class Pair<F extends Comparable<F>, S extends Comparable<S>>
		implements Comparable<Pair<F, S>> {

	private F first;
	private S second;

	public Pair(F first, S second) {
		this.first = first;
		this.second = second;
	}

	public F getFirst() {
		return first;
	}

	public S getSecond() {
		return second;
	}

	public void setFirst(F first) {
		this.first = first;
	}

	public void setSecond(S second) {
		this.second = second;
	}

	@Override
	public int compareTo(Pair<F, S> o) {
		int t = this.first.compareTo(o.getFirst());

		if (t != 0) {
			return t;
		}

		return this.second.compareTo(o.getSecond());
	}

	@Override
	public boolean equals(Object obj) {
		if (obj == null) {
			return false;
		}

		Pair<F, S> another = (Pair<F, S>) obj;
		return Objects.equals(this.getFirst(), another.getFirst())
				&& Objects.equals(this.getSecond(), another.getSecond());

	}

	@Override
	public int hashCode() {
		int h1 = first.hashCode();
		int h2 = second.hashCode();
		String connected = String.valueOf(h1) + ' ' + String.valueOf(h2);
		return connected.hashCode();
	}

	@Override
	public String toString() {
		return Objects.toString(first) + ' ' + Objects.toString(second);
	}

}