ABC169 F
サイズ3000の数値の列Aが与えられる。そのすべての部分列Tについて、Tの部分列であって、要素の和が与えられたSであるようなものの個数を数え上げよ、という問題。問題
すべての部分集合について考えると2の3000乗なのでもちろん無理。小さいサンプルデータについてDPで考える。2,2,4とS=4について。
2,2で4になる経路と、4が1個で4になる経路がある。それぞれの経路の太さがどう決まるか考える。
素朴にコードにする
pythonimport numpy as np
P = 998244353
# N = 10
# S = 10
# AS = list(map(int, "3 1 4 1 5 9 2 6 5 3".split()))
N, S = map(int, input().split())
AS = list(map(int, input().split()))
DP = np.zeros((S + 1, N + 1), dtype=np.int64)
DP[0, 0] = 1
# print(DP)
for i in range(N):
for j in range(S + 1):
v = DP[j, i] * 2
if AS[i] <= j:
v += DP[j - AS[i], i]
DP[j, i + 1] = v % P
# print(DP)
print(DP[S, N])サンプルデータに正解したのでサブミットしたが13 TLE
jについてループを回さずにnumpyでまとめて計算することが可能だとは思うけど、考えるのが面倒なのでnumbaで解決
Related Pages
- →atcoder×テストは記憶の手段×人に教える×numba×abc171×質の良い情報源の発見×テストの高速サイクル×気づきの言語化×abc172c×経路に依存しない×順序のない列は多重集合×educational_dp_contest×エンジニアの学び方×学び方→
- →atcoder×atcoder_library_practice_contest×numba×cython×フェニック木×セグメント木×遅延伝搬セグメント木×接尾辞配列×lcp_array×Pythonでの累乗・逆数・階乗・階乗逆数・組み合わせ×中国剰余定理×floor_sum×np.convolve×two_snuke×長整数が速い×dsu×unionfind×最大流×最小費用流×scc×2-sat→
- →座標圧縮×setはメモリ食い×numba×numbaに複雑な型を渡す×numba bisect×numpy.unique×長方形グラフ探索×番兵×numba np.concatenate×csr_matrix×リンクトリスト×mprof×atcoder→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]