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