Toyota Programming Contest 2023 Spring Qual B (AtCoder Beginner Contest 290) E - Make it Palindrome (500)
コンテスト中の考察
全ての文字のペアの和から同じ文字のペアを引くと良さそう
ペアの和は$ \sum_{i=1}^{n} (n-i+1)\left\lfloor\frac{i}{2}\right\rfloor
同じ文字のペアが使われる数はそれぞれの位置を$ l,r (l \lt r)とすると、$ \min(l,n-r)
これを効率的に求める方法が分からなかった
コンテスト後の考察
それぞれの数の登場回数を覚えておく
数列中央から以下を行う
iは左右端からの距離
左の要素について$ 自身の数の登場回数 \times i を答えから引く
右の要素についても同様に行う
左右の要素の値が同じなら更に$ iを引く
左右それぞれの登場回数を1加える
以上で$ \mathcal{O}(N)になる