AtCoder ABC 162 D - RGB Triplets kの求め方
アルゴリズム部分は書けていたのに計算が出来なくて解けなかった問題。
けんちょんさんが丁寧な解説を書いてくれています。
ただ、一部理解しきれなかったところがあったので、考えたことをメモします。
具体的には
i, j, k が等差数列にならなければならないという制約がついているので、効率よく数えることができる。i と j を固定してあげると、k が自動的に決まるのだ。
よって整理すると、
・i, j (i < j) を固定すると
・k = 2j - i と決まるので (この時点で k >= N の場合はダメ)
・S[i], S[j], S[k] が互いに異なるならばカウントする。
この、kを求める部分がなぜ求められるのかが直感的に分からずACは出来たもののこのままでは次に活かせそうにない。
Twitterで色々な人に助言を貰ってなんとか理解出来た気がする、
j−i != k−j であるということ
きりみんちゃんはそもそも引き算というものを理解できていませんでした。
a - bとは、aとbの差分を出すということである。つまり、a - b == c - dとはa - bとc - dの差分が同じだということになる。
さて、上記をふまえて問題に戻ると、j - i != k - jという制約は、それぞれの差分が異なるということだ。
逆にj - i == k - jであればそれぞれの差分が同じであるということになりそう。
また、3つの数字は異なるという制約もあるため、iとjが定まっている時、kは一意に決まるはずだ。
iとjの差分とjとkの差分が同じであるということは、jとiとjの差分だけ離れている数がkということになる。
これを計算したのがけんちょんさんの解説にあるk = j*2-iという式で、これを更に直感的な式にするとk = j + (j - i)となる。
あとはけんちょんさんの解説の通り、
「S[i], S[j], S[k] が異なる」という条件を満たすものすべてから、
「S[i], S[j], S[k] が異なる」かつ「j - i = k - j である」という条件を満たすものを引く
をすればいい。