いやぁ、ソート済みのデータって便利ですね。そう思わせるような問題を今日解きました。

A[1],...,A[n]は昇順にソートされた配列です。この時、
A - 2A[j] = A - 3A[k] = 0 (1 二分探索を使ったとしても、O(nlogn)かかります。
条件を満たすものを見つけるには探索が必要二分探索以上に効率的な探索は聞いたことが無いなのにlognという項が出ない
ｱﾙﾙｳｳｴｴ！？！？
どうしたものかと頭をひねりまして諦めムード。教授と雑談してるときに言われた「O(n)ってことは一回見た奴は見ないんじゃね」という言葉でひらめきました。


まず、A[1],...,A[n]を負と正の部分列に分けます。

負:A[1],...,A
正:A[s+1],...,A[n]

A=2A[k]となるようなk(s+1 <= k <=n)に対し、
A[s-1]=2A[t]となるようなtはkより前に存在しないのです。

また
A=2A[k]となるようなk(s+1 <= k <=n)に対し、
A=3A[r]となるようなrもkより前には存在しません。

となると話は簡単です。
重複がない場合、負の部分列をAとして正の部分列でA[j]、A[k]を探すときは、正の部分列はそれぞれ、高々2回しか参照されません。(1回でもいいかも)
重複があったとしても、正の部分列のうち一つの要素が参照される回数は、負の部分列において重複している要素の個数回になり、さらに重複している部分を抜けたら、後は高々2回となるのです。

最悪の場合というのは、負の部分列が1つを除いて全て重複しているとき、A[j]、A[k]の探索各々において、正の部分列のどれかがs-1回参照され、さらに正の部分列の要素の上を全て操作する必要があるようなデータです。参照やその他の操作に関しては定数時間で可能なため、
O(1) * {2 * (n-(s-1)) + s-1}
=O(n+(n-s+1))
<=O(2n)
=O(n)

となり、負から正を探す場合の計算量がO(n)となります。

同様の議論が正から負を探すときも可能であり、こちらもO(n)。
よって全体でO(n)で実行可能となるのです。

ソートによるうまみは計り知れませんね…久しぶりにうおおおおソートしゅごいいいいいいい！！！！と感じました。