AtCoder Beginner Contest 162 の各問題の考察を書いていきます。

E問題が多く解かれそうにみえて、かつF問題がとっつきやすそうだったので、今回はFを先に解く戦法に出てみました。解けなかったので、結果は滑り込みのE完でした。

前回: 競プロ参戦記 #77 Yutori | ABC 161
問題一覧: https://atcoder.jp/contests/abc162/tasks

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)

なお、実装では 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 個の要素を選んだ状態や「直前の要素が選ばれているか」といった必要な情報が欠けているのでダメですね。