半年ぐらい前に水色になって満足したのでしばらく競プロから離れていたのですが、5/19(日)のABCから~2000Ratedになるそうで、これを機に復帰しようかなと思い立ったので、当時は解けていた400点問題頻出のアルゴリズムを復習してテンプレート化しました。各アルゴリズムの詳細は他ページに譲って、計算量と使い所とテンプレートの説明に特化します。星は頻出度(独断)を表しています。
数学的な計算
GCD(最大公約数) ★★★
これは400点未満の問題でもバシバシ出るんですけど、一応。O(log(min(num1,num2)))で最大公約数を算出できます。ちなみにですけどnum1*num2/gcdで最小公倍数を算出できます。
//return gcd O(logN)
public static int gcd(int num1,int num2) {
if(num2==0) return num1;
else return gcd(num2,num1%num2);
}
nCk(mod M)(組み合わせ) ★★
特に10^9+7のmod処理が面倒だったのでテンプレート化しました。ついでに累乗計算も。累乗計算は底をa/指数をbとしてO(logb)、nCk(mod M)はO(min(k,n-k)*logM)の計算量です。
//return nCk mod M (M must be prime number) O(min(k,n-k)*logM)
public static int nCk(int n,int k,int M) {
long ret = 1;
int min = Math.min(k, n-k);
for(int i=1;i<=min;i++) {
ret = (ret * pow(i,M-2,M)) % M;
}
for(int i=n-min+1;i<=n;i++) {
ret = (ret * i) % M;
}
return (int)ret;
}
//return a^b mod M O(logB)
public static long pow(long a,long b,int M) {
long ret = 1;
long tmp = a;
while(b>0) {
if((b&1)==1) ret = (ret * tmp) % M;
tmp = (tmp * tmp) % M;
b = b>>1;
}
return ret;
}
便利なデータ構造
Union-Find ★★★
グルーピングを管理する問題では死ぬほど出てきます。ただ、これそのままの形で解答することはほとんどなく、問題に沿った形に中のデータ構造を変える必要があるケースがほとんどです。例えばグループのノード数を保持するよう変形するとかです。その辺の丁度良い応用力が問いやすいので400点でよく出題されるのでしょう。親ノードの抽出とグループの結合をどちらもO(logN)より高速な時間で実行できます。
//return root node idx O(a(N)) ( O(1)<O(a(N))<O(logN) )
public static int find(int[] tree,int idx) {
if(tree[idx]==idx) return idx;
else return tree[idx] = find(tree,tree[idx]);
}
//union idx2 tree to idx1 tree O(a(N))
public static void union(int[] tree,int idx1,int idx2) {
int root1 = find(tree,idx1);
int root2 = find(tree,idx2);
tree[root2] = root1;
}
BinaryIndexedTree ★
部分和の取り出し/配列要素への加算がそれぞれO(logN)でできるデータ構造です。部分和の取り出しだけだったら普通に累積和でいいんですけど、合間に配列要素への加算操作が必要になってくる場合にはこっちの方が適しています。まああまり見かけないですけど。
//add value at idx on bit O(logN)
public static void add(int[] bit,int idx,int value) {
for(int i=idx;i<bit.length;i+=(i&-i)) bit[i] += value;
}
//return sum [1,idx] O(logN)
public static int sum(int[] bit,int idx) {
int ret = 0;
for(int i=idx;i>0;i-=(i&-i)) ret += bit[i];
return ret;
}
その他（PriorityQueue） ★★★
後はJavaの標準ライブラリでどうにかなると思いますけど、その中でよく使うのは
- PriorityQueue
ですかね。要素の追加と最大要素/最小要素の抽出をそれぞれ0(logN)時間で実行してくれる便利なやつです。ダイクストラでも利用されています。ただ、デフォルトでは数値型の最小値取得しか受け付けていないので、最大値取得や数値型以外の要素を突っ込む場合には自分でComparatorを定義してあげましょう。サンプルはint配列を突っ込んで0番目が最大の要素を取得するようComparator定義したPriorityQueueです。
PriorityQueue<int[]> p_que = new PriorityQueue<>((array1,array2)->-array1[0]+array2[0]);
最短経路問題
ダイクストラ ★★
最短経路問題でお馴染みのやつです。計算量はノード数をV、辺数をEとしてO(ElogV)です。ただし負の辺があるとうまく機能しないので、その場合はベルマンフォードを使います。
//return min distance from start to end O(ElogV) (negative cost is prohibited)
//edge is int[3] array {from,to,cost}
//edges is edge list from specific node
//all_edges is Map<from node number,edges>
public static int dijkstra(Map<Integer,List<int[]>> all_edges,int start,int end,int max_node_number) {
int[] distance = new int[max_node_number+1];
for(int i=0;i<distance.length;i++) distance[i] = -1;
PriorityQueue<int[]> p_que = new PriorityQueue<>((a,b)->((distance[a[0]]+a[2])-(distance[b[0]]+b[2])));
distance[start] = 0;
List<int[]> edges = all_edges.get(start);
for(int i=0;i<edges.size();i++) p_que.add(edges.get(i));
while(distance[end]<0) {
int[] nearest_edge = p_que.poll();
if(distance[nearest_edge[1]]<0) {
distance[nearest_edge[1]] = distance[nearest_edge[0]] + nearest_edge[2];
if(all_edges.containsKey(nearest_edge[1])) {
edges = all_edges.get(nearest_edge[1]);
for(int i=0;i<edges.size();i++) {
int[] edge = edges.get(i);
if(distance[edge[1]]<0) p_que.add(edge);
}
}
}
}
return distance[end];
}
ベルマンフォード ★★
最短経路問題で負辺があるケースで有効なアルゴリズムです。計算量はO(EV)と、ダイクストラよりやや劣ります。ただ、負の閉路の検出など、ダイクストラではできないことも一部できたりします。負辺があったり、ダイクストラにしてはノード数や辺数の制約がゆるいな？と思ったらこっちのパターンかもしれません。
//return min distance from start to end O(EV) (negative cost is possible)
//edge is int[3] array {from,to,cost}
//edges is edge list from specific node
//all_edges is Map<from node number,edges>
public static int bellmanFord(Map<Integer,List<int[]>> all_edges,int start,int end,int max_node_number) {
int[] distance = new int[max_node_number+1];
int INF = Integer.MAX_VALUE;
for(int i=0;i<distance.length;i++) {
distance[i] = INF;
}
distance[start] = 0;
int counter = all_edges.size();
while(counter>0) {
boolean updated = false;
for(List<int[]> edges: all_edges.values()) {
if(distance[edges.get(0)[0]]==INF) continue;
for(int[] edge: edges) {
if(distance[edge[0]]+edge[2] < distance[edge[1]]) {
distance[edge[1]] = distance[edge[0]]+edge[2];
updated = true;
}
}
}
if(!updated) break;
counter--;
}
return counter==0?Integer.MIN_VALUE:distance[end];
}
ワーシャルフロイド ★
最短経路問題で全ノード間の最短距離が必要な場合に有効です。計算量はノード数をVとしてO(V^3)と重めなので、ノード数の制約条件が100以下の時ぐらいしか使えないですが、逆に知ってれば解ける場合がほとんどなので覚えておいて損はないです。
//return new distance matrix O(logV^3)
public static int[][] warshallFloyd(int[][] distance){
int node_number = distance.length;
int[][] min_distance = new int[node_number][node_number];
for(int i=0;i<node_number;i++) {
for(int j=0;j<node_number;j++) {
min_distance[i][j] = distance[i][j];
}
}
for(int via=0;via<node_number;via++) {
for(int from=0;from<node_number;from++) {
for(int to=0;to<node_number;to++) {
min_distance[from][to] = Math.min(min_distance[from][to], min_distance[from][via]+min_distance[via][to]);
}
}
}
return min_distance;
}
最小全域木問題
クラスカル法 ★★
最小全域木の問題の時によく使います。計算量はノード数をV、辺数をEとしてO(ElogV)です。ノードの結合状態（同じグループに属しているか）を判定するのにUnion-Findを使っています。
//return min cost for union all nodes O(ElogV)
//edge is int[3] array {node1,node2,cost}
//edges is edge list
public static int kruskal(List<int[]> edges,int max_node_number) {
edges.sort((a,b)->(a[2]-b[2]));
int[] uft = new int[max_node_number+1];
for(int i=0;i<uft.length;i++) {
uft[i] = i;
}
int cost_sum = 0;
for(int[] edge: edges) {
if(find(uft,edge[0])!=find(uft,edge[1])) {
union(uft,edge[0],edge[1]);
cost_sum += edge[2];
}
}
return cost_sum;
}
public static int find(int[] tree,int idx) {
if(tree[idx]==idx) return idx;
else return tree[idx] = find(tree,tree[idx]);
}
public static void union(int[] tree,int idx1,int idx2) {
int root1 = find(tree,idx1);
int root2 = find(tree,idx2);
tree[root2] = root1;
}
その他頻出トピック
アルゴリズムをテンプレート化できない、けどめちゃめちゃ出てくるトピックはこんな感じですかね。
- 累積和
- DP（動的計画法）
- bit演算（bit全探索、xor問題）
テンプレート化できないが故に応用力/その場での実装力が測りやすいため、よく出てくるんでしょう。調べれば関連記事がいっぱい出てくると思うので、~2000RatedABCに向け精進しましょう。