AGC017 の B と ABC112 の A, B, C, D を解いた

AGC017 : AtCoder Grand Contest 017 の B を解いた。

• B - Moderate Differences https://atcoder.jp/contests/agc017/tasks/agc017_b
  • 提出: https://atcoder.jp/contests/agc017/submissions/32624169
  • 解説 AC
  • 解説がわかりやすい
  • Y_i = X_{i+1} - X_i とおく
  • -D <= Y_i <= -C C <= Y_i <= D \sum_{i=1}^{N-1}{Y_i} = B - A となる
  • m 個が -D <= Y_i <= -C のとき N - 1 - m 個は C <= Y_i <= D になる
  • よって -Dm + C(N - 1 - m) <= \sum_{i=1}^{N-1}{Y_i} <= D(N - 1 - m) + -Cm
  • -Dm + C(N - 1 - m) <= B - A <= D(N - 1 - m) + -Cm
  • m をすべて試して↑を満たすものが存在すれば YES なければ NO

---

ABC112 : AtCoder Beginner Contest 112 の A, B, C, D を解いた。

• A - Programming Education https://atcoder.jp/contests/abc112/tasks/abc112_a
  • 提出: https://atcoder.jp/contests/abc112/submissions/32626354
  • 指示通りに処理する
• B - Time Limit Exceeded https://atcoder.jp/contests/abc112/tasks/abc112_b
  • 提出: https://atcoder.jp/contests/abc112/submissions/32626414
  • t_i >= T の c_i のうち最小のものを取得する
  • iter して filter して min
• C - Pyramid https://atcoder.jp/contests/abc112/tasks/abc112_c
  • 提出: https://atcoder.jp/contests/abc112/submissions/32626609
  • C_x と C_y を全探索する
  • H は h_i > 0 の i をひとつ選んで x_i y_i から計算すれば良い
  • 情報は座標と高さを特定するのに十分という前提から h_i > 0 は存在する (すべて 0 だと特定できないため)
  • C_x と C_y から H を求めたら、すべての情報について矛盾がないかを調べる
  • 0 <= C_x, C_y <= 100 で N <= 100 から 10^6 程度の計算量になるので間に合う
• D - Partition https://atcoder.jp/contests/abc112/tasks/abc112_d
  • 提出: https://atcoder.jp/contests/abc112/submissions/32626797
  • a の最大公約数を g とおく
  • a_1 / g + a_2 / g + a_3 / g + ... + a_n / g = M / g
  • g * x = M となるので x と g は M の約数に含まれる
  • a は長さ N の正整数なので x >= N のときの g のうち最大のものが答えになる
  • M <= 10^9 で約数の列挙は \sqrt 10^9 なので間に合う

---

今日のコミット。

• rust-sandbox 7 commits
  • suiro: Rename area to map
  • suiro: Support some keys
  • suiro: Add cursor::left, right, up, down
  • suiro: Add size mod
  • suiro: Change max size
  • suiro: Add outer frame
  • suiro: Add Game
• rust-atcoder 2 commits
  • abc112 a, b, c, d
  • agc017 b