AtCoder Beginner Contest 169

前半の浮動小数点の計算が合わない問題

C問題はdecimalを使うことで解けたけどBが合わない

→なぜかすべての数が2より大きいと思ってN<59などという条件を付けくわえていた…雑なミス

B - Multiplication 2

N個の数が与えられ，その積を求める問題。10^18を超える場合は-1と出力する。

intで計算すれば何とかなる

F - Knapsack for All Subsets

模範解答

1. N, S = map(int,input().split())
2. A = list(map(int,input().split()))
3. mod = 998244353
4. dp = [[0 for j in range(S + 1)] for i in range(N + 1)]
5. dp[0][0] = 1
6. for i in range(N) :
7. for j in range(S + 1) :
8. dp[i + 1][j] += 2 * dp[i][j] # 合計値が変わらない場合については、部分集合に含まれない場合、部分集合の部分集合には含まれない場合の2通り
9. dp[i + 1][j] %= mod
10. if j + A[i] <= S :
11. dp[i + 1][j + A[i]] += dp[i][j]
12. dp[i + 1][j + A[i]] %= mod
13. print(dp[N][S])

i番目まで選んだ時の和がjになるように dp[i][j] を定義し、dp[N][S]まで計算する

i+1番目を加える際、合計値が増えないのが2パターン、増えるのが1パターンあるので順番に足していく