ABC 087 - チラシの裏.htm

A

Submission #2090176 - AtCoder Beginner Contest 087

特筆事項無し

B

Submission #2090240 - AtCoder Beginner Contest 087

可能な硬貨の支払い方を全て試せばおｋ

${10a + 2b + c = x\,(0 \leq a \leq A, 0 \leq b \leq B, 0 \leq c \leq C, x = \frac{X}{50})}$ を満たす $(a, b, c)$ の組を求める問題なので $O(1)$ で解ける気がしなくも無い。一応 ${2(5a + b) = x - c = 2k\,(k: \text{整数})}$ とすることで不等式制約を満たす格子点 ${(x, k)}$ を求める問題に帰着されるけど、制約に対応する領域の形に応じて場合分けするのが割りと面倒くさそう。

C

Submission #2090297 - AtCoder Beginner Contest 087

深さ優先探索

D

Submission #2095728 - AtCoder Beginner Contest 087

頂点数 ${N}$ で辺 ${(L_i, R_i),(R_i, L_i)}$ のコストがそれぞれ $D_i, -D_i$ となる有向グラフを構成する。頂点は $x$ 軸上の人に、辺は2頂点間の距離の制約にそれぞれ対応する。グラフの各連結成分内で1点の座標を適当に固定すると他の成分内の座標も自動的に決まることを利用し、幅優先探索で隣接する頂点の座標を計算して既に求められた座標の値と合っているかどうかをチェックする。これを全ての点の座標が計算済みになるまで繰り返せば良い。

ある連結成分内の幅優先探索を終える度に座標を毎回リセットするというミスに気づかずTLEを起こしまくった。恥ずかしい。