技術室奥プログラミングコンテスト#4 Day2：D - 新入生歓迎数列 2

問題
解法
解答

問題

https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_d

解法

与えられた条件式を整理すると，

2 * A_x == P + Q

2 * (A_y + A_z) == P - Q

となる (x, y, z) の組を見つければよいと分かる．前者は自明に判定できるので，後者を見つける方法を考える．A を後ろから見ていく．A_i を A_y と見たとき，A_z となりうる数は P - Q - A_i であるから A_(i + 1) ~ A_N の中で P - Q - A_i である数の個数が分かれば (y = i, z) の組の個数は求まる．これは std::map を用いれば各数の出現回数を管理することができる．このようにして (y = i, z) の組を各 i について求め，後ろから累積和を取っておく．最後に，A_i * 2 == P + Q となる A_i が出てきたら x = i とし，i + 1 番目以降にある (y, z) の組の個数の和を答えに加算すればよい．O(NlogN)．