問題概要
$N$ 項からなる数列 $\{ A_i \}$ がある．意味がある（i.e. 使う範囲が配列外参照をしない）添字 $i$ 全てについて，$A$ の $i$ 項目からの連続する $K$ 項の積より，$i + 1$ 項目からの連続する $K$ 項の積が大きくなっているかどうかを判定せよ．
制約
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq K \leq N - 1$
- $1 \leq A_i \leq 10^9$
解法
まず，積を愚直に計算したりすると次のいずれかの理由でしにます．
- オーバーフローしてこわれる
- 桁数が大きくなりすぎて多倍長整数演算が重くなって TLE
何も考えずに書いたときにどっちになるかは言語によると思いますが，いずれにせよもう少し賢くやる必要があります．
$i$ 項目からの $K$ 項と $i + 1$ 番目からの $K$ 項を書き下して比較してみると，
\begin{align*}
A_i \times A_{ i + 1 } &\times A_{ i + 2 } \times \dots \times A_{ K - 1 } \\
A_{ i + 1 } &\times A_{ i + 2 } \times \dots \times A_{ K - 1 } \times A_K
\end{align*}
のようになっていて，先頭・末尾での入れ替わり以外は同一であることが分かります．よって，この 2 つの範囲の積の大小は，$A_i$ と $A_K$ の大小で決まるので，意味のある $i$ について $K$ 項離れた要素動詞を比較して大小関係を見てあげればよいです．
この処理は数列の長さの線形でできるので $O( N )$ 時間で完了します．
コード
main = do [ n, k ] <- readInts as <- readInts mapM_ putStrLn $ map ( which "Yes" "No" ) $ zipWith (<) as ( drop k as )
