問題リンク
問題概要
\(N\)要素の数列\(A_i\)が与えられる。
これらのうち2つを選んで得られる\(N(N-1)/2\)個のペアのうち、iとjの差の絶対値が\(A_i + A_j\)に等しいものはいくつあるか。
解法
\(|i-j|=A_i+A_j\)を変形すると
\(i > j\)のとき\(i-j=A_i+A_j\)より\(A_i-i = A_j+j\)
\(j > i\)のとき\(j-i=A_i+A_j\)より\(j-A_j = A_i+i\)
となる。
よって前者の場合はmapでそれまでに\(A_i-i\)が(別のjに対する\(A_j+j\)として)登場した回数を答えに加え、\(A_i+i\)が登場した回数に1加える操作を繰り返すとよい。
後者の場合も同様。
提出
https://atcoder.jp/contests/abc166/submissions/12725826
感想
Dにびっくりして一旦こっちに向かったけど、すぐ思いついてよかった。
