2022-02-16 アルゴリズムと数学 演習問題集 042, 043 を解いた
アルゴリズムと数学 演習問題集 042 - Sum of Divisors を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/abc172_d
単純に 1 から N まで走査してそれぞれで K * f(K) を計算すると f(K) の約数列挙に O(\sqrt{K}) なので全体で O(N \sqrt{N}) になる。これは間に合わない。
良い規則性を見つけるために K = 1 から順に書き出してみる。
f(1) = 1 -- {1}
f(2) = 2 -- {1, 2}
f(3) = 2 -- {1, 3}
f(4) = 3 -- {1, 2, 4}
f(5) = 2 -- {1, 5}
f(6) = 6 -- {1, 2, 3, 6}
-- 1, 2, 3, 4, 5, 6
1 * f(1) = 1
2 * f(2) = 2 + 2
3 * f(3) = 3 + 3
4 * f(4) = 4 + 4 + 4
5 * f(5) = 5 + 5
6 * f(6) = 6 + 6 + 6 + 6
書き出したものを縦に読むと初項 K 公差 K 項数 N/K (切り捨て) の等差数列になっている。 1 から N までのそれらの等差数列の和を計算すれば良い。全体では O(N) になり間に合う。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29371017
アルゴリズムと数学 演習問題集 043 - Is It Connected? を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_am
グラフ全体が連結かどうかはある頂点から他のすべての頂点に到達できれば良い。 DFS でも BFS でも Union-Find (FenwickTree) でも良い。ぼくは BFS にした。
頂点 1 を到達済みとマークして enqueue する。 dequeue した頂点 u から出る辺の繋がっている頂点 v を未到達なら enqueue する。この dequeue → 辺を走査 → 未到達なら enqueue を queue が空になるまで繰り返す。これで頂点 1 から到達可能なすべての頂点が到達済みとマークできる。
すべての頂点が到達済みになっているなら連結だ。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29371131
今日のコミット。