ABC 401-500/ABC417C - Distance Indicators - 競技プログラミング用 知識集積所【8/3更新】

---

問題

ABC417C

必要知識

B以下レベルの内容は省略

• 特になし

考え方

愚直にやってはTLEなので、高速化を考える。

与えられた式

j-i = A[i]+A[j]

を

j-A[j] = i+A[i]

と変形してやると、各jについて、「今までのiの中で、i+A[i]がj-A[j]に一致するものはいくつあるか？」を合計すればいいだけとわかる。

よって、map（未作成）を使って前から順に「i+A[i]は今までどんな値が何個出たか？」を保管していけば、簡単に答えが出る。

解答例

解答例

注意点

答えがint型に入らない場合がある

例えば{3,2,1,0,1,2,3}という数列の場合、i<=4かつj>=4であれば、4でダブる場合を除き全部条件を満たす。
同様な数列を作ると、ほぼ10^10くらいの答えになる場合があり得る。

別解