AtCoder Regular Contest 083

更新日時:

AtCoder Regular Contest 083

ソースコード

解法のメモ

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

見てもいない。

ポイント

その他

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

コメントする