パッケージ library

クラス Utility

java.lang.Object

library.Utility

public class Utility
extends java.lang.Object

基本のライブラリ

ネストされたクラスの概要

ネストされたクラス

修飾子とタイプ	クラス	説明
private static class	Utility.FastScanner	java.util.Scanner の高速版
private static class	Utility.ListMap<K,V>
private static class	Utility.Pair<T1,T2>
private static class	Utility.Permutation	[0,N)の順列を求める action で結果を処理する O(N!)

フィールドの概要

フィールド

修飾子とタイプ	フィールド	説明
private static java.util.Comparator<java.lang.Long>	lowerBoundComparator	指定した値以上の要素が初めて出現する場所を取得するComparator
private static java.util.Comparator<java.lang.Long>	upperBoundComparator	指定した値より大きい要素が初めて出現する場所を取得するComparator

コンストラクタの概要

コンストラクタ

コンストラクタ	説明
Utility()

メソッドの概要

修飾子とタイプ	メソッド	説明
private static int	calcLCSLength(java.lang.String a, java.lang.String b)	Hunt–Szymanski algorithm O(n log n) で最長共通文字列の長さを計算する
private static long	euclideanAlgorithm(long a, long b)	ユークリッドの互除法
private static long	floorSum(long n, long m, long a, long b)	IntStream.range(0, n) .map(i -> (a * i + b) / m) .sum() を O(log a + log m) で計算できる
private static long	iterativePow(long a, long b)	繰り返し二乗法
private static long	iterativePow(long a, long b, long result)
private static java.util.Map<java.lang.Integer,java.lang.Integer>	primeFactorization(int n)	素因数分解
private static java.util.Map<java.lang.Integer,java.lang.Integer>	primeFactorizationRecursive(int n, int i)	10^9でやるとスタックオーバーフローする
private static java.util.List<java.lang.Integer>	sieveOfEratosthenes(int number)	エラトステネスの篩

クラスから継承されたメソッド java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

フィールドの詳細

lowerBoundComparator

private static final java.util.Comparator<java.lang.Long> lowerBoundComparator

指定した値以上の要素が初めて出現する場所を取得するComparator

upperBoundComparator

private static final java.util.Comparator<java.lang.Long> upperBoundComparator

指定した値より大きい要素が初めて出現する場所を取得するComparator

コンストラクタの詳細

Utility

public Utility()

メソッドの詳細

euclideanAlgorithm

private static long euclideanAlgorithm(long a,
                                       long b)

ユークリッドの互除法

パラメータ:

a - 63bitまでの非負整数

b - 63bitまでの非負整数

戻り値:

最大公約数

primeFactorization

private static java.util.Map<java.lang.Integer,java.lang.Integer> primeFactorization(int n)

素因数分解

パラメータ:

n - 素因数分解したい31bitまでの非負整数

戻り値:

引数を構成している素数をキー，掛けられる回数をバリューとしたマップ

primeFactorizationRecursive

private static java.util.Map<java.lang.Integer,java.lang.Integer> primeFactorizationRecursive(int n,
                                                                                                    int i)

10^9でやるとスタックオーバーフローする

sieveOfEratosthenes

private static java.util.List<java.lang.Integer> sieveOfEratosthenes(int number)

エラトステネスの篩

与えられた整数以下の素数のリストを O(nloglogn) で返す．

パラメータ:

number - 上限

戻り値:

条件を満たす素数のリスト

iterativePow

private static long iterativePow(long a,
                                 long b)

繰り返し二乗法

パラメータ:

a - 基数

b - べき数

戻り値:

基数の冪乗

iterativePow

private static long iterativePow(long a,
                                 long b,
                                 long result)

floorSum

private static long floorSum(long n,
                             long m,
                             long a,
                             long b)

IntStream.range(0, n) .map(i -> (a * i + b) / m) .sum() を O(log a + log m) で計算できる

関連項目:

Floor Sum (ACL Practice Contest C)

calcLCSLength

private static int calcLCSLength(java.lang.String a,
                                 java.lang.String b)

Hunt–Szymanski algorithm O(n log n) で最長共通文字列の長さを計算する

パラメータ:

a - 文字列

b - 文字列

戻り値:

最長共通部分文字列の長さ

関連項目:

最長共通部分列（ O( (n+r) log n) ）