AtCoder ABC057 D - Maximum Average Sets
問題
D: Maximum Average Sets - AtCoder Beginner Contest 057 | AtCoder
N(1 <= N <= 50)個の品物が与えられ、それぞれの品物には価値Vi(1 <= i <= N)が設定されている。A個以上、B以下の品物を取ることが出来る時、選択した品物の価値の最大の平均値と、その最大の平均値となるように品物を選択する通り数を出力する問題。
解法
まずは、全列挙できるか考え見る。
全列挙による解法
品物を選択する方法を全列挙し、平均値を計算するという方法を考えてみる。全列挙の通り数は、N個の中からi(A <= i <= B)個選択する場合の数の総和となる。N個の中からi個選択する場合の数は、NCi (nCk: combination)と表す事ができる。よってΣ(A <= k <= B) nCk
となり、最大で計算量はO(2N)なる。この場合、N = 50の時に間に合わない。よって別の解法を考える。
ソート済みの配列からA個取る解法
この問題のポイントは平均値を出すということだ。価値の配列を昇順のソートすると、先頭から後方にかけて値は小さくなる。この時、先頭からA個取った場合が平均値が最大となる。これは平均の計算方法が分母に選択した要素数を当てるからである。
次に、平均値が最大となるような品物のとり方の場合の数を考えてみる。具体的に、以下のような場合を考える。
N = 4, A = 2, B = 3
values = {20, 10, 10, 10}
上記の例では、先頭からA個、つまり2個取った場合、選択した品物の価値は{20, 10}となる。これらの値で平均値を計算したものが最大の平均値となる。しかし、A番目である10
という数字はA番目以外にも存在する。つまり、平均値を計算するので、A番目以外の10
を選択しても最大の平均値となる。今回はA番目と同じ数はvaluesの中に合計で3つ存在する。また、先頭からA番目までの範囲で10
は1つ存在するので、平均値が最大となるには選択する品物の中に10
は1つ含める必要がある。10
の合計数は3つなので、平均値が最大となる選びからは、3C1通り存在することが分る。
今度は以下の例を見てみる
N = 5, A = 2, B = 3
values = {1, 1, 1, 1, 1}
この例の場合では、先頭の数字とA番目の数字が一致している。つまり、選択する全ての数字が同じ数字の場合を考える。A番目の数をVa
と置いた時にvaluesの中でVa
と一致する数の個数をCountVa
とすると、CountVa個の中からi個選択する場合の数CountVa C i
の総和(A <= i <= min(CountVa, B))となる。これは、平均値の性質で全て同じ数字であれば、選択する数を増やしても平均値は変わらないからだ。
パスカルの三角形によって組合せを求める
nCkなどのコンビネーションはパスカルの三角形によって求める事ができる。パスカルの三角形は動的計画法を使うことで計算量O(N2)で作る事ができる。
詳しくは以下を参照。
パスカルの三角形を用いてコンビネーション(組み合わせ)のクラスを実装する - マツシタケイタの技術ブログ(勉強中)
全体の計算量
後者の解法の計算量を考える。
- 配列をソートする → O(NlogN)
- A番目の数と同じ数字を探す → O(N)
- パスカルの三角形を作る → O(N2)
よって全体の計算量はO(N2)となる。Nの最大は50なので間に合う。