blog.bouzuya.net

2022-06-20 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 を解いた。


今日のコミット。