ABC-only 回です。参加できなかったので練習記になります。D に90分ぐらい費やしていたので実質C完でした。
AtCoder Beginner Contest 133
- この連載記事では、着手した問題の考察を自分なりに書いていきます。
- 問題の詳細は問題一覧を参照してください。
A - T or T
問題概要: N 人で旅行しようとしている。交通手段として電車とタクシーがある。電車を使うと、1 人あたり A 円のかかる。タクシーを使うと、N 人で B 円かかる。交通費の最小値を求めよ。
A: 考察
1人あたり A 円ということは N 人で N * A 円です。N * A と B の小さい方を出力すればよいです。
2つの数値の小さい方を計算する関数として std::cmp::min があります。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc133/submissions/6397873
B - Good Distance
問題概要: D 次元上に N 個の点がある。i 番目の点の座標を (X(i, 1), X(i, 2), .., X(i, D)) で表す。点のペアで、2点間の距離が整数であるようなものを数えよ。
制約:
- N≤10
- X(i, j): 整数
B: 考察
制約から点のペアは 100 通り以下です。これらを列挙して、ペアが実際に条件を満たすか判定する方針で考えます。
制約から点の座標は整数なので、2点間の距離の2乗 X は常に整数になります。X の平方根 (距離) が整数かどうかは、実際に r * r = X になる整数 r があるかを調べればよいです。
調べるのは r * r ≤ X の範囲で十分なので、全体として O(√X) 時間です。具体的には、制約から X < 10^9 が分かるので、10^5 ステップ程度です。
全体として 10^7 ステップ程度で解けます。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc133/submissions/6397954
C - Remainder Minimization 2019
問題概要: 非負整数 L, R が与えられる。条件 L ≤ i < j ≤ R をみたす整数 i, j について、式 (i * j) % 2019 の最小値を求めよ。
C: 考察
はじめに最小値 0 を達成できるか確認します。(i * j) % 2019 = 0 は要するに i * j が 2019 の倍数ということなので、i, j のどちらかを 2019 の倍数にすればよいです。
L, R の範囲が十分に広ければ (R - L > 2019)、2019 の倍数が含まれるので最小値 0 が達成可能です。
逆に R - L ≤ 2019 のケースでは、全探索すればよいです。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc133/submissions/6398035
D - Rain Flows into Dams
問題概要: 円周上にダムと山が交互に N 個ずつ存在する。i 番目の山に x リットルの雨が降った後、両隣のダムにそれぞれ x/2 リットルの水が溜まることが知られている。
i 番目のダムに溜まっている水の量を A(i) とおく。はじめ A(i) = 0 である。すべての山に雨が降った。これにより i 番目の山に降った雨の量を L(i) リットルとおく。このときの貯水量 A(i) が与えられる。
L(i) は一意に定まる。L(i) を求めよ。
制約:
- N: 奇数
- L(i): 偶数
D: 考察
例えば N=3, A=(2, 2, 4) なら以下のように、降雨量がそれぞれ L=(4, 0, 4) になります。
各ダムの貯水量は両隣の山の降水量の半分の和なので、以下の連立方程式が立ちます。
- L(1)/2 + L(2)/2 = A(1)
- L(2)/2 + L(3)/2 = A(2)
- L(3)/2 + L(1)/2 = A(3)
変形すると、
- L(2)/2 = -L(1)/2 + A(1)
- L(3)/2 = -L(2)/2 + A(2)
- L(1)/2 = -L(3)/2 + A(3)
となります。
上の2本の式によれば L(2), L(3) はいずれも L(1) を使って表せます。そのため、3本目の式は L(1) 単独の一次方程式に変形可能です。それを解けば L(1) の値が判明して、残りの変数の値も計算できます。
方針が定まったので、次に実装です。変数 L(i) が L(1) の一次式で表すということは、以下の式を満たす s(i), t(i) (係数) を求めればいいです。
L(i) = s(i) * L(1) + t(i)
i=1 では明らかに s(i)=1, t(i)=0 です。
一般に L(i+1) (ただし i+1≤N) については、
L(i+1)/2 = -L(i)/2 + A(i)
L(i+1) = -L(i) + 2 * A(i)
= -(s(i) * L(1) + t(i)) + 2 * A(i)
= (-s(i)) * L(1) + (2 * A(i) - t(i))
s(i+1) = -s(i)
t(i+1) = 2 * A(i) - t(i)
となります。最後の式だけは L(i), L(i+1) ではなく L(N), L(1) に関する式なので一般化できませんが、
L(N) = s(N) * L(1) + t(N)
L(1)/2 = -L(N)/2 + A(N)
L(1) = -L(N) + 2 * A(N)
= -(s(N) * L(1) + t(N)) + 2 * A(N)
= (-s(N)) * L(1) + (2 * A(N) - t(N))
(1 + s(N)) * L(1) = 2 * A(N) - t(N)
L(1) = (2 * A(N) - t(N)) / (1 + s(N))
というふうになります。(N が奇数という制約のおかげで 1 + s(N) ≠ 0 (= 2) がいえます。)
というわけで DP で解けました。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc133/submissions/6399196
Weighted Union Find を使おうとしましたがいりませんでしたね……