AtCoder Regular Contest 083
Updated:
Source codes
Solutions
C - Sugar Water
水の量は総当たりできる。すると最大の砂糖の量が求まる。 それをできるだけ達成するようにしたいが C の方を固定すると、 D も決まる。 ループの内側の回る回数は 30 * 30 * 1500 くらいで済むので間に合う。
ポイント
答えの濃度が 0 である場合に注意。
D - Restoring Road Network
全ての 3 頂点について、三角不等式を充していない場合、不可能。 最短経路より短い経路を与えている。 充している場合は、可能である。全ての頂点のペアに対し、最短経路の道を作ればいい。
このグラフから何本削れるかを競うわけだが、さっきの三角不等式で退化している辺は削っても良い。遠回りの道とどちらを削ってもコストは変わらないが、遠回りの道を削ると影響が出るかもしれない。しかし退化している辺を削っても影響は出ない。遠回りの道を通ればいいからだ。 逆に、退化が一度も起こってない辺は削ってはならない。その辺を削ると最小距離が達成できなくなるからだ。
E - Bichrome Tree
頂点にペアを対応させる。そのペアは (頂点の色に対応したコスト つまり X[i], そうでない色のコスト) というようにしたい。
まず、子がいない頂点は (X[i], 0) 以外にやりようがない。
子のペアが決まっているとして、その頂点のペアを決めよう。
ペアの小さい方の和が X[i] を超えていると、非負整数を書きようがないから IMPOSSIBLE である。そうでないとすると、とりあえずそれらを選んで同じ色にして数字を書き込めばいい(黒か白かは後から親の都合で子の方を反転させれば辻褄があう)。これを根まで続けられれば POSSIBLE である。
ところが、今いった方法はベストの方法ではない。サンプルで実験すると、書く数字は小さければ小さいほど上に対して有利であると。つまり第 2 成分はできるだけ小さく持っておきたい。
私たちに許される動作は、同じ色として各子のペアの第 1 成分を採用するか第 2 成分を採用するかである。それら全ての和は一定なので、「第 2 成分はできるだけ小さく」とは「各子のペアの第 1 成分を採用するか第 2 成分を採用することにより X[i] 以下で最大の数 $M$ を得る」ことに等しい。 $(X[i], \mathrm{allsum} - M)$ が求めるペアである。これは原始的な動的計画法をやることによって求まる。
ポイント
一発で正解してびっくりした。頑張って考察して、必死に実装すれば通る。
F - Collecting Balls
見てもいない。
ポイント
Others
C - sample: 3, tle: 3.000, time: 20:41, from_submit: 69:05
D - sample: 4, tle: 2.000, time: 10:00, from_submit: 59:04
E - sample: 4, tle: 2.000, time: 59:05, from_submit: 00:00
F - sample: 5, tle: 2.000, time: 00:00