Je pense que le goulot d'étranglement lors de la participation à une programmation compétitive en Java est la limitation du temps d'exécution. Dans certains cas, la plateforme à laquelle je participe prend 20 à 20 fois plus longtemps que C ++ 14 et 4 fois plus longtemps que Python3 (Java8 OpenJDK 1.8.0).
Même si j'ai trouvé la logique pour résoudre le problème, j'ai souvent le sentiment que je ne peux pas le terminer car la réponse n'est pas correcte en raison de la limitation du temps d'exécution.
Par conséquent, je voudrais partager le contenu des problèmes difficiles que j'ai récemment rencontrés et les mesures et politiques pour ces problèmes. C'est une note d'un codeur débutant (pas humble), alors n'hésitez pas à commenter.
- Compte tenu de l'entrée de 2 ou plus de A pairs et de 1 ou plus de nombres naturels A, le centre de l'ensemble pour un nombre impair de nombres à l'exclusion d'un entier A dans chaque ordre d'entrée Sortez les valeurs dans l'ordre. *
- Cependant ・ Il est garanti que A vaut toujours 10 ^ 5 ou moins. -Il est garanti que toutes les entrées sont des entiers. *
- Exemple de traitement: * input *6 (==A) 7 1 4 2 6 9 (Saisie d'un ou plusieurs nombres naturels donnés (donné comme cas de test)) *
output
Cliquez ici pour une description de la médiane https://ja.wikipedia.org/wiki/%E4%B8%AD%E5%A4%AE%E5%80%A4
Du contenu du problème
** - Stocke la valeur saisie dans un tableau numérique (dans Array ou ArrayList). ** ** ** - Supprimer les éléments dans l'ordre de ce tableau. ** ** ** - Trier le tableau. ** ** ** ・ (A / 2) -Sortir la première valeur. ** **
Vous pouvez voir le déroulement du traitement. Cela signifie
-Supprimer les éléments dans l'ordre de ce tableau. -Trier le tableau. ・ (A / 2) -Sortir la première valeur. Il vous suffit d'écrire le processus itératif.
Voici le premier code que j'ai écrit.
Main.java
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
ArrayList<Integer> arr = new ArrayList<>();
for (int i = 0; i < n; i++) {
arr.add(s.nextInt());
}
ArrayList<Integer> arrCopy = (ArrayList<Integer>) arr.clone();
for(int j=0;j<n;j++){
/*★*/ arr.remove(j);
/*★*/ Collections.sort(arr);
System.out.println(arr.get((n / 2) - 1));
/*★*/ arr = (ArrayList<Integer>) arrCopy.clone();
}
}
}
Cependant, ce code dépassera le temps d'exécution dans l'environnement de production. Out car la liste est supprimée, triée et dupliquée pour A fois à la position ★. La classe ArrayList a un nombre variable d'éléments, mais a la propriété qu'elle a tendance à s'exécuter plus lentement que la classe Array.
À propos, le contenu de la tâche était de sortir la valeur médiane de chacun. Et vous devez supprimer les éléments un par un et spécifier la valeur médiane, mais vous ne devez pas utiliser ArrayList. …
En fait, la valeur médiane de ce problème, ** peu importe le nombre d'éléments, il y a deux candidats **.
Par exemple
1，2，3，4，5，6
Étant donné le nombre, même si vous supprimez les nombres un par un de 1 à 6, la valeur médiane sera toujours ** 3 ** ou ** 4 **.
Lorsque 1,2,3 sont supprimés, 4 est la valeur médiane, Lorsque 4,5,6 est supprimé, 3 est déterminé comme valeur médiane.
Voici le code que j'ai écrit après avoir pris cela en compte.
Main.java
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int[] sortedArr = new int[n];
for (int i = 0; i < n; i++) {
sortedArr[i] = s.nextInt();
}
int[]originArr=sortedArr.clone();
Arrays.sort(sortedArr);
int firstNum=sortedArr[(n/2)-1];
int secondNum=sortedArr[n/2];
for(int j=0;j<n;j++){
if(originArr[j]<secondNum){
System.out. println(secondNum);
}
else{
System.out.println(firstNum);
}
}
}
}
Il en va de même jusqu'au point où les nombres saisis sont stockés dans le tableau (bien que la classe du tableau soit différente). Après cela, (n / 2) -stocker les 1er et n / 2ème nombres comme valeurs int, respectivement. Ensuite, il compare le nombre supprimé avec le petit nombre de candidats médians et génère une valeur arbitraire.
Dans ce code, vous n'avez pas à manipuler le tableau dans l'instruction de sortie. Et même en Java, même si les éléments du tableau sont variables, vous pouvez garder la contrainte de temps.
Tout d'abord, dans un premier temps, il est faux de supposer que la valeur médiane de chaque tableau supprimé change dynamiquement. Le facteur qui a fait une telle prémisse est l'impatience que "je dois écrire le code rapidement et le soumettre".
Je pense que la programmation de compétition est un environnement spécial pour les codeurs, et pour la plupart des participants, je dois écrire du code qui fonctionne dans les périodes de compétition difficiles. En d'autres termes, il est facile de s'impatienter car vous voulez écrire du code rapidement.
Pour ceux qui sont habitués dans une certaine mesure (ceux qui peuvent répondre à des questions autres que celles qui ne peuvent répondre qu'à quelques pour cent du total), le temps requis est un facteur plus important pour déterminer le classement des participants que le nombre de réponses correctes à la question. Surtout.
Cependant, dans un environnement contraint, plus lors de la participation à une programmation compétitive telle que Java dans un langage «désavantageux» ・ Ecrire plusieurs processus dans une phrase répétitive, ・ Utilisez des cours pratiques
plutôt que, ・ Examiner les règles pour les réponses ・ Même si des instructions répétées sont utilisées, le traitement qu'elles contiennent est minimisé.
C'est une stratégie importante, qui est également un commandement pour moi, et je voulais la partager cette fois.
C'est tout. Si vous avez des erreurs ou d'autres solutions, veuillez nous en informer dans les commentaires.
Recommended Posts