B - The Number of Products

Quiz

https://codeforces.com/contest/1215/problem/B

Submission

https://codeforces.com/contest/1215/submission/62082416

解法

  • dpのようにi番目まで考えた時の ansP (正の組み合わせ数) を考える
  • A[]の値は+1, -1に単純化しておく
  • 前から i まで見ていった時、全部かけた場合の符号が決まる
  • 今、iを見ているとして、そこの符号と、それまでに出てきた同じ符号の数を見れば、足す数が決まる
  • (Aからbalが決まり、balからsが決まり、sからansPが決まる)

画像イメージ

f:id:peroon:20191008065801p:plain f:id:peroon:20191008065659p:plain