LoginSignup
0

More than 3 years have passed since last update.

競プロ参戦記 #55 Rain Flows into Dams | ABC 133

Posted at

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) になります。

rain-input1.png

各ダムの貯水量は両隣の山の降水量の半分の和なので、以下の連立方程式が立ちます。

  • 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 を使おうとしましたがいりませんでしたね……

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