AtCoder Beginner Contest 169 解説

C問題

decimalを使えば10進数の小数計算は（28桁まで）誤差なしにできる。使い方を忘れてたので調べた。

from decimal import *

A, B = map(Decimal, input().split())
print(int(A * B))

D問題

p,p^2,p^3,...の順に使うのが最適。

E問題

Aの中央値とBの中央値の間はすべて作れる。奇数個なら1刻み、偶数個なら0.5刻みなので注意。無証明。

F問題

組合せ的な方法があるのかもしれないけど式変形で解いた。dp[いくつ見たか][総和][使った個数]=組合せ数で解けるのは良くて、最終的な答えはすべての$k$に対して$dp[i][j][k] 2^{n-k}$の総和。$ep[i][j][k]=dp[i][j][k]2^{n-k}$と置きなおして漸化式を立てると、

\begin{align}
ep[i][j][k] \to ep[i+1][j][k]
\end{align}

\begin{align}
ep[i][j][k] \to ep[i+1][j + a_i][k + 1] / 2 \\
\end{align}

遷移に$k$を使ってないので$k$は忘れてよくて、$ep[i][j]$だけで解ける。

組合せ的な解　まず部分集合Sを列挙して、さらにSの部分集合Tを列挙する、というのは$3^n$通りの方法がある。n桁の3進数の間に全単射が作れて、

ある要素がTに含まれるとき0
ある要素がSに含まれるとき1
それ以外のとき2

とすればよい。この対応を使えば漸化式を立てることができる。