題意
- $n$個の正の数字が与えられる。
- 「あなたは好きな要素を$+1$してよい」これを最大で$k$回行える。(すべて別の要素を選んでもよい)
- ある$x$を$y$個作りたいと思ったとき$y$の最大数はいくつか？
こう考えた
例題の通り、$[1,4,8,13]$としよう。まず、ソートする。今回の場合、すでにソートされている。
$+1$しかできないので、ある数字にそろえるとすると、その数より大きい数は小さくできない。つまり、$4$は$+1$を4回行えば$8$になれるが、$8$は操作しても$1$にも$4$にもなれない。
ここで左から順に、それまでの要素をいくつ揃えられるかを考える。例えば、13に合わせるとしよう。kが十分に大きければ$[13,13,13,13]$にできる($k$が本当に大きければ$[14,14,14,14]$などにもできるが、これはyの最大数に意味がない)。
必要な$k$が小さい方から考えると、$[1,4,13,13]$, $[1,13,13,13]$, $[13,13,13,13]$のように、13の一つ左の要素から何個目まで$k$で足りるかを考えるのが良さそうである。また、この時に必要な数は、$(一番右の数 \times 要素の数) - (その区間の和)$ である。わかりやすく考えるなら、$[4,8,13]$を$[13,13,13]$にするのには、$(13-4) + (13-8) + (13-13)$が必要であるが、これは先ほどの式に他ならない。
さて、今回のrは連続区間を求めるものなので、ある要素$l$, $r$番目を選んだ時に$(r-l+1)$を最大と言い換えられる。ここで、$r$を増加させていくと、$l$は必ず減算方向にはいかない。
このため、$l=0$の状態から$r$を引き延ばしていき、各段階で、$l$をどこまで$r$に近づければならないかを考えればよい。
つまり、for rで、lを引き寄せる尺取りをする。
実装
from typing import List, Tuple
from pprint import pprint
class Solution:
def maxFrequency(self, nums: List[int], k: int) -> int:
l = 0
nums.sort()
res = 0
sum = 0
for r in range(len(nums)):
sum += nums[r]
while True:
targetnum = nums[r] * (r - l + 1)
if k < (targetnum - sum):
sum -= nums[l]
l += 1
else:
res = max(res, (r - l + 1))
break
print(res)
return res