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 <= -CC <= 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) + -Cmmをすべて試して↑を満たすものが存在すれば 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_iy_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 / gg * x = MとなるのでxとgはMの約数に含まれる- a は長さ
Nの正整数なのでx >= Nのときのgのうち最大のものが答えになる M <= 10^9で約数の列挙は\sqrt 10^9なので間に合う
今日のコミット。