Competitive programming private cheat sheet (Java)

Note. Added sequentially.

Round up the remainder

public static int roundUp(int a, int b) {
    return (a + b - 1) / b;
}

Greatest common divisor

The calculation is performed using the Euclidean algorithm.

reference: Euclidean algorithm and indefinite equation | Beautiful story of high school mathematics

private static long gcd(long a, long b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

For example, if a = 370 b = 273,

Loop a b
1 370 273
2 273 370 % 273 = 117
3 117 273 % 117 = 39
4 39 117 % 39 = 0

When b = 0, return a returns the value of a. That value is the greatest common divisor.

Least common multiple

Calculate using the greatest common divisor.

reference: Two proofs of the property of the product of the greatest common divisor and the least common multiple | Beautiful story of high school mathematics

private static long lcm(long a, long b) {
    return a * b / gcd(a, b);
}

Rotation matrix

double rad = Math.toRadians(60);
double ux = (tx-sx)*Math.cos(rad) - (ty-sy)*Math.sin(rad)+sx;
double uy = (tx-sx)*Math.sin(rad) + (ty-sy)*Math.cos(rad)+sy;
Point u = new Point(ux, uy);

Number of combinations

Number of permutations

Permutation enumeration

Enumeration of combinations

Breadth-first search

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

public class DFS {

    private class Graph {
        List<List<Integer>> graph;
        boolean[] seen;

        public Graph(int n) {
            graph = new ArrayList<>();
            seen = new boolean[n];
            for (int i = 0; i < n; i++) {
                graph.add(new ArrayList());
                seen[i] = false;
            }
        }

        public void add(int from, int to) {
            graph.get(from).add(to);
            graph.get(to).add(from);
        }

        public void search(int v) {
            seen[v] = true;

            for (int next : graph.get(v)) {
                if (seen[next]) continue;
                search(next);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        final int N = sc.nextInt();
        final int M = sc.nextInt();

        Graph graph = new DFS().new Graph(N);

        for (int i = 0; i < M; i++) {
            final int A = Integer.valueOf(sc.next());
            final int B = Integer.valueOf(sc.next());
            graph.add(A, B);
        }

        graph.search(0);
    }
}

Recommended Posts

Competitive programming private cheat sheet (Java)
java competitive programming memo
Java Stream API cheat sheet
C # cheat sheet for Java engineers
javac, jar, java command cheat sheet
[Java] Data type / string class cheat sheet
JMeter cheat sheet
java programming basics
java Generic Programming
Kotlin cheat sheet
[Docker cheat sheet]
Mockito + PowerMock cheat sheet
Constraint programming in Java
Eclipse Collections cheat sheet
Rails Tutorial cheat sheet
Spring Boot2 cheat sheet
Java paid private memo
Java programming basics practice-array
Java programming (class method)
SCSS notation cheat sheet
Java programming (class structure)
All about Java programming
Oreshiki docker-compose cheat sheet
Java encapsulation private public
Docker command cheat sheet
Java Programming Thread Runnable
Java programming (variables and data)
Check Java9 Interface private methods
Java Development Basics-Practice ③ Advanced Programming-
Java programming basics practice-for statement
[Eclipse] Shortcut key cheat sheet
Java programming basics practice-switch statement
[Java] Basic terms in programming
A cheat sheet for Java experienced people to learn Ruby (rails)