オンサイトで未確認

ukuku09の活動記録。

2017-02-17から1日間の記事一覧

AtCoder Beginner Contest 034 D: 食塩水

ABC埋め続き。 問題文 abc034.contest.atcoder.jp 解法 貪欲に混ぜるとダメ。 水:食塩の比率が同じ2つの食塩があるときは、水が少ないほうを優先的に入れたほうが、全体の濃度を薄める効果が小さい(=最終的な濃度を大きくできる)。みたいに考えていると…

AtCoder Beginner Contest 023 D: 射撃王

ABC埋め。 問題文 abc023.contest.atcoder.jp 解法 制約的に $O(NlogN)$ くらいかなぁってなるので、二分探索をする。 風船のペナルティの最大値を x とすると、各風船がそこに到達するまでの時間は、 $$T_i = (x - H_i) / S_i$$ で求められる。あとは、この…

AtCoder Beginner Contest 051 D: Candidates of No Shortest Paths

ABC埋め中。 問題文 abc051.contest.atcoder.jp 解法 Warshall-Floyd で全頂点間の最短経路を求めて、与えられたエッジの端点間の最短経路重みがエッジの重みより小さくなっているかどうかを判定するだけで、そのエッジがグラフ上のいずれかの最短経路上に含…

AtCoder Beginner Contest 054 D: Mixing Experiment

2月なのでABC埋め。記事は自分用なのであんまりタメにならなそう。 問題文 abc054.contest.atcoder.jp 解法 制約がそんなに大きくないので01ナップザックっぽく解いた。 dp[i][j][k]:=薬品 i-1 まででタイプAが j グラム、タイプBが k グラムの溶液を作る最…