観察

配列 \(A = (1, 2, 3)\) が与えられた時 、\(K\) 回操作したときの \(ans\) はどうなるでしょうか？（ \(ans\) が達成される \(A\) の一例も挙げますが、一例であることに注意してください）

• \(K = 1\) では \(A = (2, 2, 3)\) で \(ans = 2\)
• \(K = 2\) では \(A = (3, 2, 3)\) で \(ans = 2\)
• \(K = 3\) では \(A = (3, 4, 3)\) で \(ans = 3\)
• \(K = 4\) では \(A = (4, 4, 3)\) で \(ans = 3\)
• \(K = 5\) では \(A = (4, 4, 6)\) で \(ans = 4\)

このように \(K\) に対して \(ans\) が「単調増加」であるような性質があります。これを「解が単調」などと呼ぶことがあります。

解の二分探索

「解が単調」である問題では、しばしば 解の二分探索 が有用です。 \(ans\) を直接求めるのではなく、「 \(ans\) を \(X\) 以上にすることが可能ですか？」という質問で解を二分探索することで、解を特定するというテクニックです。

これは多くの問題において、いわゆる「 \(ans\) を \(X\) 以上にすることが可能ですか？」などの 判定問題 のほうが解くほうが（直接元の問題を解くより）簡単であることが多いことを利用しています。

判定問題を解く

今回の問題で解くべき判定問題は

「（ \(K\) 回の操作で）\(ans\) を \(X\) 以上にできるか？」

です。これは

「 \(ans\) を \(X\) 以上にするのに、必要な操作回数は \(K\) 回以下か？」

と同じことですし、

「すべての要素を \(X\) 以上にするのに、必要な操作回数は \(K\) 回以下か？」

と同じことです。

---

最後の問題であれば簡単に解けます。すべての \(i ~(1 \le i \le N)\) について

• \(A_i \ge X\) のとき、 \(0\)
• \(A_i\lt X\) のとき、 \(\displaystyle \Big\lceil \frac{X - A_i}{i} \Big\rceil\)

を足したものが最小の操作回数です。これが \(K\) 以下か判定すればよいです。

解法

今回であれば、必ず \(ans\) は \(1\) 以上になります。また \(A_1 + K + 1\) 未満です。（ \(A_1\) に \(K\) 回すべて操作を行っても届かないためです）よって、この範囲で解の二分探索をすればよいです。

上の判定問題の計算量は \(O(N)\) です。判定問題を \(O( \log (A_1 + K))\) 回解けばよいので、計算量は \(O(N \log(A_1 + K))\) となります。

実装例

n, k = map(int, input().split())
a = [0] + list(map(int, input().split())) # 1-indexed で扱えるようにする

def isok(x):
    # ans を x 以上にすることができますか？
    nk = 0
    for i in range(1, n + 1):
        if a[i] < x:
            nk += (x - a[i] + i - 1) // i # ceil((x - a[i]) / i)
            if nk > k:
                return False
    return True

ok = 1
ng = a[1] + k + 1

while ng - ok > 1:
    m = (ok + ng) // 2
    if isok(m):
        ok = m
    else:
        ng = m

print(ok)

注意

• ceil を小数で計算しようとすると、その精度によっては WA となります。基本的には整数範囲で行うことを意識するよいでしょう。

• overflow も注意してください。 ng も実装方針によってはしますし、判定問題内の nk の overflow は気が付きにくいです。