ABC417のC問題 Distance Indicators
目次
AtCoder Beginner Contest 417に参加しましたが、C問題 Distance Indicatorsを正解することが出来ませんでした。式を変形して二重ループを無くすところまでは出来たのですが、最後のひと工夫が足りませんでした。そこで、解説を参考に再挑戦してみました。
C - Distance Indicators
数列\(A\)が与えられるので、\(j-i = A_i + A_j\)が成り立つ組み合わせの数を答える問題。
考え方
\(j-i\)と\(A_i+A_j\)と考えると二重ループになり、制限時間をオーバーすることが目に見えます。そこで、式を\(j-A_j = i+A_i\)と変形して、\(j-A_j\)と\(i+A_i\)に分けます。そして、それぞれを個別に計算して、同じ値となる組を見つけます。
ただし\((i,j)\)の組み合わせは、\(j \gt i\)という条件があるので、\(i=j\)の場合を除く必要があります。しかし、この場合は、\(j-i=0\)となりますが、\(A_i \gt 1\)という制約があるので\(2A_i \ge 2\)となるので\(i-i = A_i + A_i\)が成り立つ心配はありません。
また、\(i+A_i \ge 2\)のため、\(j-A_j \lt 2\)は、候補から外れます。
技術的工夫
配列中に含まれる指定値の個数は、Array.count()で数えることが出来ます。しかし、毎回\(j-A_j\)と等しい\(i+A_i\)を探していると制限時間を超えてしまいました。そこで、事前に\(i+A_i\)の値に対する個数を数えて辞書化しておくことで効率化します。
N = int(input())
A = list(map(int, input().split()))
Aj = []
for j in range(N):
a = j - A[j]
if a >= 2:
Aj.append(a)
Ai_count = {}
for i in range(N):
a = i + A[i]
if a in Ai_count:
Ai_count[a] += 1
else:
Ai_count[a] = 1
count = 0
for x in Aj:
if x in Ai_count:
count += Ai_count[x]
print(count)