C - All Green

はじめに

競技プログラミングAtCoder Beginner Contest 104
C - All Green
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

プログラミングコンペティションサイト AtCode は、アルゴリズムの問題集を提供しています。 
それぞれの問題には、難易度に応じて点数が付けられています。 
現在、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点以上にすることは可能である。

入力

入力は以下の形式で標準入力から与えられる。

D G
p1 c1
:
pD cD

出力

総合スコアをG点以上にするために解く必要のある最小の問題数を出力せよ。
なお、この目標は必ず達成可能である(制約を参照のこと)。

解き方

以下を参考にしています。
https://img.atcoder.jp/abc104/editorial.pdf
提出 #3149305 - AtCoder Beginner Contest 104

解き方の方針を考える

まず、
単純に点数が大きいほうから考えていけば
少ない問題数でGを超える得点を出せるように見えますが
コンプリートボーナスがあるので
この考え方では解けません。

次に
配点ごとの組み合わせを全て試すことを
考えますが
時間的制約に引っかかってしまうので
これも難しいです。

そこで、
制約の中で一番
数が小さいものを探します。
すると、以下の制約に気づきます。

・1≤D≤10

上の制約から
点数の種類は1以上10以下しかないことが分かったので
これを中心に解き方を考えてみます。

すると、
点数の取り方には以下の特徴があることに気づきます。

① 点数の種類(100i点)の中で、
 解く問題数が中途半端な数になるものが存在したとしても一つだけである、
 それ以外の点数の問題は全て解いてコンプリートボーナスをとるか、
 一問も解かないかのどちらか
② ①で解く問題が中途半端な数になるのは、問題を全て解く点数を除いた中で、最も点数が高い問題

①について
一つの点数に対する問題を全て解けば、
コンプリートボーナスがもらえるので
中途半端に解くよりも多くの得点を得ることができます。

なるべく少ない問題数で目標に到達するには
コンプリートボーナスをとるほうが得なので
基本的には一つの点数に対する問題は全て解くことなり、
解かない点数の問題は一問も解かず、
中途半端に解く点数は一つだけになります。

②について
中途半端に解く問題はコンプリートボーナスをとれないので、
とれる点数は問題の点数だけです、
そのため、
全ての問題を解く点数を除いた中で
一番点数の高いものを選ぶことによって
少ない問題数で目標点数に到達することができます。

解き方を考える

上で考えた方針をもとに具体的な解き方を考えていきます。
上で導いた特徴をもとにすると各点数は
以下の3グループ(③はあれば)に分けられます。

①全て解いてコンプリート報酬までとる
②全く解かない
(③)中途半端に解く(コンプリート報酬はとらない)

この中で③は
①でコンプリート報酬までとった合計が
目標点数を超えていてかつ
最も少ない問題数で済んでいる場合は存在しないので
取り敢えず①と②を出す方法を考えます。

各点数を①と②のグループに分けたいので、
ここではbit全探索が使えることに気づきます。

bit全探索については以下の記事が分かり易いです。
lovedvoraklayout.hatenablog.com

bit全探索で選ばれたものは
①全て解いてコンプリート報酬までとる
のグループに入れることにして
解いた問題数と
コンプリート報酬までとった点数を保存しておきます。

ここで、
保存した点数が目標点数まで到達して「いる」場合は、
今までの問題数の最小値と比べて
小さければ最小値として保存します。

保存した点数が目標点数まで到達して「いない」場合は
③に入れる点数のグループを考えます。

③の点数は
①全て解いてコンプリート報酬までとる
を除いて最も高いものです。

もしこの③の点数の問題数が足りずに
目標点数まで到達しなかった場合は
①②③の組み合わせが解答として正しくないので
飛ばして次の組み合わせを作ります。

問題数が足りて、
目標点数に到達した場合は
今までの問題数の最小値と比べて
小さければ最小値として保存します。

これを繰り返していくと、
問題数の最小値を出すことができます。

全体のコード

using System;
using System.Linq;
using System.Collections.Generic;

class Cmondai
{
    static void Main()
    {
        var dg = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
        var D = (int)dg[0];
        var G = dg[1];
        //問題数とボーナススコアを保存するリスト
        var list = new List<long[]>();
        for (int i=0;i<D;++i)
        {
            var pc= Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
            list.Add(new long[2] { pc[0], pc[1] });
        }
        //解く問題数の最小値を更新していく変数
        var ans = long.MaxValue;
        //bit全探索
        for (int i = 0; i < (Math.Pow(2, D)); i++)
        {
            var count = 0L;
            var total = 0L;
            for (int j = 0; j < D; j++)
            {
                if ((1 & i >> j) == 1) {
                    //「①全て解いてコンプリート報酬までとる」のグループに入るので
                    //問題数と点数を足す
                    count += list[j][0];
                    total += list[j][0] * 100 * (j + 1) + list[j][1];
                }
            }
            //目標点数まで足りない場合
            if (total < G)
            {
                //①に入るグループを除いた中で、最も点数の大きいものが対象になる
                for (int j = D - 1; 0 <= j; --j)
                {
                    //①のグループ((1 & i >> j) == 1)に入らないもの
                    if ((1 & i >> j) == 0)
                    {
                        //目標を達成するために必要な問題数
                        var add = ((G-total)+((j + 1) * 100)-1) / ((j + 1) * 100);
                        //問題数が足りていたら
                        if (add <= list[j][0])
                        {
                            //問題数と点数を足す
                            count += add;
                            total += add * 100 * (j + 1);
                            //最小値を更新
                            if (G <= total) ans = Math.Min(ans, count);
                        }
                        break;
                    }
                }
            }//目標点数まで足りた場合は、問題数の最小値を更新
            else ans=Math.Min(ans,count);
        }
        Console.WriteLine(ans);
    }
}