yoyoyousei technical notes

サーバ、インフラ周りについて書きます

AtCoder Regular Contest 083 解法

コンテストページ

arc083.contest.atcoder.jp

C - Sugar Water

問題

次の4種類の操作を行って砂糖水を作る。

  • 操作 1: ビーカーに水を 100A [g] 入れる。
  • 操作 2: ビーカーに水を 100B [g] 入れる。
  • 操作 3: ビーカーに砂糖を C [g] 入れる。
  • 操作 4: ビーカーに砂糖を D [g] 入れる。

できるだけ濃度が高く、砂糖が溶け残っておらず(砂糖は100[g]当たりE [g]溶ける)、重さがF以下の砂糖水を作って砂糖水の重量とそれに溶けている砂糖の質量を求めろ。答えが複数ある場合はどれを答えても良い。

 

制約

  • 1≦A<B≦30
  • 1≦C<D≦30
  • 1≦E≦100
  • 100A≦F≦3,000
  • A,B,C,D,E,F はすべて整数である。

解法

制約より、操作1~3を行った回数で全探索する。なるべく濃度の高い砂糖水を作りたいので、操作1~3を行った回数が分かれば最適な操作4の回数が決まる。操作4を行う回数は合計の重量がFを超えない、かつは砂糖が溶け残らない回数だけ行えばいい。0[g]の砂糖水はダメなので(コンテスト中のclarificationより)濃度0%の砂糖水をつくるの場合もそれを作るときの砂糖水と砂糖の量を出力することに気をつける。

計算量は O(F/ 100A * F/100B * F/C )で A, B, C が1でFが3000だとしても 2.7 * 106で十分間に合う。

提出コード: http://arc083.contest.atcoder.jp/submissions/1601536

D - Restoring Road Network

問題

頂点nの都市があり、いくつかの都市の組は道路で双方向に結ばれている。全ての都市と道をグラフと考えたときにグラフは連結無向グラフとなっている。 n x nの表Aが与えられる。全てのAu,vについて、Au,vが都市uから都市vまでの最短経路になるようなグラフが存在するか調べよ。もし存在するならそのようなグラフの中で道路の長さの和が最小になるようなものについてその和を求めよ。存在しないなら-1を出力しろ。

制約

  • 1≦N≦300
  • i≠j のとき、1≦Ai,j=Aj,i≦109
  • Ai,i=0

解法

まずワーシャルフロイドで全てのu, vについてAu,vの長さの辺を張ったときのグラフで各点の間の最短経路がAu,vと等しいかチェック。

等しいなら所望のグラフは存在する。ただ全ての辺についてAu,vの辺を張ったグラフは存在する道路の長さの和が最小とは限らないので、全ての辺Eu,vについて、Eu,v == Eu,x + Ex, vとなるxが存在するかチェックする。 存在するならEu, vはなくても最短経路は変わらないので取る。

等しくないなら所望のグラフは存在しないので-1。

計算量はO(N3)。

提出コード:

Submission #1602625 - AtCoder Regular Contest 083 | AtCoder

まとめ

今年から社会人なのですが、お仕事慣れて余裕ができたので参加。

やっぱり問題解けると楽しい