AtCoder ABC 080 B&C AtCoder - 080
2015/05/23 Hinzufügen des Problemnamens ・ Hinzufügen der Lösung des C-Problems in der DFS 2015/05/23 Eine weitere Lösung zur DFS-Lösung des C-Problems wurde hinzugefügt (Flag-Verwaltung von int [] in Bit ersetzt).
A - Parking
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
Die Summe jeder Ziffer wird durch Rekursion berechnet. Ist das nicht schneller?
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
Wie benötigt
――Wie drücken Sie die Geschäftszeiten Ihres Geschäfts in der Straße $ 2 ^ {10} $ aus?
Es gibt.
Wenn Sie 1023 Mal mit for drehen, um jedes Mal ein Bit-Array zu generieren, können Sie ein Array zum Maskieren generieren. --0000000000 = $ 1024-0 $ Straße, weil es NG ist, wenn es zu keinem Zeitpunkt geöffnet ist
//Erstellen Sie ein Array von 0000000000 bis 1111111111. Es kann durch Hinzufügen eines Restes von 2 in eine Binärzahl umgewandelt werden.
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;
}
}
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;
//Erstellen Sie ein Array von 0000000000 bis 1111111111. Es kann durch Hinzufügen eines Restes von 2 in eine Binärzahl umgewandelt werden.
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();
}
}
/*
*In DFS nachschlagen
* new int[10] =>joisino memo der zeitzone, in der deine schwester öffnet
*/
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 Arten von Ladenöffnungszeiten
* currentI>=Da es 10 wurde, entschied ich mich, die Zeitzone zu öffnen, nachdem ich den Joisino-Laden gefüllt hatte.
*Gewinnberechnung
*/
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++;
}
//Wenn es irgendwann geöffnet ist, ist das offene Flag eingeschaltet
if (joisinoShop[k] == 1 && !isOpen) {
isOpen = true;
}
}
/*
*Es ist NG, nirgendwo zu öffnen
*Gewinne minimieren
*/
if (!isOpen) {
return Integer.MIN_VALUE;
}
res += rieki[j][cnt];
}
return res;
}
//Kosten, wenn nicht während der aktuellen Zeitzone geöffnet
int val1 = recursiveC(shop, rieki, joisinoShop, currentI + 1, shopNum);
//Kosten beim Öffnen in der aktuellen Zeitzone
joisinoShop[currentI] = 1;
int val2 = recursiveC(shop, rieki, joisinoShop, currentI + 1, shopNum);
//Löschen Sie die offene Flagge für die nächste Suche
joisinoShop[currentI] = 0;
return Integer.max(val1, val2);
}
Referenz: Eine Besonderheit zur Verwendung der Bitarithmetik (Bitarithmetik)! ~ Von Maskenbit zu Bit DP ~
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();
}
}
/*
*In DFS nachschlagen
* joisinoShop =>joisino Damit Memo die Zeitzone notiert, in der sich Ihre Schwester öffnet
*/
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 Arten von Ladenöffnungszeiten
* currentI>=Da es 10 wurde, entschied ich mich, die Zeitzone zu öffnen, nachdem ich den Joisino-Laden gefüllt hatte.
*Gewinnberechnung
*/
if (currentI >= 10) {
/*
*Es ist NG, nirgendwo zu öffnen
*Gewinne minimieren
*/
if (joisinoShop == 0) {
return Integer.MIN_VALUE;
}
//Berechnen Sie, ob es irgendwann geöffnet ist
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;
}
//Kosten, wenn nicht während der aktuellen Zeitzone geöffnet
int val1 = recursiveCNotUseArray(shop, rieki, joisinoShop, currentI + 1, shopNum);
//Kosten beim Öffnen während der aktuellen I-Zeitzone
joisinoShop = joisinoShop | (1 << currentI);
int val2 = recursiveCNotUseArray(shop, rieki, joisinoShop, currentI + 1, shopNum);
//Löschen Sie die offene Flagge für die nächste Suche
joisinoShop = joisinoShop ^ (1 << currentI);
return Integer.max(val1, val2);
}
Recommended Posts