[JAVA] ABC --080- A & B & C

AtCoder ABC 080 B&C AtCoder - 080

2015/05/23 Ajout du nom du problème ・ Ajout de la solution du problème C dans DFS 2015/05/23 Ajout d'une autre solution sur la solution DFS du problème C (gestion des indicateurs remplacée de int [] à bit)

A - Parking

• $ T $ Si vous vous garez pendant des heures $ T * A $ Yen
• $ B $ Yen quelle que soit l'heure de stationnement $ T $ ――Quel est le moins cher?

	private void solveA() {
		Scanner scanner = null;
		int numN = 0;
		int numA = 0;
		int numB = 0;

		try {
			scanner = new Scanner(System.in);
			numN = scanner.nextInt();
			numA = scanner.nextInt();
			numB = scanner.nextInt();

			System.out.println(Math.min(numA * numN, numB));

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

B - Harshad Number

-Calculer la somme de chaque chiffre de $ X $

• $ mod Détermine si la somme de chaque chiffre = 0 $

La somme de chaque chiffre est calculée par récursivité. N'est-ce pas plus rapide?

	private void solveB() {
		Scanner scanner = null;
		int numN = 0;

		try {
			scanner = new Scanner(System.in);
			numN = scanner.nextInt();

			int res = addAllDigit(numN);

			if (numN % res == 0) {
				System.out.println("Yes");
			} else {
				System.out.println("No");

			}

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

	private int addAllDigit(int num) {
		if (num < 10) {
			return num;
		}
		return addAllDigit(num / 10) + num % 10;
	}

C - Shopping Street

version d'utilisation du masque de bits

• $ F_1 ・ ・ ・ Il y a des magasins jusqu'à F_n $ ――Le magasin est ouvert de 10 façons le matin et l'après-midi
• Sélectionnez les heures d'ouverture de votre magasin parmi les rues de 2 $ ^ {10} $ pour trouver celle qui maximise votre bénéfice d'exploitation

Comme requis

――Comment exprimez-vous les heures d'ouverture de votre magasin sur la rue $ 2 ^ {10} $?

Il y a.

Si vous tournez 1023 fois avec for pour générer un tableau de bits à chaque fois, vous pouvez générer un tableau pour le masquage. --0000000000 = 1024-0 $ rue car elle est NG si elle n'est pas ouverte à tout moment

Code du masque

		//Créez un tableau de 0000000000 à 1111111111. Il peut être converti en un nombre binaire en ajoutant un reste de 2.
		for (int i = 1; i < 1024; i++) {
			int[] myShop = new int[10];
			int wkBit = i;
			for (int j = 0; j < 10; j++) {
				myShop[j] = wkBit % 2;
				wkBit /= 2;
			}
		}

Code du corps de la réponse à la question C

• Bouclez les heures d'ouverture possibles de votre boutique (2 $ ^ {10} $ rue)
• Boucle de génération de séquence de masque --Masquer les heures d'ouverture d'un magasin
• Comptez le fuseau horaire correspondant aux heures d'ouverture du magasin --Acquérir celui avec le profit maximum

	private void solveC() {
		Scanner scanner = null;
		int numN = 0;

		try {
			scanner = new Scanner(System.in);
			numN = scanner.nextInt();

			int[][] shop = new int[numN][10];
			int[][] rieki = new int[numN][11];

			for (int j = 0; j < numN; j++) {
				for (int k = 0; k < 10; k++) {
					shop[j][k] = scanner.nextInt();
				}
			}

			for (int j = 0; j < numN; j++) {
				for (int k = 0; k < 11; k++) {
					rieki[j][k] = scanner.nextInt();
				}
			}
			int res = Integer.MIN_VALUE;
			//0000000000=0、1111111111=1023
			for (int i = 1; i < 1024; i++) {
				int wkRes = 0;
				int[] myShop = new int[10];
				int wkBit = i;
				//Créez un tableau de 0000000000 à 1111111111. Il peut être converti en un nombre binaire en ajoutant un reste de 2.
				for (int j = 0; j < 10; j++) {
					myShop[j] = wkBit % 2;
					wkBit /= 2;
				}
				for (int j = 0; j < shop.length; j++) {
					int cnt = 0;
					for (int k = 0; k < myShop.length; k++) {
						if (myShop[k] == shop[j][k] && myShop[k] == 1) {
							cnt++;
						}
					}
					wkRes += rieki[j][cnt];
				}
				res = Math.max(res, wkRes);
			}

			System.out.println(res);

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

Version DFS

	/**
	 * DFS
	 */
	private void solveC3() {

		try (Scanner scanner = new Scanner(System.in)) {

			int numN = scanner.nextInt();

			int[][] shop = new int[numN][10];
			int[][] rieki = new int[numN][11];

			for (int j = 0; j < numN; j++) {
				for (int k = 0; k < 10; k++) {
					shop[j][k] = scanner.nextInt();
				}
			}

			for (int j = 0; j < numN; j++) {
				for (int k = 0; k < 11; k++) {
					rieki[j][k] = scanner.nextInt();
				}
			}
			/*
			 *Rechercher dans DFS
			 * new int[10] =>joisino mémo du fuseau horaire à l'ouverture de votre sœur
			 */
			int res = recursiveC(shop, rieki, new int[10], 0, numN);

			System.out.println(res);

		}
	}

	private int recursiveC(int[][] shop, int[][] rieki, int[] joisinoShop, int currentI, int shopNum) {

		/*
		 *10 types d'horaires d'ouverture des magasins
		 * currentI>=Depuis qu'il est devenu 10, j'ai décidé le fuseau horaire pour ouvrir après avoir rempli la boutique joisino.
		 *Calcul des bénéfices
		 */
		if (currentI >= 10) {
			int res = 0;
			for (int j = 0; j < shop.length; j++) {
				int cnt = 0;
				boolean isOpen = false;
				for (int k = 0; k < 10; k++) {
					if (shop[j][k] == 1 && joisinoShop[k] == 1) {
						cnt++;
					}
					//S'il est ouvert à un moment donné, le drapeau ouvert est activé
					if (joisinoShop[k] == 1 && !isOpen) {
						isOpen = true;
					}
				}
				/*
				 *C'est mal de ne pas ouvrir nulle part
				 *Minimisez les profits
				 */
				if (!isOpen) {
					return Integer.MIN_VALUE;
				}
				res += rieki[j][cnt];
			}
			return res;
		}
		//Coût si non ouvert pendant le fuseau horaire actuelI
		int val1 = recursiveC(shop, rieki, joisinoShop, currentI + 1, shopNum);
		//Coût lors de l'ouverture dans le fuseau horaire actuelI
		joisinoShop[currentI] = 1;
		int val2 = recursiveC(shop, rieki, joisinoShop, currentI + 1, shopNum);
		//Supprimez le drapeau ouvert pour la prochaine recherche
		joisinoShop[currentI] = 0;
		return Integer.max(val1, val2);

	}

Gestion des indicateurs DFS + par bit

référence: Une fonction spéciale sur la façon d'utiliser l'arithmétique des bits (arithmétique des bits)! ~ Du bit de masque au bit DP ~

• Le mouvement de base est le même que la version DFS. Modification de la méthode de vérification d'ouverture à quel fuseau horaire --``` new int [10] `` `Je n'en avais pas besoin ...

	private void solveC3() {

		try (Scanner scanner = new Scanner(System.in)) {

			int numN = scanner.nextInt();

			int[][] shop = new int[numN][10];
			int[][] rieki = new int[numN][11];

			for (int j = 0; j < numN; j++) {
				for (int k = 0; k < 10; k++) {
					shop[j][k] = scanner.nextInt();
				}
			}

			for (int j = 0; j < numN; j++) {
				for (int k = 0; k < 11; k++) {
					rieki[j][k] = scanner.nextInt();
				}
			}
			/*
			 *Rechercher dans DFS
			 * joisinoShop =>joisino Pour mémo pour mémoriser le fuseau horaire lorsque votre sœur ouvre
			 */
			int res = recursiveCNotUseArray(shop, rieki, 0, 0, numN);

			System.out.println(res);

		}
	}

	private int recursiveCNotUseArray(int[][] shop, int[][] rieki, int joisinoShop, int currentI, int shopNum) {

		/*
		 *10 types d'horaires d'ouverture des magasins
		 * currentI>=Depuis qu'il est devenu 10, j'ai décidé le fuseau horaire pour ouvrir après avoir rempli la boutique joisino.
		 *Calcul des bénéfices
		 */
		if (currentI >= 10) {
			/*
			 *C'est mal de ne pas ouvrir nulle part
			 *Minimisez les profits
			 */
			if (joisinoShop == 0) {
				return Integer.MIN_VALUE;
			}
			//Calculez s'il est ouvert à un moment donné
			int res = 0;
			for (int j = 0; j < shop.length; j++) {
				int cnt = 0;
				for (int k = 0; k < 10; k++) {
					if (shop[j][k] == 1 && (joisinoShop & (1 << k)) > 0) {
						cnt++;
					}
				}
				res += rieki[j][cnt];
			}
			return res;
		}
		//Coût si non ouvert pendant le fuseau horaire actuelI
		int val1 = recursiveCNotUseArray(shop, rieki, joisinoShop, currentI + 1, shopNum);
		//Coût lors de l'ouverture pendant le fuseau horaire I actuel
		joisinoShop = joisinoShop | (1 << currentI);
		int val2 = recursiveCNotUseArray(shop, rieki, joisinoShop, currentI + 1, shopNum);
		//Supprimez le drapeau ouvert pour la prochaine recherche
		joisinoShop = joisinoShop ^ (1 << currentI);
		return Integer.max(val1, val2);

	}