最近、競技プログラミングを始めたのですが、才能はなく、要領も悪く、解法を覚えるのも苦手でどうしようもない弱者なのだと思い知る日々です。それでも、強くなりたいので、よく出てきそうなアルゴリズムやデータ構造や細かい Tips など何でも、メモできることはして、少しずつ知識と経験を蓄えていきたいと思って書いています。
今回は「約数カウント」についてメモします。
「約数カウント」
何をやるか
$1$ からある正の整数 $n$ までの整数のそれぞれについて、正の約数の個数を数え上げる。
どうやるか
- 長さ $n + 1$ の整数配列 $A$ を用意する。（つまり $n$ までのインデックスを持つ配列）
- $1$ から $n$ までの整数について、配列 $A$ 内でその整数の倍数をインデックスとする要素をインクリメントしていく。
コード
divisorCounts := make([]int, n+1, n+1)
// 1 から n までの i について
for i := 1; i <= n; i++ {
// i の倍数を処理
for j := i; j <= n; j += i {
divisorCounts[j]++
}
}
「約数カウント」を使う問題
AtCoder ABC172 D Sum of Divisors
私の解答はこちら: https://atcoder.jp/contests/abc172/submissions/14795780
上の説明で示した通りのコードを使います。
func Solve(n int) int {
divisorCounts := make([]int, n+1, n+1)
// 1 から n までの整数 i について
for i := 1; i <= n; i++ {
// i の倍数を処理
for j := i; j <= n; j += i {
divisorCounts[j]++
}
}
ans := 0
for i, v := range divisorCounts {
ans += i * v
}
return ans
}
AtCoder ABC134 D Preparing Boxes
私の解答はこちら: https://atcoder.jp/contests/abc134/submissions/14843714
この問題では、「約数カウント」を少し変形した形で使います。
「約数カウント」では $n$ の約数は $n$ 以下の範囲にしか存在しない ことを利用して、小さい $i$ から順番にその倍数を加算していくことで効率的に約数の個数を数え上げていきました。配列において インデックスの小さい要素から値を確定させていく イメージです。
それに対して以下では、これを逆転して $n$ の倍数は $n$ 以上の範囲にしか存在しない ことを利用します。配列において インデックスの大きな要素から値を確定させていく イメージです。
したがって、「約数カウント」とは対照的に、配列の後方 から要素を処理します。
func Solve(a []int) []int {
inOrNotList := make([]int, len(a)+1, len(a)+1)
var ans []int
// n から 1 までの整数 i について
for i := len(a); i >= 1; i-- {
sum := a[i-1]
// i の倍数を処理
for j := i * 2; j <= len(a); j += i {
sum += inOrNotList[j]
}
if sum%2 == 1 {
inOrNotList[i] = 1
ans = append(ans, i)
}
}
return ans
}
AtCoder ABC170 D Not Divisible
私の解答はこちら: https://atcoder.jp/contests/abc170/submissions/14849721
この問題は、 配列において他の要素のどれでも割り切れない要素を数える というものです。
これは言い換えれば、 配列において他の要素の倍数になっていない要素を数える ということですから、これは配列の各要素について、そのすべての倍数に対して（その数の約数が配列に含まれること示す）印をつけていくことで確かめられます。
func Solve(A []int) int {
sort.Sort(sort.IntSlice(A))
max := A[len(A)-1]
divisible := make([]int, max+1, max+1)
// 配列内の要素それぞれについて
for _, n := range A {
if divisible[n] != 0 {
divisible[n]++
continue
}
// 要素の倍数を処理
for multiple := n; multiple <= max; multiple += n {
divisible[multiple]++
}
}
notDivisibleCount := 0
for _, n := range A {
if divisible[n] == 1 {
notDivisibleCount++
}
}
return notDivisibleCount
}
最後に
私は記事を書くのも初心者ですから、分かりにくいところや説明不足なところがあったらどんどん厳しく教えていただけると幸いです。
また、自分で過去問に取り組む中で同系統の問題に遭遇したら、随時ここへ追加していきたいと思いますが、知っている方はコメントで教えていただけるととても嬉しいです。
最後まで読んで下さってありがとうございました。