【AtCoder-Ruby】ABC104 C - All Green

問題

問題文

現在、1 以上 D 以下のそれぞれの整数 i に対して、100i点を付けられた問題が pi 問存在します。
これらの p1 + … + pD 問が AtCode に収録された問題のすべてです。
AtCode のユーザーは 総合スコア と呼ばれる値を持ちます。
ユーザーの総合スコアは、以下の 2 つの要素の和です。

• 基本スコア: ユーザーが解いた問題すべての配点の合計です
• コンプリートボーナス: 100i 点を付けられた pi 問の問題すべてを解いたユーザーは、基本スコアと別にコンプリートボーナス ci 点を獲得します ( 1 ≤i ≤D)

AtCode の新たなユーザーとなった高橋くんは、まだ問題を 1 問も解いていません。 彼の目標は、総合スコアを G 点以上にすることです。
このためには、少なくとも何問の問題を解く必要があるでしょうか？

制約

• 1 ≤D ≤10
• 1 ≤pi ≤100
• 100 ≤ ci ≤ 10 ** 6
• 100 ≤ G 入力中のすべての値は整数である
• ci, G はすべて 100 の倍数である
• 総合スコアを G 点以上にすることは可能である。

問題リンク

考えたこと

むずい。。。
多分貪欲法で、一番点数の高い問題から順に実行すると思うけど、ボーナスはどうする。
すべてのパターンをチェックするだと間に合わない。

神に聞いてみよう。

全完する難易度帯を 2D 通り決め打ちする

• それだけで G 点に到達する場合はそれで OK
• それだけでは到達しない場合は、全完対象でないもののうち Greedy に高難易度から順に解いて行けば OK

ここで全完対象でないものを結果的に全完してしまう場合などへの不安が頭をよぎるが、
そういうやつは「そういうやつについても全完するように決め打ちした場合」できちんと考慮されるはずなので気にしなくて OK！

出典: AtCoder ABC 104 C - All Green (300 点)

なるほど。

回答

答え見ちゃいましたが、おいらなりに書いてみました。

def chmin(a, b) a < b ? a : b end

D, G = gets.strip.split.map(&:to_i)

counts = []
points = []
D.times { |i| counts[i], points[i] = gets.strip.split.map(&:to_i) }

res = 10 ** 6
(1<<D).times do |mask|
  sum = 0
  count = 0
  D.times do |i|
    unless (mask & (1<<i)).zero?
      sum += (counts[i] * (i + 1) * 100) + points[i]
      count += counts[i]
    end
  end

  if sum < G
    (D - 1).downto(0) do |i|
      next unless (mask & (1<<i)).zero?
      (0...counts[i]).each do
        break if sum >= G
        sum += (i + 1) * 100
        count += 1
      end
    end
  end
  res = chmin(count, res)
end

puts res

考察

bit 全探索 について

けんちょんさんの回答で 1をシフトする処理があり、これが何かわからなかった。。。
調べた結果これもけんちょんさんのエントリーだが「bit 全探索」アルゴリズムで、数十件であれば、この手法が適用可能。

bit 全探索とは、n 個の要素からなる集合 {0,1,…,n−1} の部分集合をすべて調べ上げる手法のことです。以下のように実施できます: 　・ この解法では例えば n=100 となると計算時間的に破綻してしまいます。

bit 全探索

だから「これはなんか結構大変な Greedy になりそうな予感がするところに、制約 D≤10 が目に入る。」という件がでてくるのか。なるほど。

もっと良い書き方は？（正解者を参照）

一番短いやつを参照してみました。
Ruby とか Perl とか直感で書けると気持ちい良いけど、後から見直した時に思い出せる程度には見やすさも大切と感じる。
バランスが大切。

eval"D,G,*A="+`dd`.split*?,
p (0..1023).map{|b|n=e=0;s=G;D.times{|i|q,c=A[i*2,2];e+=100;b[i]>0?(n+=q;s-=q*e+c):Q=q*E=e};s>0?s>Q ? G: n--s/E: n}.min