Overall Editorial by cirno3153
このユーザー解説はJava/Kotlinにおける実装例を紹介するものとなっています。
A問題 - World Cup
\(Y\) から順に数字を増やしていき、 \(4\) で割った余りが \(2\) になった値を出力すると答えが求まります。
Javaの実装例
import java.util.Scanner;
import static java.lang.System.out;
public class Main {
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
int Y = sc.nextInt();
while(Y % 4 != 2) ++ Y;
out.println(Y);
}
}
}
Kotlinの実装例
import java.util.Scanner
fun main() {
Scanner(System.`in`).use { sc ->
var Y = sc.nextInt()
while(Y % 4 != 2) ++ Y
println(Y)
}
}
あるいは、直接計算で求めることもできます。
答えから \(2\) を引いた値は、 \(Y-2\) 以上の最小の \(4\) の倍数を求める問題となっています。
\(Y-2\) 以上の最小の \(4\) の倍数は \(Y-2+(4-1)=Y+1\) 以下の最大の \(4\) の倍数であることから、これを求めれば良いです。
ところで、 \(Y+1\) 以下の最大の \(4\) の倍数は、ある整数 \(x\) を用いて \(4x\) と表すことができます。
また、 \(x = \lfloor \frac{Y+1}{4} \rfloor\) であり、Java/Kotlinでは正整数の除算は切り捨て除算であることからこれは簡単に計算できます。
従って、求める値は \(4 \lfloor \frac{Y+1}{4} \rfloor + 2\) です。
Javaの実装例
import java.util.Scanner;
import static java.lang.System.out;
public class Main {
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
int Y = sc.nextInt();
out.println((Y + 1) / 4 * 4 + 2);
}
}
}
Kotlinの実装例
import java.util.Scanner
fun main() {
Scanner(System.`in`).use { sc ->
val Y = sc.nextInt()
println((Y + 1) / 4 * 4 + 2)
}
}
B問題 - Triangle (Easier)
明らかにABC258-G Triangleの制約弱化版なので、ここからACコードを貼ることでも正答できます。 とはいえ、それでは解説にならないので、実装方法を解説します。
まず、 \(a, b, c\) を全て決め打っても計算量は \(\Theta (N^3)\) で、これは十分に高速です。
従って、 \(a, b, c\) を全て決め打った時に、この組が条件を満たすかを高速に調べたいです。
これは、 \(\{a, b\}, \{b, c\}, \{a, c\}\) という三つの辺がどれも存在するかが分かれば良いです。
辺 \(\{a, b\}\) が存在するかを調べる方法は幾つかありますが、その一つとしてはboolean型の二次元配列graph[u][v]を用意しておき、graph[u][v]には辺 \(\{u, v\}\) が存在するか否かを格納すると良いです。
配列graphの宣言で \(O(N^2)\) 、辺の追加に \(O(M)\) 、判定に \(O(1)\) となり、全体の計算量は \(O(N^3+M)\) となります。
Javaの実装例
import java.util.Scanner;
import static java.lang.System.out;
public class Main {
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
int N = sc.nextInt(), M = sc.nextInt();
boolean[][] graph = new boolean[N][N];
for (int i = 0;i < M;++ i) {
int U = sc.nextInt() - 1, V = sc.nextInt() - 1; // 0-indexedに直す
graph[U][V] = graph[V][U] = true; // 無向辺なので、U-VとV-Uの両方の辺を追加
}
int ans = 0; // 答えを格納
for (int c = 0;c < N;++ c) {
for (int b = 0;b < c;++ b) {
for (int a = 0;a < b;++ a) {
if (graph[a][b] && graph[b][c] && graph[a][c]) ++ ans;
}
}
}
out.println(ans);
}
}
}
Kotlinの実装例
import java.util.Scanner
fun main() {
Scanner(System.`in`).use { sc ->
val N = sc.nextInt()
val graph = Array(N) {BooleanArray(N)}
val M = sc.nextInt()
repeat(M) {
val U = sc.nextInt() - 1 // 0-indexedに直す
val V = sc.nextInt() - 1 // 0-indexedに直す
graph[U][V] = true
graph[V][U] = true // 無向辺なので、U-VとV-Uの両方の辺を追加
}
var ans = 0 // 答えを格納
for (c in 0 until N) {
for (b in 0 until c) {
for (a in 0 until b) {
if (graph[a][b] && graph[b][c] && graph[a][c]) ++ ans
}
}
}
println(ans)
}
}
おまけとして、計算量をもっと改善する方法も書いておきます。
さらなる高速化
Triangleの想定解
\(a\) と \(b\) のみを決め打つことを考えます。
この時、頂点 \(v\) に隣接する頂点を \(N(v)\) とすると、求めるものは \(a\) と \(b\) の両方に接する頂点 \(c\) 、つまり \(N(a) \cap N(b)\) です。
\(N(v)\) をbitsetを用いて表すことにすると、 \(N(a) \cap N(b)\) は \(O(\frac{N}{w})\) で求めることができます(ただし \(w\) はワードサイズ、 \(64\) と仮定して良い)。
従って、計算量は \(O(\frac{N^3}{w} + M)\) となります。
Javaの実装例
import java.util.BitSet;
import java.util.Scanner;
import static java.lang.System.out;
public class Main {
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
int N = sc.nextInt(), M = sc.nextInt();
BitSet[] graph = new BitSet[N]; // graph[v]は、vに隣接する頂点の集合
for (int i = 0;i < N;++ i) graph[i] = new BitSet(N);
for (int i = 0;i < M;++ i) {
int U = sc.nextInt() - 1, V = sc.nextInt() - 1; // 0-indexedに直す
graph[U].set(V);
graph[V].set(U); // 無向辺なので、U-VとV-Uの両方の辺を追加
}
int ans = 0; // 答えを格納
for (int c = 0;c < N;++ c) {
for (int b = 0;b < c;++ b) {
if (!graph[b].get(c)) continue; // bとcが隣接していないなら条件を満たさない
BitSet a = graph[b].get(0, b); // aの値域は[0, b)なので最初に縮めておく
a.and(graph[c]); // これでaはbとcの両方に隣接する頂点であってb未満のものになっている
ans += a.cardinality();
}
}
out.println(ans);
}
}
}
Kotlinの実装例
import java.util.BitSet
import java.util.Scanner
fun main() {
Scanner(System.`in`).use { sc ->
val N = sc.nextInt()
val graph = Array(N) { BitSet(N) }
val M = sc.nextInt()
repeat(M) {
val U = sc.nextInt() - 1 // 0-indexedに直す
val V = sc.nextInt() - 1 // 0-indexedに直す
graph[U][V] = true
graph[V][U] = true // 無向辺なので、U-VとV-Uの両方の辺を追加
}
var ans = 0 // 答えを格納
for (c in 0 until N) {
for (b in 0 until c) {
if (!graph[b][c]) continue // bとcが隣接していないなら条件を満たさない
val a = graph[b][0, b] // aの値域は[0, b)なので最初に縮めておく
a.and(graph[c]) // これでaはbとcの両方に隣接する頂点であってb未満のものになっている
ans += a.cardinality()
}
}
println(ans)
}
}
計算量だけで見た最速
グラフの隣接行列を \(G\) とします。
この時、 \((G^n)_{u, v}\) は頂点 \(u\) から頂点 \(v\) に向かう長さ \(n\) のパスの総数になることが証明できます。
実際に、数学的帰納法を用いて証明してみましょう。
\(G^1\) は隣接行列であり、これが仮定を満たすことは明らかです。
\(G^k\) が仮定を満たすとき、 \(G^{k+1}\) について考えてみましょう。
頂点 \(u\) から頂点 \(v\) に向かう長さ \(k+1\) のパスであって、頂点 \(v\) の直前に頂点 \(t\) を通ったものを考えます。
数学的帰納法の仮定より、このようなパスの総数は \((G^k)_{u, t}\ G_{t, v}\) であることが分かります。
従って、これを全ての \(t\) に対して求めれば良いですが、 \(G_{u, v} = \sum_{t} (G^k)_{u, t}\ G_{t, v}\) というのはすなわち \(G^{k+1}\) にほかなりません。
従って、数学的帰納法より \((G^n)_{u, v}\) は頂点 \(u\) から頂点 \(v\) に向かう長さ \(n\) のパスの総数になることが示せました。
さて、三角形というのは任意の頂点 \(u\) に対して、長さ \(3\) のパスであって頂点 \(u\) に戻るようなものです。
従って、このようなものは \(\mathrm{tr}(G^3)\) で数え上げることができます。
長さ \(n\) の正方行列積の計算量を \(M(n)\) とすると、 計算量は \(O(M(n))\) です。ここで \(M(n)\) はLe Gallのアルゴリズムなどを用いて \(O(N^{2.3728679})\) などで求めることができます。
なお現実的には遅いので、まともに実用的なのはStrassen法の \(O(N^{2.8073550})\) でしょうか。
三角形列挙
頂点 \(v\) について、 \(v\) を含む三角形の個数は最大でも \(\min(\frac{\mathrm{d}(v)^2}{2}, M)\) です。
従って、全ての三角形の個数は \(\sum_{v} \min(\frac{\mathrm{d}(v)^2}{2}, M) \leq M \sqrt{2M}\) で上から抑えられます。
実際に、 \(O(N + M \sqrt{M})\) で列挙できるので、この計算量で求めることができます。(参考)
Javaの実装例
import java.util.ArrayList;
import java.util.Scanner;
import static java.lang.System.out;
public class Main {
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
int N = sc.nextInt(), M = sc.nextInt();
ArrayList<ArrayList<Integer>> graph = new ArrayList<>(N); // 問題文で与えられたグラフに対して各辺に適当に向きを付けてDAGにしたもの
for (int i = 0;i < N;++ i) graph.add(new ArrayList<>());
{
int[][] edges = new int[M][2];
int[] degree = new int[N];
for (int i = 0;i < M;++ i) {
edges[i][0] = sc.nextInt() - 1;
edges[i][1] = sc.nextInt() - 1;
++ degree[edges[i][0]];
++ degree[edges[i][1]];
}
for (int[] edge : edges) { // 次数の小さい方から大きい方にのみ辺を付けたDAGにする
if (degree[edge[0]] <= degree[edge[1]]) graph.get(edge[0]).add(edge[1]); // この方法だと各辺から出る辺の個数が高々sqrt(2M)個になることに注意
else graph.get(edge[1]).add(edge[0]);
}
}
int ans = 0; // 答えを格納
for (int a = 0;a < N;++ a) {
boolean[] find = new boolean[N]; // 頂点aと直接つながる頂点の集合
for (int c : graph.get(a)) find[c] = true;
for (int b : graph.get(a)) { // この時点で、abは辺列挙だから計算量O(N+M)なことに注意
/*
三角形abcを列挙したい
ここで、元のグラフに適当に向き付けをしてDAGになったグラフで三角形を改めて列挙することを考える
DAGではその順番で不等号≦が定義できるので、a≦b≦cだけを数えるとして問題ない
この時、辺abを順番に見ていくと、あるcであって辺acも辺bcも存在するものだけ数え上げれば良いことが分かる
これは、頂点aから出る頂点の集合と頂点bから出る頂点の集合の共通集合に等しい
ところで、頂点aから出る頂点の集合は先にfind配列とかに持たせておくとする
すると、頂点bから出る頂点を一つ一つ見て、findに入っていれば三角形カウントすれば良い
各頂点から出る頂点の個数は高々sqrt(2M)個なので計算量も保てて大丈夫
*/
for (int c : graph.get(b)) if (find[c]) ++ ans; // O(sqrt(M))
}
}
out.println(ans);
}
}
}
Kotlinの実装例
import java.util.Scanner
fun main() {
Scanner(System.`in`).use { sc ->
val N = sc.nextInt()
val graph = sc.nextInt().let { M -> // 問題文で与えられたグラフに対して各辺に適当に向きを付けてDAGにしたもの
val edges = Array(M) {(sc.nextInt() - 1) to (sc.nextInt() - 1)}
val degree = IntArray(N).apply {
for ((u, v) in edges) {
++ this[u]
++ this[v]
}
}
Array(N) {mutableListOf<Int>()}.apply {// 次数の小さい方から大きい方にのみ辺を付けたDAG
for ((u, v) in edges) { // この方法だと各辺から出る辺の個数が高々sqrt(2M)個になることに注意
if (degree[u] <= degree[v]) this[u].add(v)
else this[v].add(u)
}
}
}
var ans = 0 // 答えを格納
for (a in 0 until N) {
val find = BooleanArray(N) // 頂点aと直接つながる頂点の集合
for (c in graph[a]) find[c] = true
for (b in graph[a]) { // この時点で、abは辺列挙だから計算量O(N+M)なことに注意
/*
三角形abcを列挙したい
ここで、元のグラフに適当に向き付けをしてDAGになったグラフで三角形を改めて列挙することを考える
DAGではその順番で不等号≦が定義できるので、a≦b≦cだけを数えるとして問題ない
この時、辺abを順番に見ていくと、あるcであって辺acも辺bcも存在するものだけ数え上げれば良いことが分かる
これは、頂点aから出る頂点の集合と頂点bから出る頂点の集合の共通集合に等しい
ところで、頂点aから出る頂点の集合は先にfind配列とかに持たせておくとする
すると、頂点bから出る頂点を一つ一つ見て、findに入っていれば三角形カウントすれば良い
各頂点から出る頂点の個数は高々sqrt(2M)個なので計算量も保てて大丈夫
*/
for (c in graph[b]) if (find[c]) ++ ans // O(sqrt(M))
}
}
println(ans)
}
}
C問題 - Min Max Pair
複数の条件を満たすものの数え上げでは、より複雑な条件のものが成り立っている状態を仮定する方法が有効です。
ここでは、 \(\min(a_i, a_j)=i\) が成り立っていると仮定してみましょう。
この時、 \(a_i = i\) 、あるいは \(a_j = i\) のどちらかが成り立っています。
仮に、 \(a_i = i\) だとします。 この時、 \(\max(a_i, a_j) = a_j = j\) であることも分かります。
つまり、 \(a_x = x\) であるような \(x\) の個数を \(n\) とすると、そのようなもののうち任意に二つ選べば条件を満たすので答えは \(_nC_2 = \frac{n(n-1)}{2}\) 通りです。
次に、 \(a_j = i\) だとします。 この時、 \(\max(a_i, a_j) = a_i = j\) であることも分かります。
つまり、 \(i\) を決め打ってあげると、 \(a_i = j\) なので \(i < a_i\) かつ \(a_{a_i} = i\) であるかを確認すれば十分であることが分かります。
どちらの場合でも計算量は \(O(N)\) なので、 \(O(N)\) でこの問題が解けました。
Javaの実装例
import java.util.Scanner;
import static java.lang.System.out;
public class Main {
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
int N = sc.nextInt();
int[] a = new int[N];
for (int i = 0;i < N;++ i) a[i] = sc.nextInt() - 1; // 0-indexedに直す
long ans = 0;
int loop = 0; // a_i = iなるiの個数
for (int i = 0;i < N;++ i) {
if (a[i] == i) {
ans += loop;
++ loop;
} else if (i < a[i] && a[a[i]] == i) ++ ans;
}
out.println(ans);
}
}
}
Kotlinの実装例
import java.util.Scanner
fun main() {
Scanner(System.`in`).use { sc ->
val N = sc.nextInt()
val a = IntArray(N) {sc.nextInt() - 1}
var ans = 0L
var loop = 0 // a_i = iなるiの個数
for (i in 0 until N) {
if (a[i] == i) {
ans += loop
++ loop
} else if (i < a[i] && a[a[i]] == i) ++ ans
}
println(ans)
}
}
D問題 - I Hate Non-integer Number
平均値が整数であるということは、総和が要素数の倍数であるということです。 そこで、次のような状態を持つ動的計画法を考えることができます。
\(f(i, j, k, l)\) を、 \(1\) 番目から \(i\) 番目の要素までのうち \(j\) 個の要素を選び、総和を \(k\) で割った余りが \(l\) であるようなものの個数と定めます。 この時、答えは \(\sum_{i=1, N} f(N, i, i, 0)\) です。
まずは初項を考えます。 \(i=0\) のとき、選んだ要素数は \(0\) 個であり、総和が \(0\) であることは明らかです。 従って、 \(j=0, l=0\) ならば \(1\) 、それ以外は \(0\) となります。
次に遷移を、配る方向で考えます。
\(f(i, j, k, l)\) が分かっている時、次の遷移としては \(a_i\) を選ぶか選ばないかが挙げられます。
\(a_i\) を選ぶならば \(f(i+1. j+1, k, l + a_i \bmod k)\) に、 \(a_i\) を選ばないならば \(f(i+1, j, k, l)\) に遷移するので、そのように実装すればよいです。
状態が \(O(N^4)\) 、遷移が \(O(1)\) なので計算量は \(O(N^4)\) です。これは正しく実装すれば十分高速です。
Javaの実装例
import java.util.Scanner;
import static java.lang.System.out;
public class Main {
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
int N = sc.nextInt();
int[] a = new int[N];
for (int i = 0;i < N;++ i) a[i] = sc.nextInt();
final int MOD = 998_244_353;
int ans = 0;
for (int k = 1;k <= N;++ k) { // 先に、選ぶ要素数を決め打つ
int[][] dp = new int[k + 2][k]; // dp[j][l]: j個の要素を選び、総和をkで割った余りがlであるようなものの個数
dp[0][0] = 1; // 初期状態では0個を選び、総和も0
for (int i = 0;i < N;++ i) {
int[][] now = dp, next = new int[k + 2][k];
for (int j = 0;j <= Math.min(i, k);++ j) {
for (int l = 0;l < k;++ l) {
next[j + 1][(l + a[i]) % k] = (next[j + 1][(l + a[i]) % k] + now[j][l]) % MOD; // a[i]を使う時の組合せ
next[j][l] = (next[j][l] + now[j][l]) % MOD; // a[i]を使わない時の組合せ
}
}
dp = next;
}
ans = (ans + dp[k][0]) % MOD; // 選ぶ要素数kに一致し、かつ総和がkの倍数になったものが条件を満たす
}
out.println(ans);
}
}
}
Kotlinの実装例
import java.util.Scanner
import kotlin.math.min
fun main() {
Scanner(System.`in`).use { sc ->
val N = sc.nextInt()
val a = IntArray(N) {sc.nextInt()}
val MOD = 998_244_353
val plus = { l: Int, r: Int -> (l + r) % MOD}
val ans = (1..N).map { k -> // 先に、選ぶ要素数を決め打つ
var dp = Array(k + 2) {IntArray(k)} // dp[j][l]: j個の要素を選び、総和をkで割った余りがlであるようなものの個数
dp[0][0] = 1 // 初期状態では0個を選び、総和も0
for (i in 0 until N) {
val ai = a[i]
val next = Array(k + 2) {IntArray(k)}
for (j in 0..min(i, k)) {
for (l in 0 until k) {
next[j + 1][(l + ai) % k] = plus(next[j + 1][(l + ai) % k], dp[j][l]) // a[i]を使う時の組合せ
next[j][l] = plus(next[j][l], dp[j][l]) // a[i]を使わない時の組合せ
}
}
dp = next // 選ぶ要素数kに一致し、かつ総和がkの倍数になったものが条件を満たす
}
dp[k][0]
}.reduce(plus)
println(ans)
}
}
ちょっと高速化してみる
\(N=100\) で \(O(N^4)\) は少し怖い、そういう気持ちを持つ方も少なくないかと思います。
そこで、オーダー記法ではなくもう少し正確に計算量を見積もり、定数を改善する方法を考えていきましょう。
まず、上の実装では空間として \(N^2(k+2)k\) だけ確保しており、最もボトルネックになる遷移の処理は合計で \(\sum_{k=1}^N \sum_{i=1}^N k \min(i, k) \simeq \frac{5}{24}N^4\) 回です。
また、遷移の演算では余りを取る演算が3回発生するため、これが最も高負荷になります。
余りの演算はおおよそ \(20\) クロック掛かり、この部分の負荷は \(60\) クロックほどと推定されます。 競プロではおおよそ \(3 \times 10^9\) クロック程度が1秒で処理できるため、今回の実行時間は 0.4秒程度と予想できます。
ということはこれでも間に合うのですが、やはり高速化できるならば高速化していきたいです。
余りを高速に求める
まず、加算に比べて余りを取る演算は十分に遅いです。
従って、(l + a[i]) % kを両辺で計算することは無駄であり、いったん変数に入れて使いまわすことで剰余計算を減らすことができます。
また、そもそも加算の演算の場合に余りを取るなら剰余を取る必要はありません。
値 \(a, b\) がどちらも \(0\) 以上 \(P\) 未満のとき、 \(a+b\) は \(0\) 以上 \(2P-1\) 未満です。
従って、この値が \(P\) 以上なら \(P\) を引く、と書くだけで余りを取ったことになります。
これならば比較1回と引き算1回で済むので、高々 \(3\) クロック程度で収まります。
掛け算も高速化できるよ！
掛け算の場合は、上で用いた高速化を使うことはできません。
しかし、実は掛け算の場合の高速化手法も幾つか存在します。
掛け算を高速化する手法としては、Montgomery multiplicationやBarrett Reductionと呼ばれる方法が存在します。
Montgomery Reduction
配列を一次元にする
今回は多次元配列を用いていますが、一般に配列は次元が増えるほど遅くなります。
これは、多次元配列が実際には配列の配列という形になっており、アドレスが連続していないのが原因です。
例えばint[10000][2] array;と宣言した時、これは要素数 \(2\) の配列を \(10000\) 個宣言し、それを一つの配列に入れたことになります。
そこで、計算によって一次元化することで高速化が見込めます。と言っても二次元配列を一次元配列にすることによる速度上昇は \(2\) 倍もありませんが……。
posted:
last update: