CODE FESTIVAL 2017 qual C B: Similar Arrays

code-festival-2017-qualc.contest.atcoder.jp

解き方

  • a_m...a_nと似ていて、積が偶数である数列b_m...b_nとしてあり得る数列の個数を、m=n, n-1, ..., 1の順序で考える
    • |a_i - b_i| <= 1より、b_iとして考えられる数字は3つ

github.com