AtCoder ABC 080 B&C AtCoder - 080
2015/05/23 Addition of problem name ・ Addition of method for solving C problem in DFS 2015/05/23 Added another solution about DFS solution of C problem (flag management replaced from int [] to bit)
A - Parking
-$ T $ If you park for hours $ T * A $ Yen --$ B $ Yen regardless of parking time $ T $ ――Which is cheaper?
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
-Calculate the sum of each digit of $ X $ -$ mod Determine if the sum of each digit = 0 $
The sum of each digit is calculated by recursion. Isn't while faster?
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
-$ F_1 ・ ・ ・ There are stores up to F_n $ ――The shop is open in 10 ways in the morning and afternoon --Select your store's business hours from $ 2 ^ {10} $ streets to find the one that maximizes your operating profit
As needed
――How do you express the business hours of your store on $ 2 ^ {10} $ street?
There is.
If you turn 1023 times with for to generate a bit array each time, you can generate an array for masking. --0000000000 = $ 1024-0 $ street because it is NG if it is not open at any time
//Create an array from 0000000000 to 1111111111. It can be converted to a binary number by inserting the remainder of 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;
}
}
--Loop for possible business hours of your shop ($ 2 ^ {10} $ street) --Array generation loop for mask --Mask the business hours of one store --Count the time zone that matches the business hours of the store --Get the one with the highest profit
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;
//Create an array from 0000000000 to 1111111111. It can be converted to a binary number by inserting the remainder of 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();
}
}
}
/**
* 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();
}
}
/*
*Look up in DFS
* new int[10] =>joisino memo of the time zone when your sister opens
*/
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 of shop open times
* currentI>=Since it became 10, I decided the time zone to open after filling the joisino Shop.
*Profit calculation
*/
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++;
}
//If it is open at some time, the open flag is ON
if (joisinoShop[k] == 1 && !isOpen) {
isOpen = true;
}
}
/*
*It is NG to not open anywhere
*Minimize profits
*/
if (!isOpen) {
return Integer.MIN_VALUE;
}
res += rieki[j][cnt];
}
return res;
}
//Cost if not opened during currentI time zone
int val1 = recursiveC(shop, rieki, joisinoShop, currentI + 1, shopNum);
//Cost when opening in the currentI time zone
joisinoShop[currentI] = 1;
int val2 = recursiveC(shop, rieki, joisinoShop, currentI + 1, shopNum);
//Drop the open flag for the next search
joisinoShop[currentI] = 0;
return Integer.max(val1, val2);
}
reference: A special feature on how to use bit operations (bit operations)! ~ From mask bit to bit DP ~
--The basic movement is the same as the DFS version. Changed the check method of opening at what time zone --``` new int [10] `` `I didn't need it ...
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();
}
}
/*
*Look up in DFS
* joisinoShop =>joisino For memo to memo the time zone when your sister opens
*/
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 of shop open times
* currentI>=Since it became 10, I decided the time zone to open after filling the joisino Shop.
*Profit calculation
*/
if (currentI >= 10) {
/*
*It is NG to not open anywhere
*Minimize profits
*/
if (joisinoShop == 0) {
return Integer.MIN_VALUE;
}
//Calculate if it is open at some time
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;
}
//Cost if not opened during currentI time zone
int val1 = recursiveCNotUseArray(shop, rieki, joisinoShop, currentI + 1, shopNum);
//Cost when opening during the currentI time zone
joisinoShop = joisinoShop | (1 << currentI);
int val2 = recursiveCNotUseArray(shop, rieki, joisinoShop, currentI + 1, shopNum);
//Drop the open flag for the next search
joisinoShop = joisinoShop ^ (1 << currentI);
return Integer.max(val1, val2);
}
Recommended Posts