AtCoder Beginner Contest D - Enough Array Difficulty: 859
Ce thème, somme cumulée + dichotomie
Énoncé du problème (Condition) La somme des valeurs de tous les éléments inclus dans la sous-colonne continue est égale ou supérieure à K. À partir de , vous pouvez voir que la somme cumulée est utilisée, mais comme 1 ≤ N ≤ 100_000, si vous tournez la boucle deux fois, elle devient TLE.
Par conséquent, puisque la somme cumulée est une augmentation monotone, une dichotomie est également utilisée pour réduire la quantité de calcul.
Ruby
ruby.rb
n, k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
acc = 0
x = [0] + a.map{|v| acc += v}
cnt = 0
x.each do |y|
j = x.bsearch_index{|z| z - y >= k}
if j == nil
break
else
cnt += n - j + 1
end
end
puts cnt
accumulate.rb
acc = 0
x = [0] + a.map{|v| acc += v}
La somme cumulée est calculée ici. ** Addenda ** Je l'ai modifié pour le code que vous avez reçu dans les commentaires.
bsearch.rb
j = x.bsearch_index{|z| z - y >= k}
Bien qu'il s'agisse d'une dichotomie, lower_bound dans *** C ++ *** devient bsearch ou bsearch_index dans *** Ruby ***.
Python
python.py
from sys import stdin
def main():
import bisect
import itertools
input = stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))
x = [0] + list(itertools.accumulate(a))
cnt = 0
for z in x:
j = bisect.bisect_left(x, k + z)
if j <= n:
cnt += n - j + 1
print(cnt)
main()
accumulate.py
x = [0] + list(itertools.accumulate(a))
*** Python *** a une fonction appelée ʻaccumulate` qui calcule la somme cumulée.
bisect.py
j = bisect.bisect_left(x, k + z)
C'est une dichotomie, mais utilisez «bisect» ou «bisect_left» «bisect_right». Si le nombre à rechercher est dans le tableau, «bisect» renvoie la position à droite de ce nombre et «bisect_left» renvoie la position à gauche.
for.py
for z in x:
for i in range(n):
Quand j'ai tourné la boucle avec range (), c'était TLE.
| Ruby | Python | |
|---|---|---|
| Longueur du code(Byte) | 238 | 377 |
| Temps d'exécution(ms) | 165 | 101 |
| Mémoire(KB) | 11780 | 14196 |
Site référencé
Recommended Posts