AtCoder Beginner Contest 167 of C problem (C-Skill Up) of I haven't seen the explanation video. Or, it is an article for those who have seen but are worried whether they understood it.
I saw the commentary on the video, but I've put it together for organization.
The explanation video is also very easy to understand, so Please refer to that as well. C problem is around 21:30 to 42:00. The explanation video is here.
** How to try all combinations of numbers from 1 to N **.
The problem statement can be summarized as follows.
There are M algorithms that Takahashi wants to learn, There are N algorithm reference books in the bookstore.
Takahashi has a budget to buy all the reference books, If possible, I want to learn efficiently and keep the minimum expense.
In what order should you buy and read the reference books to save the most money? Find the minimum cost.
** Buy N reference books Try all combinations **
There are "1 << N" combinations for purchasing N reference books.
<< is a shift operation. "1 << N" means to shift 1 to the left by N pieces.
The shift operation is considered in binary.
Binary number
0: 0000
1: 0001
2: 0010
3: 0011
4: 0100
5: 0101
6: 0110
7: 0111
8: 1000
Example: 1 << 3 It means to shift 0001 to the left by three, so It will be 0001000. Therefore, it is "8" in decimal.
Therefore, if N of N books is "3", the combination will be "8 patterns".
Look at the binary numbers 0-7 above. If you pay attention to the 3 digits from the right, you can see that all patterns are covered by 0 to 7.
Think of each of these digits as whether to buy each reference book.
Example: When there are 3 reference books
000-> Case where you do not buy even one book
001-> The case where you buy the first reference book but not the second and third
010-> The case where you buy the second reference book but not the first and third
011-> Buy the first and second reference books, but not the third
100-> The case where you buy the third reference book but not the first and second
101-> A case where you buy the first and third reference books, but not the second
110-> Buy the second and third reference books, but not the first
111-> Case to buy all
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));
}
}
}
↑ It loops 8 patterns, so you can simply loop 8 times. I tried to output 0 to 7 in binary.
Output result
patternCount=8
0
1
10
11
100
101
110
111
Let's look at books to buy and books not to buy depending on whether each digit in binary is 1.
If it is 001, the first reference book is bought, but the second and third are not. If it is 110, buy the second and third reference books, but not the first
It's like that.
In other words
When buying the first book, the first number counting from the right is 1. When buying the second book, the second number counting from the right is 1. When buying the third book, the third number from the right is 1.
That's right.
Use the "&" operator to find out if the digit specified in binary is 1.
The "&" operator is set to 1 only if both digits of each digit are 1 in the binary representation.
Let's express it in binary for easy understanding.
1111 & 0001 -> 0001 1111 & 1001 -> 1001 1000 & 1001 -> 1000
In this way, it is an operation that compares each digit of the left and right binary numbers and sets that digit to 1 only when both are 1.
Take advantage of this
--To find out if you bought the first book, check if the result of & with 001 is 001 --To find out if you bought a second book, check if the result of & on 010 is 010 --To find out if you bought a third book, check if the result of & with 100 is 100
It will be.
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(" %Buy the dth reference book\n", j + 1);
}
}
}
}
}
↑ In this way, check whether each digit of the binary number is 1. The output result is as follows.
n=3
patternCount=8
0
1
Buy the first reference book
10
Buy a second reference book
11
Buy the first reference book
Buy a second reference book
100
Buy a third reference book
101
Buy the first reference book
Buy a third reference book
110
Buy a second reference book
Buy a third reference book
111
Buy the first reference book
Buy a second reference book
Buy a third reference book
Now we have the foundation to solve this problem. Try all the patterns to see the lowest purchase cost.
In the source code below, C problem is AC.
import java.util.*;
class Main {
final static int INF = 1001001001;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//Store input data in a variable
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();
//Answer=Since it is the minimum cost value, initialize it with a large number for comparison of the minimum value.
int ans = INF;
//Check all combination patterns
for (int s = 0; s < 1<<n; s++) {
int cost = 0; //The cost of this s th combination
int[] d = new int[m]; //Understanding of each algorithm in this sth combination
//Check if each bit is 1 in binary
for (int i = 0; i < n; i++) {
//If the i-th bit from the right is 1, add the cost and algorithm as a reference book to purchase.
if ( (s & 1<<i) == 1<<i) {
//Add cost
cost += c[i];
//Add to the understanding of each algorithm
for (int j = 0; j < m; j++) {
d[j] += a[i][j];
}
}
}
//Check if the comprehension of all algorithms exceeds x
boolean ok = true;
for (int j = 0; j < m; j++) {
if (d[j] < x) ok = false; //If even one is less than x.
}
//If the check is OK, whether the cost updates the minimum value.
if (ok) ans = Math.min(ans, cost);
}
//Ans remains INF if there is no pattern in which the comprehension of all algorithms exceeds x
if (ans == INF) System.out.println(-1);
else System.out.println(ans);
}
}
What did you think?
** Try all combinations of numbers from 1 to N **
I think that this solution can be used when encountering such a problem.
end.
Recommended Posts