AtCoder Beginner Contest 162 の各問題の考察を書いていきます。
E問題が多く解かれそうにみえて、かつF問題がとっつきやすそうだったので、今回はFを先に解く戦法に出てみました。解けなかったので、結果は滑り込みのE完でした。
A - Lucky 7
問題概要: 3 桁の整数 N が与えられる。N のいずれかの桁に数字の 7 が含まれるか判定せよ。
A: 考察
N を数値型ではなく文字列型 (String など) の変数に持ち、文字 7 が含まれるか判定すればよいです。
String::contains が使えます。
let N: String = ...; // 入力を受け取る
let yes = N.contains('7');
println!("{}", if yes { "Yes" } else { "No" });
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc162/submissions/11797082
B - FizzBuzz Sum
問題概要: 列 a を次のように定義するとき、整数である a(i) (1≤i≤N) の総和を求めよ。
定義:
- a(i) = "FizzBuzz" (i が3でも5でも割り切れるとき)
- a(i) = "Fizz" (i が3で割り切れるとき)
- a(i) = "Buzz" (i が5で割り切れるとき)
- a(i) = i (上記以外)
B: 考察
「i が d で割り切れる」は「i を d で割ったあまりが 0」(i % d == 0)と言い換えられます。
a(i) = i となる条件は、i が3でも5でも割り切れないことです。各 i に対してこの条件を判定し、a(i) = i の総和を計算すればよいです。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc162/submissions/11794846
C - Sum of gcd of Tuples (Easy)
問題概要: $\sum_{a=1}^K \sum_{b=1}^K \sum_{c=1}^K \operatorname{gcd}(a, b, c)$ を求めよ。(ただし gcd(a, b, c) は a, b, c の最大公約数を表す。)
制約: K≤200
C: 考察
gcd(a, b, c) = gcd(gcd(a, b), c) = gcd(a, gcd(b, c)) が成り立ちます。
gcd はユークリッドの互除法を使うか、num_integer クレートの gcd 関数 を使えば、対数時間で求まります。
K が小さいので、3重ループを回して実際に gcd(a, b, c) を計算し、足せば OK です。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc162/submissions/11791272
D - RGB Triplets
問題概要: R, G, B からなる長さ N の文字列 S がある。以下の条件をすべて満たす (i, j, k) (ただし 1 ≤ i < j < k ≤ N) の個数を求めよ。
条件:
- S(i) ≠ S(j)
- S(i) ≠ S(k)
- S(j) ≠ S(k)
- j - i ≠ k - j
制約: N≤4000
D: 考察
直観的にいうと、文字列上の R, G, B の3文字を選ぶ方法を数える、ただし2つ目の文字が「中央」にあるような選び方は認めない、ということです。
R???G?????B (OK)
^^^ ^^^^^
3 5
R???G???B (NG)
^^^ ^^^
3 3
すべての i, j, k を列挙して条件を確認するのは O(N^3) 時間かかり、間に合いません。
S(i) = R, S(j) = G, S(k) = B と決め打ちして考えます。というのも、R, G, B の3文字をシャッフルする6通りを個別に解いて、結果を足せばよいからです。
いったん条件 j - i ≠ k - j を忘れて、(i, j, k) の数え方を考えます。制約から2重ループが間に合うので、(i, j) は全列挙してよいです。S(k)=B となる k (j < k ≤ N) の個数は、事前に累積和をしておけば O(1) 時間で求まります。
S = B R R G R B G B
1 0 0 0 0 1 0 1 B→1, R/G→0 とした配列を考える
3 2 2 2 2 2 1 1 後ろから累積和を取る
^ 右にある B の個数を表す
この方法では条件を満たさない k も数えてしまいます。条件を k について変形すると k ≠ 2j - i であり、この条件を満たさない k は k = 2j - i の1通りしかありません。つまり、S(2 * j - i) = B だったら1を引く、とすれば OK です。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc162/submissions/11850545
E - Sum of gcd of Tuples (Hard)
問題概要: 1 以上 K 以下の整数からなる長さ N の数列全体からなる集合を α とおく。Σ gcd(A) (A ∈ α) を求めよ。(mod 10^9+7)
制約: N, K≤10^5
E: 考察
整数の除算を x//y と書きます。
すべての数列 A を列挙して gcd(A) を計算するのは間に合いません。
最大公約数の値で数列をグループ分けし、各グループごとに総和を計算して足す 方針を考えます。最大公約数が g に等しい数列 A の個数を f(g) とおくと、そのような数列に関する総和は Σ gcd(A) = g・f(g) です。
次に数列の個数 f(g) を計算する方法を考えます。数列 A の最大公約数が g に等しいとき、数列の要素はすべて g の倍数です。逆に、数列の要素がすべて g の倍数なら A の最大公約数が g になるかというと、必ずしもなりません。最大公約数が 2g, 3g, ..., m・g (≤K) になることもあるからです。これらの分を差し引いて数えます。
2 4 6 8 ← すべて2の倍数、最大公約数は 2
4 8 16 32 ← すべて2の倍数、最大公約数は 4
6 6 36 72 ← すべて2の倍数、最大公約数は 6
数列の要素がすべて g の倍数である数列の個数は、各要素が K//g 通りなので、(K//g)^N 通りです。ここから、最大公約数が 2g, 3g, ..., m・g (≤K) である数列の個数を引きます。漸化式:
f(g) = (\operatorname{floor}(\frac{K}{g}))^N - \sum_{2g \leq m \cdot g \leq K}{f(m \cdot g)}
g の値が大きい順に f(g) を埋めていけば、問題なく計算できます。
// 疑似コード
for g: 1 <= g <= K (降順) {
count = (K / g)^N
for m: 2 * g <= m * g <= K {
count -= f[m * g] // (*)
}
f[g] = count
}
2重ループなので O(K^2) にみえますが、実は全体で O(K log K) 時間です。(*) の部分の実行回数は m の個数なので、各 g に対して K//g-1 回です。これらを足した和 (K//1 + K//2 + K//3 + ... + K//K - K) が O(K log K) になります。(調和級数を参照)
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc162/submissions/11850545
F - Select Half
問題概要: 整数の除算を x//y と書く。長さ N の整数列 A が与えられる。ちょうど N//2 個の要素を、どの2箇所も連続しないように選ぶ。選ばれた整数の和の最大値を求めよ。
制約: N≤10^5, |A(i)|≤10^9
F: 考察
数列 A の前から i 個の要素からなる部分を A(..i) と書きます。
例えば N=4 のとき、次の3通りの選び方があります。
- ●○●○
- ●○○●
- ○●○●
N=5 のときは、次の6通りです。
- ●○●○○
- ●○○●○
- ●○○○●
- ○●○●○
- ○●○○●
- ○○●○●
N=15 のときは ●○● ○●○ ●○● ○●○ ○○● など。
見てのとおり、選び方の自由度は低いです。言い換えると、選ぶ要素(●)の 間隔の上限 が小さく、実は常に 3 以下です。(仮に要素を4つ連続で選ばない部分(○○○○)があるとすると、両側で可能なかぎり要素を選んでも N//2 個未満になります。詳細は略)
このことから、前から順番に各要素を選ぶか否か決めていくとき、選びすぎても、選ばなすぎてもダメです。各 i に対して、A(..i) から選ぶ要素は (i//2 - 1) 〜 (i//2 + 1) 個、という条件が必要です。これにより状態数が大幅に減少し、O(N) になります。
次の DP により解けます。
- 状態 (i, s, u; 1≤i≤N, -1≤s≤1, u∈{0, 1}):
- A(..i) の各要素を選ぶか否かが決まっていて、ちょうど (i//2 + s) 個の要素を選んでいる。
- u=1 ⇔ A(i-1) を選んでいる
- 値:
- 状態 (i, s, u) において、選んだ要素の総和の最大値を dp(i, s, u) に持つ。
- 初期条件:
- i=0 のケースは dp(0, 0, 0) = 0 のみ
- 遷移 (i = 1, ..., N):
- i 番目の要素を選ぶケース
- (i+1, t, 1) ← (i, s, 0) + A(i) (for s)
- 遷移先の t の値は条件 (i//2 + s) + 1 = (i+1)//2 + t から決まる。
- i 番目の要素を選ばないケース
- (i+1, t, 0) ← (i, s, u) (for s)
- i 番目の要素を選ぶケース
なお、実装では s がマイナスにならないように s→s-1 に変換しています。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc162/submissions/11896993
反省: DP の設計に難儀しました。はじめは dp(i, p) = (A(..i) から i//2 + p 個の要素を選んだ状態での総和の最大値) と定め、「連続して選べない」は i → i+2 に遷移させることでカバーしていました。いま振り返ると、i//2-1 個の要素を選んだ状態や「直前の要素が選ばれているか」といった必要な情報が欠けているのでダメですね。