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

AtCoder Beginner Contest 135

この連載記事では、着手した問題の考察を自分なりに書いていきます。
- 前回: 競プロ参戦記 #56 Sequence Decomposing | ABC 134
問題の詳細は問題一覧を参照してください。
- 問題一覧: https://atcoder.jp/contests/abc135/tasks

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) の方が賢いですね。