java competitive programming memo

I have summarized the code that is often used when programming competitions in java. Compared to C ++, there are fewer people doing competitive programming in java and less information, so I came up with this article. It is assumed that only the standard library will be used.

Basic code

Before the contest starts, the code is prepared as follows.

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		System.out.println();
	}
}

In addition, it is defined as follows.

static int MOD = 1000000007;
static int INF = Integer.MAX_VALUE;

input

Array input

By using Arrays.setAll, you can write more clearly than using the for statement.

int[] a = new int[N];
Arrays.setAll(a, i -> sc.nextInt());

Tree input

The list shows which node has a branch from which node.

List<Integer>[] edge = new ArrayList[N];
for(int i = 0; i < N; i++)
	edge[i] = new ArrayList<>();
for (int i = 0; i < N-1; i++) {
    int a = sc.nextInt()-1;
    int b = sc.nextInt()-1;
    edge[a].add(b);
    edge[b].add(a);
}

Input of a tree with an order on the branches

If you need the order of the branches as information, such as when you need output, make the branch your own class and save it in HashMap. Assumed problem: ABC146D Coloring Edges on Tree

static int N;
static Map<Integer, HashSet<edge>> m = new HashMap<>();
static class edge{
	int to, id;
	edge(int to, int id){
		this.to = to;
		this.id = id;
	}
}
public static void main(String[] args) {
	for(int i = 0; i < N-1; i++) {
		int a = sc.nextInt();
		int b = sc.nextInt();
		if(!m.containsKey(a))
			m.put(a, new HashSet<>());
		m.get(a).add(new edge(b, i));
	}
}

Various methods

bit full search

When N is small (N <about 20), search all 2 ^ N ways.

boolean[] x = new boolean[N];
for(int i = 0; i < 1<<N; i++) {
	for(int j = 0; j < N; j++) {
		if ((1 & i >> j) == 1)
			x[j] = true;
		else
			x[j] = false;
	}
}

Distance from one point in the graph

Using breadth-first search, store the distance from a node v in the array d

int[] d = new int[N+1];
Arrays.fill(d, INF);
d[v] = 0;
Queue<Integer> q = new ArrayDeque<>();
for(int i : edge.get(v)) {
	q.offer(i);
	d[i] = 1;
}
while(q.size() > 0) {
	int x = q.poll();
	for(int i : edge.get(x)) {
		if(d[i] > d[x] + 1) {
			d[i] = d[x] + 1;
			q.offer(i);
		}
	}
}

Various methods

Maximum / minimum value of array

You can get it with Arrays without turning the for statement.

Arrays.stream([Array name]).min().getAsInt()
Arrays.stream([Array name]).max().getAsInt()

Least common multiple

Express the Euclidean algorithm with a recursive function.

public static int gcd(int a, int b) {
		return b == 0 ? a: gcd(b, a % b);
}

Greatest common divisor

Use the least common multiple.

public static int lcm(int a, int b) {
		return a / gcd(a, b) * b;
}

Factorial n!

It is the basis of recursive functions.

public static long factorial(long n){
	  return n <= 0 ? 1 : n * factorial(n-1);
}	

Combination nCr

Consider the case of outputting the remainder divided by 10 ^ 9 + 7 when finding the combination. When N is small (about <2000), it can be calculated by dynamic programming, considering Pascal's triangle.

int MAX = 2000;
long[][] com = new long[MAX][MAX];
for(int i = 0; i < MAX; i++)
	com[i][0] = 1;
for(int i = 1; i < MAX; i++) {
	for(int j = 1; j <= i; j++) {
		com[i][j] = com[i-1][j-1] + com[i-1][j];
		com[i][j] %= MOD;
	}
}

If N is large, it is necessary to find the inverse element. Calculation is performed by calling COMinit () in the main method, and nCr can be obtained by combination (n, r).

public static int MOD = 1_000_000_007;
public static int MAX = 100000;
public static long[] fac = new long[MAX];
public static long[] finv = new long[MAX];
public static long[] inv = new long[MAX];
	
public static void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for(int i = 2; i < MAX; i++) {
		fac[i] = fac[i-1] * i % MOD;
		inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
		finv[i] = finv[i-1] * inv[i] % MOD;
	}
}

public static long combination(int n, int k){
	if(n < k || n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}
public static void main(String[] args) {
	COMinit();
	System.out.println(combination(2000, 3));
}

Full permutation output

Output all permutations according to N !.

static List<String> z;
	
public static void permutation(String q, String ans){
	if(q.length() <= 1) {
		z.add(ans + q);
	 }
	 else {
	    	for (int i = 0; i < q.length(); i++) {
	    		permutation(q.substring(0, i) + q.substring(i + 1),
	    		ans + q.charAt(i));
	        }
	 }
}
public static void main(String[] args) {
	z = new ArrayList<>();
	permutation("12345","");
	for(int i = 0; i < z.size(); i++)
		System.out.println(z.get(i));
}

Binary search

In java, binary search is possible with Arrays.binarySearch. Arrays.binarySearch returns the position if the array contains a key, otherwise it returns the position where the key should be inserted. Since there are no methods such as lower_bound and upper_bound in C ++, the number cannot be counted by binary search. So I implemented it myself.

public static int lowerbound(int[] a, int key) {
	if(a[a.length-1] < key)
		return a.length;
	int lb = 0, ub = a.length-1, mid;
	do {
		mid = (ub+lb)/2;
		if(a[mid] < key)
			lb = mid + 1;
		else
			ub = mid;
	}while(lb < ub);
	return ub;
}
public static int upperbound(int[] a, int key) {
	if(a[a.length-1] <= key)
		return a.length;
	int lb = 0, ub = a.length-1, mid;
	do {
		mid = (ub+lb)/2;
		if(a[mid] <= key)
			lb = mid + 1;
		else
			ub = mid;
	}while(lb < ub);
	return ub;
}
public static int count(int[] a, int key) {
	return upperbound(a, key) - lowerbound(a, key);
}

Factorization

A method that factorizes and saves in HashMap.

static Map<Integer, Integer> fact = new HashMap<>();
public static void factorization(int N){
	for(int i = 2; i <= Math.sqrt(N); i ++) {
		if(N % i == 0) {
			int n = 0;
			while(N % i == 0) {
				N /= i;
				n++;
			}
			fact.put(i, n);
		}
	}
	if(N > 1)
		fact.put(N, 1);
}

Postscript

This article is in the process of being edited. I will update it from time to time.

Recommended Posts

java competitive programming memo
Java memo
Competitive programming private cheat sheet (Java)
java anything memo
Java Silver memo
java programming basics
Java SE 7 memo
java anything memo 2
Java specification memo
Java pattern memo
Java development environment memo
java basic knowledge memo
Java learning memo (method)
Java Kuche Day memo
[Java ~ Method ~] Study memo (5)
java se 8 programmer Ⅰ memo
Java paid private memo
Java programming basics practice-array
[Java ~ Array ~] Study memo 4
Java learning memo (basic)
(Memo) Java for statement
Java lambda expression [memo]
Java learning memo (interface)
Java programming (class structure)
All about Java programming
Java learning memo (inheritance)
[Memo] Java Linked List
Java Programming Thread Runnable
Java (WebSphere Application Server) memo [1]
[Java] Variable name naming memo
Java memo (standard class) substring
Java learning memo (data type)
Amazing Java programming (let's stop)
Java memo (standard class) length
Java programming (variables and data)
Java Silver Study Method Memo
[Java ~ Boolean value ~] Study memo (2)
Create a java method [Memo] [java11]
Java Silver exam preparation memo
Java Development Basics-Practice ③ Advanced Programming-
Java programming basics practice-for statement
Java learning memo (logical operator)
Java learning memo (abstract class)
[Java] Date Related Term Memo
Java study memo 2 with Progate
Java programming basics practice-switch statement
What are Java metrics? _Memo_20200818
Java HashMap, entrySet [Personal memo]
[Java] Basic terms in programming
A memo to start Java programming with VS Code (2020-04 version)
[Eclipse Java] Development environment setting memo
Java learning memo (creating an array)
JCA (Java Cryptography Architecture) Usage Memo
[Java] Memo for naming class names
Java Functional Programming Exercise Book --zipWith-
[Study session memo] Java Day Tokyo 2017
Java learning memo (while statement, do-while statement)
Java
From Java to VB.NET-Writing Contrast Memo-
Java beginner's stumbling block [memo writing]
Java