トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

AtCoder Beginner Contest 034

[競技プログラミング,競プロ解説]

AtCoder Beginer Contest 034 - D

  解説

どうやって食塩水を選ぶか

  • ある数列やハッシュ(以下集合と呼ぶ)が与えられたとき、K個選んで平均や価値を最大化するとする
    • 無能おじさん「ソートして貪欲法で最大を取ればいいじゃん」
    • ???「そんな簡単にできるわけないんだよなあ…」

無能おじさんの試行

  • 食塩水の濃度の高いやつからK個とればいいじゃん(いいじゃん)
3 2
100 15
300 20
200 30
  • 無能おじさん「濃度の高いやつは下から{w,p} = {200,30},{300,20} なんだから」
  • 無能おじさん「食塩の合計 ÷ 食塩水の合計の重さ × 100 が答えでしょ、 小学生でもできる」
  • 無能おじさん「食塩の合計 ÷ 食塩水の合計の重さ × 100 = (200*0.3 + 300*0.2) ÷ (200+300) × 100 = 24.000000000 (ドヤ)」
  • ???「答えは25.000000000のようですが…そもそも濃度でソートしたとしても水の量で全然結果違いますよね??」
  • 無能おじさん「ファッ…おかしい。こんなことは許されない…」

蟻本精読

  • 実はこの問題は蟻本の中級編に収録されている典型問題のようだ。無能おじさんが失敗したように、この問題は単純にソートして貪欲法で取得することはできない。
  • ではどうするか?コンピュータプログラムは全探索を許容するので探索すればいいのだが、単純にNからK個選んでくる処理を作るととたんに破綻してしまう。ので、ここでは二分探索を使用する。
  • 考え方のヒントは 評価関数をもつ二分探索 に書いた。

  解説の解説

  • 手順
    • 評価関数C(x)を用意する ← ここにほとんどの労力を使う
    • 0 ~ 10^5 までの範囲で適当に二分探索実行
    • 評価関数C(x)のxが食塩水の濃度で設定するので、二分探索で求めた下限〜上限の間を答えとする

評価関数C(x)を用意する

  • 蟻本の定石の通り、xを目的とする濃度として式を立て、式変形
    1. %5Csum%5F%7Bi%3D0%7D%5E%7Bk%7D+%28w%5Fi+%5Ccdot+p%5Fi+%2F+100%29+%2F+%5Csum%5F%7Bi%3D0%7D%5E%7Bk%7D+w%5Fi+ (= 食塩の合計値 ÷ 食塩水の合計値)
    2. %5Csum%5F%7Bi%3D0%7D%5E%7Bk%7D+%28w%5Fi+%5Ccdot+p%5Fi+%2F+100%29+%2F+%5Csum%5F%7Bi%3D0%7D%5E%7Bk%7D+w%5Fi+%5Cgeq+x+ (= 食塩の合計値 ÷ 食塩水の合計値 ≧ 濃度X )
    3. %5Csum%5F%7Bi%3D0%7D%5E%7Bk%7D+%28w%5Fi+%5Ccdot+p%5Fi+%2F+100+%2D+x+%5Ccdot+w%5Fi%29+%5Cgeq+0+ (= 食塩の合計値 ÷ 濃度X - 食塩水の合計値 ≧ 0 )
   # @w = water
   # @p = concentration
   #  sigma (@w*@p/100) / sigma (@w)
   #  sigma (@w*@p/100) / sigma (@w) >= x
   #  sigma (@w*@p/100 - x*@w) >= 0
  • Float値として計算したいのでやたら面倒になった
  def C(x)
    y=[]
    for i in [email protected]
      y[i] = (@w[i].to_f*@v[i].to_f).quo(100).to_f - (x * @w[i].to_f).to_f
    end
    y=y.sort

    sum=0.to_f
    for i in [email protected]   # 合計するのはK個まで
      sum+=y[@n-i-1]
    end

    return sum>=0
  end

二分探索実行

    INF = 10**5 # 適当にデカイ値をキメておく

    lb,ub=0.to_f,INF.to_f
    for i in 0..100
      mid = (lb+ub).quo(2).to_f

      if C(mid)
        lb = mid
      else
        ub = mid
      end
    end

二分探索で求めた下限〜上限

  • upper_bound, lower_bound どちらを答えとしても誤差が小さいので大丈夫
puts "%.9f" % (ub * 100)
お名前: コメント: