Introduction aux algorithmes avec la méthode java-Shakutori

Résumé de l'article

Ceci est une série d'articles que j'ai compilés dans mon étude et mémo. La sixième balle. Cliquez ici pour les articles précédents.

Dans cet article

• • Méthode Shakutori *

Je vais étudier sur. Avec somme cumulée? Est-ce celui qui est utilisé? Je les vois souvent présentés comme un ensemble.

Méthode Shakutori

Comme la somme cumulée, il semble que ce soit une technique pour accélérer les opérations sur un tableau de nombres.

Référence: [[Somme cumulative, méthode shakutori] Illustration d'algorithme que même les débutants peuvent comprendre](https://paiza.hatenablog.com/entry/2015/01/21/%E3%80%90%E7%B4%AF% E7% A9% 8D% E5% 92% 8C% E3% 80% 81% E3% 81% 97% E3% 82% 83% E3% 81% 8F% E3% 81% A8% E3% 82% 8A% E6% B3% 95% E3% 80% 91% E5% 88% 9D% E7% B4% 9A% E8% 80% 85% E3% 81% A7% E3% 82% 82% E8% A7% A3% E3% 82% 8B% E3% 82% A2% E3% 83% AB% E3% 82% B4)

Eh bien ... c'est un peu déroutant si vous regardez le lien. .. .. Je vais l'expliquer pour ma propre étude.

À titre d'exemple, considérons un tableau d'entiers de taille n. Lorsqu'elle est divisée en la longueur t de la section spécifiée à partir de là, quelle est la valeur maximale de la somme dans cette section? C'est un problème pour résoudre un problème typique. C'est un problème qui peut être résolu avec une somme cumulative. Voir également l'article précédent (https://qiita.com/aja_min/items/3a334fb03749d8f42a25).

À titre d'exemple, considérons le cas de la taille 5 (n = 5) et de la longueur de l'intervalle 2 (t = 2).

Considérez la disposition comme indiqué. Si vous divisez cela par la longueur de 2 de la section, ce sera comme suit.

D'après la conclusion, 4 + 10 = 14 de la somme lors du choix du 4e et du 5e est la valeur la plus élevée, mais quel est le montant du calcul jusqu'à présent?

1. Quelle section sélectionner
2. Calcul de la somme dans l'intervalle

Pensons-y séparément.

Tout d'abord, 1. Comment diviser la section, n'est-ce pas? Dans l'exemple ci-dessus, la somme est prise quatre fois. Si vous le déposez dans la formule, ce sera n-t + 1 fois. Cette fois 5-2 + 1 = 4 fois.

Vient ensuite 2. Calcul de la somme dans cet intervalle, qui est traitée deux fois pour accéder à chaque élément du tableau.

En général, c'est (n --t + 1) * t fois. Notez que si t dépend de n, le montant du calcul sera d'environ O (n ^ 2). Dans ce cas, si n est pris comme 10 ^ 5, cela prendra énormément de temps. Dans un tel cas, la méthode Shakutori est introduite.

Eh bien, c'est une histoire relativement simple ... Souvenez-vous de la somme pour ne pas avoir à ajouter de 1 à chaque fois. à propos de ça. Voir la figure ci-dessous.

Comprenez-vous en quelque sorte? En vous rappelant la somme, vous n'avez pas à ajouter tous les éléments t fois à la fois. La quantité de calcul est n-t + 1 fois car nous n'avons plus besoin d'accéder à chaque élément du tableau. Je pense que cela peut être exprimé par O (n).

Passons à l'exemple.

exemple

Exemple: AtCoder --abc032-c "column"

N K
s1 
s2
:
sN

C'est le problème. C'est un peu appliqué. C'est fondamentalement une méthode fragile, mais cette fois, la durée n'a pas été décidée. Il sera mis en œuvre selon la politique suivante.

• Enregistrez le produit de la même manière que la méthode Shakutori.
• Tant que les conditions sont remplies, passez à la bonne extrémité. --Lorsque les conditions ne sont plus remplies, passez à l'extrémité gauche. ――Lorsque l'extrémité gauche se trouve à l'extrême droite, la recherche se termine. La valeur la plus longue à ce moment est sortie.

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(); //Longueur de chaîne entière non négative
		long k = sc.nextLong(); //Produit maximum

		long[] s = new long[n]; //Chaîne entière non négative

		for (int i = 0; i < n; i++) {
			s[i] = sc.nextLong();
			if (s[i] == 0l) {
				System.out.println(n);
				return;
			}
		}

		long seki = 1; //Variables stockant le produit
		int ans = 0; //Longueur maximale
		int ans_max = -1; //Enregistrez la réponse
		int left = 0; //Extrémité gauche
		int right = 0; //Extrémité droite

		for (left = 0; left < n; left++) {

			//Fixez l'extrémité gauche et déplacez l'extrémité droite aussi loin que vous pouvez aller pour multiplier
			while (right < n && seki * s[right] <= k) {
				seki *= s[right++];
			}

			//Stockage de maximum ans
			ans = right - left;
			if (ans_max < ans) {
				ans_max = ans;
			}

			//Déplacez le bord gauche. la gauche==Soyez prudent quand cela devient juste.
			if (left == right) {
				right++;
			} else {
				seki /= s[left];
			}

		}

		System.out.println(ans_max);
	}
}

Oui. J'ai mentionné diverses sources, mais c'était assez difficile. .. L'exemple où la gauche rattrape la droite a été particulièrement difficile. Cela semble également exiger de la pratique. .. .. Pratiquons bien. Je vais lire la source encore et encore.

à plus!