AtCoder Beginner Contest 167 de Problème C (C-Skill Up) de Je n'ai pas vu la vidéo des commentaires. Ou, c'est un article pour ceux qui s'inquiètent s'ils peuvent le comprendre.
J'ai vu le commentaire sur la vidéo, mais je l'ai mis en place pour l'organisation.
La vidéo de commentaire est également très facile à comprendre, donc Veuillez vous y référer également. Le problème C est vers 21h30 à 42h00. La vidéo de commentaire est ici.
** Comment essayer toutes les combinaisons de nombres de 1 à N **.
L'énoncé du problème peut être résumé comme suit.
Il y a M algorithmes que Takahashi veut apprendre, Il existe N livres de référence sur les algorithmes dans la librairie.
Takahashi a un budget pour acheter tous les ouvrages de référence, Si possible, je veux apprendre efficacement et garder le minimum de dépenses.
Dans quel ordre devriez-vous acheter et lire les livres de référence pour économiser le plus d'argent? Trouvez le coût minimum.
** Achetez N livres de référence Essayez toutes les combinaisons **
Il existe des combinaisons «1 << N» pour acheter N livres de référence.
<< est une opération de décalage. "1 << N" signifie décaler 1 vers la gauche de N morceaux.
Les opérations de décalage sont considérées en binaire.
Nombre binaire
0: 0000
1: 0001
2: 0010
3: 0011
4: 0100
5: 0101
6: 0110
7: 0111
8: 1000
Exemple: 1 << 3 Cela signifie décaler 0001 vers la gauche de trois, donc Ce sera 0001000. Par conséquent, il est "8" en décimal.
Par conséquent, si N de N livres vaut "3", la combinaison sera "8 modèles".
Regardez les nombres binaires 0-7 ci-dessus. Si vous faites attention aux 3 chiffres à partir de la droite, vous pouvez voir que tous les motifs sont couverts de 0 à 7.
Pensez à chaque chiffre pour savoir s'il faut acheter chaque livre de référence.
Exemple: quand il y a 3 livres de référence
000-> Cas où vous n'achetez même pas un livre
001-> Le cas où vous achetez le premier livre de référence mais pas le deuxième et le troisième
010-> Le cas où vous achetez le deuxième livre de référence, mais n'achetez pas le premier et le troisième
011-> Achetez les premier et deuxième livres de référence, mais pas le troisième
100-> Un cas où vous achetez le troisième livre de référence, mais n'achetez pas le premier et le deuxième
101-> Un cas où vous achetez les premier et troisième livres de référence, mais pas le deuxième
110-> Un cas où vous achetez les deuxième et troisième livres de référence, mais pas le premier
111-> Cas pour tout acheter
class Main {
public static void main(String[] args) {
int patternCount = 1 << 3;
System.out.printf("patternCount=%d\n", patternCount);
for (int i = 0; i < patternCount; i++) {
System.out.println(Integer.toBinaryString(i));
}
}
}
↑ Il boucle 8 motifs, vous pouvez donc simplement boucler 8 fois. J'ai essayé de sortir 0 à 7 en binaire.
Résultat de sortie
patternCount=8
0
1
10
11
100
101
110
111
Regardons les livres à acheter et les livres à ne pas acheter selon que chaque chiffre en binaire est 1.
S'il s'agit de 001, le premier livre de référence est acheté, mais le deuxième et le troisième ne le sont pas. Si c'est 110, achetez les deuxième et troisième livres de référence, mais pas le premier
C'est comme ça.
En d'autres termes
Lors de l'achat du premier livre, le premier nombre à partir de la droite est 1. Lors de l'achat du deuxième livre, le deuxième nombre à partir de la droite est 1. Lors de l'achat du troisième livre, le troisième chiffre en partant de la droite est 1.
C'est vrai.
Utilisez l'opérateur "&" pour savoir si le chiffre spécifié en binaire est 1.
L'opérateur "&" est défini sur 1 uniquement si les deux chiffres sont 1 dans la représentation binaire.
Exprimons-le en binaire pour une compréhension facile.
1111 & 0001 -> 0001 1111 & 1001 -> 1001 1000 & 1001 -> 1000
De cette manière, il s'agit d'une opération qui compare chaque chiffre des nombres binaires gauche et droit et définit ce chiffre à 1 uniquement lorsque les deux sont 1.
Profitez-en
Ce sera.
class Main {
public static void main(String[] args) {
int n = 3;
System.out.printf("n=%d\n", n);
int patternCount = 1 << n;
System.out.printf("patternCount=%d\n", patternCount);
for (int i = 0; i < patternCount; i++) {
System.out.println(Integer.toBinaryString(i));
for (int j = 0; j < n; j++) {
if ( (i & 1<<j) == 1<<j) {
System.out.printf(" %Achetez le livre de référence dth\n", j + 1);
}
}
}
}
}
↑ De cette manière, vérifiez si chaque chiffre du nombre binaire est 1. Le résultat de sortie est le suivant.
n=3
patternCount=8
0
1
Achetez le premier livre de référence
10
Achetez un deuxième livre de référence
11
Achetez le premier livre de référence
Achetez un deuxième livre de référence
100
Achetez un troisième livre de référence
101
Achetez le premier livre de référence
Achetez un troisième livre de référence
110
Achetez un deuxième livre de référence
Achetez un troisième livre de référence
111
Achetez le premier livre de référence
Achetez un deuxième livre de référence
Achetez un troisième livre de référence
Nous avons maintenant les bases nécessaires pour résoudre ce problème. Essayez tous les modèles pour voir le coût d'achat le plus bas.
Dans le code source suivant, Le problème C est AC.
import java.util.*;
class Main {
final static int INF = 1001001001;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//Stocker les données d'entrée dans des variables
int n = sc.nextInt();
int m = sc.nextInt();
int x = sc.nextInt();
int[][] a = new int[12][12];
int[] c = new int[n];
for (int i = 0; i < n; i++) {
c[i] = sc.nextInt();
for (int j = 0; j < m; j++) {
a[i][j] = sc.nextInt();
}
}
sc.close();
//Répondre=Puisqu'il s'agit de la valeur minimale du coût, initialisez-la avec un grand nombre pour comparer la valeur minimale.
int ans = INF;
//Vérifiez tous les modèles de combinaison
for (int s = 0; s < 1<<n; s++) {
int cost = 0; //Le coût de cette s e combinaison
int[] d = new int[m]; //Compréhension de chaque algorithme dans cette combinaison qc
//Vérifiez si chaque bit est 1 en binaire
for (int i = 0; i < n; i++) {
//Si le i-ème bit à partir de la droite est 1, ajoutez le coût et l'algorithme comme référence à l'achat.
if ( (s & 1<<i) == 1<<i) {
//Ajouter un coût
cost += c[i];
//Ajouter à la compréhension de chaque algorithme
for (int j = 0; j < m; j++) {
d[j] += a[i][j];
}
}
}
//Vérifiez si la compréhension de tous les algorithmes dépasse x
boolean ok = true;
for (int j = 0; j < m; j++) {
if (d[j] < x) ok = false; //Si même un est inférieur à x.
}
//Si la vérification est OK, si le coût met à jour la valeur minimale.
if (ok) ans = Math.min(ans, cost);
}
//Ans reste INF s'il n'y a pas de modèle dans lequel la compréhension de tous les algorithmes dépasse x
if (ans == INF) System.out.println(-1);
else System.out.println(ans);
}
}
Qu'as-tu pensé?
** Essayez toutes les combinaisons de nombres de 1 à N **
Je pense que cette solution peut être utilisée lors de la rencontre d'un tel problème.
fin.
Recommended Posts