Ex - Dice Sum 2 Editorial by kyopro_friends


公式解説の最初の部分を確率母関数を陽に使わずに説明します(本質的には同じです)。

確率変数 \(X\) の期待値を \(E[X]\) と表すものとします。

サイコロ \(i\) の出目を表す確率変数を\(X_i\) とします。求める値は \(E[(\sum_{i=1}^{K}X_i)^2]\) です。これは期待値の線形性などから

\(\displaystyle E\left[\left(\sum_{i=1}^{K}X_i\right)^2\right]\\ =\sum_{i=1}^{K}E[X_i^2] +\sum_{i\neq j}E[X_i]E[X_j]\\ =\sum_{i=1}^{K}E[X_i^2] + \left(\sum_{i=1}^{K}E[X_i]\right)^2-\sum_{i=1}^{K}E[X_i]^2\\ =\left(\sum_{i=1}^{K}E[X_i]\right)^2+ \sum_{i=1}^{K}(E[X_i^2]-E[X_i]^2)\)

と変形することができます。よって \(x_i=E[X_i], \ y_i=E[X_i^2]-E[X_i]^2-C_i\) とすることで、公式解説同様、\((\sum x)^2+\sum y\) を最大化する問題に帰着することができました。

公式解説のように確率母関数を使うと \(\sum_{i\neq j}E[X_i]E[X_j]=\left(\sum_{i=1}^{K}E[X_i]\right)^2-\sum_{i=1}^{K}E[X_i]^2\) というテクい変形を行うことなく、機械的に処理することができるところに嬉しさがありますが、積の和に関するこの変形は低難易度帯でもしばしば登場するため(例:ABC177C)、Ex問題に挑むレベルであればよく慣れ親しんでいるものと思います。

posted:
last update: