Quiz
https://codeforces.com/contest/1159/problem/B
Submission
https://codeforces.com/contest/1159/submission/54048500
実験
- サンプル3を見る
- |i-j| = 3のとき、minは717
- k x 3 <= 717
- k <= 239
- これは答えと一致する
解法
- |i-j|を幅と呼ぶことにする
- 幅を固定した時、minも求まる
- 条件式よりk <= ?なる値が得られる
- k<=?がN本ほど得られるので、それらを重ねたものから答えが求まる
- プログラム的には重ねる行為はminに対応する
- ところで「幅を固定した時のminを求める」これは左右からの累積minを事前計算しておけばO(1)で求められる
- 幅をO(N)で全探索しつつ、その時のminがO(1)で求まるので、O(N)で解くことができました
