Introduction aux algorithmes avec somme cumulée Java

Résumé de l'article

Il s'agit d'une série d'articles que j'ai compilés dans mon étude et mon mémo. Le cinquième. Cliquez ici pour les articles précédents.

# article
4 Introduction aux algorithmes avec java-Recherche (peu de recherche complète)
3 Introduction aux algorithmes avec java-Recherche (recherche avec priorité à la largeur)
2 Introduction aux algorithmes avec java-Recherche (recherche prioritaire en profondeur)
1 Introduction aux algorithmes avec java-Recherche (recherche complète, recherche dichotomisée)

Dans cet article

Je vais étudier sur. Terminons la section d'exploration et étudions un autre algorithme (ce qui vous intéressait dans le concours hebdomadaire).

Somme cumulée

Cela semble être une technique de calcul. Il semble pratique de trouver la somme des sections avec le tableau.

Référence: Etre capable d'écrire la somme cumulée sans réfléchir!

Je vais vous l'expliquer pour le moment.

Séquence a, {1,3,1,4,7,6,1,0,9} Dirons-nous cela? Par exemple, supposons que l'on vous demande de trouver la somme du 3e au 5e de cette séquence.

Méthode normale

a: Ajoutez simplement le 3ème au 5ème de {1,3, ** 1,4,7 **, 6,1,0,9}. La réponse est 1 + 4 + 7 = 12

Utiliser la somme cumulée

En plus de a, créez un tableau b qui stocke la somme jusqu'au i-ième de a. b:{0,1,4,5,9,16,22,23,23,32} Si vous écrivez a_1 comme le premier élément de a, b_1 = 0 (corrigé ici. Les indices seront décalés de un par la suite) b_2 = a_1 = 1 b_3 = a_1 + a_2 = 1 + 3 = 4 b_4 = a_1 + a_2 + a_3 = 1 + 3 + 1 = 5 b_5 = a_1 + ... + a_4 = 1 + ... + 4 = 9 b_6 = a_1 + ... + a_5 = 1 + ... + 7 = 16 ...

Je me sens dit. À ce moment, la somme du 3e au 5e de a est calculée comme suit. b_6 - b_3 = 16 - 4 = 12

Les détails sont les suivants.


  b_6 = a_1 + a_2 + a_3 + a_4 + a_5
-)b_3 = a_1 + a_2
--------------------------------------
      = a_3 + a_4 + a_5

Comprenez-vous en quelque sorte? En sauvegardant la somme dans l'ordre du front, vous n'avez pas à vous soucier d'ajouter 3ème + 4ème + 5ème!

De quoi êtes-vous heureux?

Par exemple, lorsque vous devez trouver la somme de ● à ▲ plusieurs fois (en supposant un problème avec de nombreuses variations de ● et ▲), vous devez retourner la boucle encore et encore de la manière habituelle. Il y en a, mais si vous utilisez la somme cumulée, vous pouvez trouver la somme totale (avec O (1)) en un seul coup.

Regardons le problème.

exemple

Exemple: AtCoder --abc037-c "total"

Cliquez ici pour afficher des phrases de problème et des exemples de saisie
* Veuillez vous référer au lien de problème autant que possible

(Début de section) 【Énoncé du problème】 Étant donné une séquence de longueur N {ai} et un entier K supérieur ou égal à 1 et inférieur ou égal à N. Cette séquence de nombres a N − K + 1 sous-colonnes contiguës de longueur K. Trouvez la somme des valeurs totales dans chacune de ces sous-colonnes.

[Restrictions] Toutes les entrées sont des entiers 1≤K≤N≤10^5 0≤ai≤10^8

【contribution】 L'entrée est donnée à partir de l'entrée standard dans le format suivant.

N K
a1 .. aN

【production】 Sortez la somme des N − K + 1 valeurs totales contenues dans la sous-colonne.

(Fin de la section)


C'est le problème. C'est juste une question de somme cumulative. Vous devez ajouter K pièces N-K + 1 fois. Le montant du calcul est O (K * (N-K + 1)). De plus, si vous faites un mauvais choix (K = N / 2, etc.), vous constaterez que cela coûte O (N ^ 2). Ce n'est pas à temps. C'est pourquoi la somme cumulée entre en jeu. "K additions sont N-K + 1 fois", mais si vous utilisez la somme cumulée, "K additions" peut être fait avec O (1), donc la quantité de calcul est à peu près O (N). ..

La politique est la suivante.

--Préparer un tableau pour contenir la somme cumulée

Ensuite, voici un exemple de réponse.

Main.java



import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int k = sc.nextInt();

		long a[] = new long[n]; //Array pour recevoir des entrées
		long b[] = new long[n + 1]; //Stocker la somme cumulée

		for (int i = 0; i < n; i++) {
			//Recevoir une entrée
			a[i] = sc.nextLong();
		}

		for (int i = 1; i <= n; i++) {
			//Calcul de la somme cumulée
			b[i] = b[i - 1] + a[i - 1];
		}

		long ans = 0; //Stockage des réponses
		for (int i = 0; i < n - k + 1; i++) {
			ans += b[i + k] - b[i];
		}

		System.out.println(ans);
	}
}

... Hmm, c'était difficile à l'indice. .. Surtout, il est difficile de le mettre à 0 au tout début de la somme cumulée.

N'y a-t-il qu'un peu de pratique? Je suis content de connaître le concept et la manière de se penser. Pour le moment, je vais terminer ici. Eh bien ~.

Recommended Posts

Introduction aux algorithmes avec somme cumulée Java
Introduction aux algorithmes avec java-Dictionary Order / Combination Divers Food (Part1)
Introduction aux algorithmes avec la méthode java-Shakutori
Introduction aux algorithmes avec java-Search (recherche prioritaire en profondeur)
Introduction aux algorithmes avec java --Search (recherche de priorité de largeur)
Introduction à web3j
Introduction à Micronaut 1 ~ Introduction ~
[Java] Introduction à Java
Introduction à la migration
Introduction à Java
Introduction à Doma
Introduction à Ratpack (Extra Edition) --Ratpack écrit en Kotlin
Introduction aux algorithmes avec java --Search (bit full search)
Introduction aux algorithmes avec java-Search (recherche complète, recherche de bisection)
Introduction aux fichiers JAR
Somme de Java_1 à 100
Introduction à Ratpack (8) - Session
Introduction à l'arithmétique des bits
Introduction à Ratpack (6) - Promesse
Introduction à Ratpack (9) --Thymeleaf
Comprendre les caractéristiques de Scala en 5 minutes (Introduction à Scala)
Introduction à PlayFramework 2.7 ① Présentation
Introduction à la mise en page Android
Pour déboguer avec Eclipse
Introduction aux modèles de conception (introduction)
Introduction à la programmation pratique
Introduction à la commande javadoc
Introduction à la commande jar
Introduction à Ratpack (2) -Architecture
Introduction au style lambda
Introduction à la commande java
Introduction au développement de Keycloak
Introduction à la commande javac
[Introduction à MVEL] Viser à être le meilleur MVELer au monde
Introduction à Rakefile qui peut être effectuée en 10 minutes environ
Une introduction aux types fonctionnels pour les programmeurs orientés objet dans Elm
Introduction au traitement parallèle + nouvelle unité d'exécution parallèle Ractor dans Ruby
Introduction aux modèles de conception (Builder)
Introduction au développement d'applications Android
Introduction à Ratpack (5) --Json & Registry
Introduction à la métabase ~ Construction de l'environnement ~
Introduction à Ratpack (7) --Guice & Spring
Reportez-vous à enum dans Thymeleaf
(Installation par points) Introduction à Java8_Impression
Introduction aux modèles de conception (composite)
Introduction à Micronaut 2 ~ Test unitaire ~
Introduction à JUnit (note d'étude)
Introduction à Spring Boot ① ~ DI ~
Introduction aux modèles de conception (poids mouche)
[Java] Introduction à l'expression lambda
Introduction à Spring Boot ② ~ AOP ~
Introduction à Apache Beam (2) ~ ParDo ~
Introduction à l'API EHRbase 2-REST
Introduction au prototype de modèles de conception