LoginSignup
0

More than 3 years have passed since last update.

競プロ参戦記 #57 Digits Parade | ABC 135

Last updated at Posted at 2019-07-30

ABC-only 回です。D 完でした。E は何も分かりませんでした……

AtCoder Beginner Contest 135

A - Harmony

問題概要: 整数 A, B (ただし A≠B) が与えられる。|A-K| = |B-K| となる整数 K が存在するか判定し、存在するなら求めよ。

A: 考察

絶対値 |A-K| は数直線上の AK 間の距離なので、条件は「AK 間と BK 間の距離が等しい」と読めます。つまり K は A と B の中央である (A+B)/2 です。整数にならないケースに注意しましょう。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc135/submissions/6567400

B - 0 or 1 Swap

問題概要: (1, 2, .., N) を並び替えた数列 P が与えられる。1回だけ、2つの要素を交換してもよい。P を昇順にできるか判定せよ。

B: 考察

実際に交換してみて、昇順になったか確認すればいいです。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc135/submissions/6566602

C - City Savers

問題概要: N+1 個の街があり、N 人の勇者がいる。i 番目の街が A(i) 体のモンスターに襲われている。i 番目の勇者は i, i+1 番目の街を襲っているモンスターを、合計で B(i) 体まで倒せる。勇者たちが倒せるモンスターの数の合計の最大値を求めよ。

C: 考察

1番目の街のモンスターを倒せるのは1番目の勇者だけなので、1番目の勇者は可能なかぎり1番目の街のモンスターを倒すのがよいです。その後、1番目の勇者は2番目の街のモンスターしか倒せないので、それを可能な限り倒します。

このとき、1番目の勇者が倒せるモンスターはすべて倒したので、2番目の街の残りのモンスターを倒せるのは2番目の勇者だけです。始めと同じ状況になったので、繰り返しで処理すればOKです。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc135/submissions/6564259

D - Digits Parade

問題概要: 数字と '?' からなる長さ N の文字列 S が与えられる。'?' を数字に置き換えて得られる整数のうち、13で割った余りが5に等しいものの個数を求めよ。(mod 10^9+7) (0 で始まる文字列もカウントする。)

D: 考察

もし「13で割って5余る」ではなく「3で割って0余る」(3の倍数)だったら、よくある桁DPです。「3の倍数は各桁の数字の和も3の倍数」という性質を使って解けるからです。

AtCoder ではコンテスト中のインターネット検索が認められているので、13 の倍数の似たような判定法がないか調べてみました。1001が13の倍数であることを利用する倍数判定法があるそうです

整数の10進展開に3桁ごとにカンマを入れて数列とみなし、交互に足し引きして13の倍数になるか確認する、という方法です。例えば 314158 は -314 +158 = -156 ≡ 0 (mod 13) なので13の倍数です。

数式で書けば $\sum_{i=0}^k 10^{3i} x_i \equiv \sum_{i=0}^k (-1)^i x_i \pmod{13}$ です。$1000 \equiv -1 \pmod{13}$ (☆) を使うと、数学的帰納法により証明できます。(無証明貪欲を反省しつつ。)

k = 0 のケースは自明なので k > 0 とします。

\begin{align}
\sum_{i=0}^k 10^{3i} x_i
  & \equiv 1000 \sum_{i=0}^{k-1} 10^{3i} x_{i+1} + x_0 & \qquad (シグマをずらした) \\
  & \equiv 1000 \sum_{i=0}^{k-1} (-1)^i x_{i+1} + x_0 & \qquad (帰納法の仮定を使った) \\
  & \equiv -\sum_{i=0}^{k-1} (-1)^i x_{i+1} + x_0 & \qquad ((☆) を使った) \\
  & \equiv \sum_{i=0}^k (-1)^i x_i & \qquad (シグマをずらした) \\
  \pmod{13}
\end{align}

というわけで、桁DPで解けます。実装は3の倍数を数える桁DPと同様で、「各桁」の代わりに「各3桁」、「各桁の和」に符号がつく、というだけです。

計算量を考えます。最悪のケース ???..??? では3桁ごとに 1000 ステップで遷移するので、全体としては 10^5/3 * 10^3 で 10^8 ステップくらいです。1ケース TLE しましたが、剰余をとる頻度を下げるという最適化をしてなんとか AC。

    // 抜粋 (遷移部分のみ)

    for d1 in lb(S[bi * 3])..ub(S[bi * 3]) { // 3i 桁目の数字
        let a = d1 * 100;
        for d2 in lb(S[bi * 3 + 1])..ub(S[bi * 3 + 1]) { // 3i+1桁目
            let b = a + d2 * 10;
            for d3 in lb(S[bi * 3 + 2])..ub(S[bi * 3 + 2]) { // 3i+2桁目
                let y = b + d3;
                let z = (13 + y - x) % 13; // (☆) を使う
                dp[bi + 1][z] += dp[bi][x];
                // ここで余りを取ると遅い
                // 10^3×10^9 は溢れないので余りを取らなくてOK
            }
        }
    }

    for z in 0..13 {
        dp[bi + 1][z] %= P; // まとめて余りを取る
    }

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc135/submissions/6575515

解説PDFの解法 (DP) の方が賢いですね。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0