AtCoder Regular Contest 083

参加しました。

C問題 sugar water

100aか100bの水を入れる、もしくはcかdの砂糖を入れるを繰り返してf以下の重さの最も濃い砂糖水を作れ（ただし、100に対してeしか砂糖は溶けず溶け残りがあってはいけない)という問題。

不等式をきちんと立ててa,bのありうる値を全部やればいい。

0gの砂糖水は僕は存在すると思います(1WA)

D問題　Restoring Road Network

N個の都市があり、N*Nの行列Aが与えられた時、Au,vが都市uから都市vへの最短距離に成るような構造はありますかという問題。あったら道の長さの総和の最短を計算せよ。

u,vに対してAu,v=Au,w+Aw,vみたいなwが存在したらその時点でu,v間に道はなくていいねという感じ。N<=300なのでu,v,w全部について試して、可能な限り道を消す。

その後、作ったグラフに対してワーシャルフロイドをして、本当に行列Aのようになっているか確認すれば良い。

E問題　Bichrome Tree

もうなんか面倒なので問題の内容省略。

各頂点について(Xi,Yi)みたいな感じのものでYiが最小に成るものを計算し、ナップザックに帰着しました。

バグらせました。

for(int i=n;i>=1;i++){

直したら通りました。はいさようなら。

179位　パフォーマンス2071 レート1987(+10)

来週こそ黄色へ