from 競技プログラミングで解法を思いつくための典型的な考え方 arc060_a https://atcoder.jp/contests/arc060/tasks/arc060_a
- 2^50なので無理
- 2^50通りについてAに一致するか判断するより緩めた方が良い？
- Aは与えられるのでとりあえずAを引いて符号でわける
- でも2^25でも厳し目かな、最悪ケースは2^49だしな
- 2^49について和を求めるのは辛いが、値域は高々50×49なので値域と定義域の交換をしよう
- 和→頻度にすればいいね、頻度表
- 下の頻度表をL、上の頻度表をU、0の個数をZとすればLi×Ri×2^Zだ
- 二つの頻度表の突き合わせ
- 一枚も選ばないケースが含まれるので-1すること
- 計算量
- Nで符号で分割
- N^3でDPで頻度表を作る
- N^2で頻度表の突き合わせ
- 公式解説
- Aを引くことによって目的を「和が0」にし、カードの枚数に関係なくすることがオーダーを減らす手であった
- 「和が0」を僕は2つの頻度表の突き合わせで数えたが、公式解法はまとめてDPして0になるところを見る