shopping

いくつかのステップに分けて書いているので、分からない時は一つだけ読んでまた考えるのも良いと思います。

1

確率論において、確率変数の期待値（きたいち、英: expected value）とは、確率変数のすべての値に確率の重みをつけた加重平均である。 (期待値 - Wikipadia より)

求める期待値は $0 \times ($ 商品が $0$ 個開封される確率 $) + 1 \times ($ 商品が $1$ 個開封される確率 $) + 2 \times ($ 商品が $2$ 個開封される確率 $) + \cdots$ という和になります。

2

Moja くんが注文した商品が一つのみであるとき、その商品が開封されてしまう確率を $p$ とすると開封されてしまう商品の個数の期待値は

$0 \times ($ 商品が $0$ 個開封される確率 $) + 1 \times ($ 商品が $1$ 個開封される確率 $) = 0 \times (1 - p) + 1 \times p = 0 + p = p$

より、商品が開封される確率そのものになります。

Moja くんが複数の商品を注文しているときは各商品について「Moja くんがその商品しか注文しなかった場合」を考えてそれぞれの場合での期待値を合計すれば問題の答えが求まります。よって、Moja くんが注文したそれぞれの商品に対し開封されてしまう確率を計算して合計すれば答えとなります。

3

Moja くんが注文した商品を一つ選び、その重量を $a_i$ とします。その商品が開封される確率を求めるために $b_j$ を全走査して $\displaystyle\max_{1 \leq j \leq n} 1 - \frac{\lvert a_i - b_j \rvert}{b_j}$ を計算すると $\Omega(n)$ の時間計算量が掛かってしまい、$1$ から $m$ までの全ての $i$ に対してこれを行うと $\Omega(mn)$ の時間計算量が掛かってしまうため、2 秒間の実行時間制限に間に合いません。しかし Moja くんの注文した商品を一つずつ見て確率を求めていくことは避けられなさそうです。では、そこは仕方ないとして、各商品が開封される確率を $\Omega(n)$ の時間を掛けずに求めることはできないでしょうか。

4

商品の重量を並べる順番は答えに関係しないので、与えられた重量はそれぞれソートすることができます。

$($整数の比較やコピー等の操作に掛かる時間が $\Theta(1)$ であることを仮定すると、時間計算量 $\Theta(m \log m + n \log n) )$

5

お母さんが商品を開封する確率に含まれる $\displaystyle 1 - \frac{\lvert a_i - b_j \rvert}{b_j}$ は Moja くんが頼んだ商品の重量 $a_i$ とお母さんが頼んだ商品 $b_j$ の「近さ」を表しています。例えば $a_i$ と $b_j$ の差 $\lvert a_i - b_j \rvert$ がとても小さいとき $\displaystyle\frac{\lvert a_i - b_j \rvert}{b_j}$ は $0$ に近くなるため、それを $1$ から引いた値は $1$ に近くなります。

そこで、$\displaystyle\max_{1 \leq j \leq n} (\,\cdots)$ の値は $a_i$ に近い $b_j$ を見るだけで計算できそうです。

6

与えられた $a$ と $b$ は昇順にソートしておきます。すると各 $i$ に対して $\displaystyle 1 - \frac{\lvert a_i - b_j \rvert}{b_j}$ が最大となる $j$ は広義単調増加します。例えば $a_5$ に一番「近い」商品が $b_5$ であったとき、次に $a_6 (\geq a_5)$ に一番「近い」商品を探すために $b_1$ から $b_4$ まで $(\leq b_5)$ を候補に入れる必要はありません。よって $a$ の配列を全走査しつつ「$b$ の配列を今どこまで見たか」という値も持っておくことで、$\Omega(mn)$ の時間計算量を避けることができます。

7

以下の擬似コードの内容を実装します。

$a$ の配列も $b$ の配列も前から後ろまで一度しか走査されないのでループの部分の時間計算量は $\Theta(m+n)$ です。配列をソートする必要があるため、全体の時間計算量は $\Theta(m \log m + n \log n)$ となります。