Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
1
Help us understand the problem. What are the problem?

More than 1 year has passed since last update.

競プロ参戦記 #78 Select Half | ABC 162

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通りの選び方があります。

  1. ●○●○
  2. ●○○●
  3. ○●○●

N=5 のときは、次の6通りです。

  1. ●○●○○
  2. ●○○●○
  3. ●○○○●
  4. ○●○●○
  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 個の要素を選んだ状態や「直前の要素が選ばれているか」といった必要な情報が欠けているのでダメですね。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
1
Help us understand the problem. What are the problem?