In the above article, the solution method in C ++ is written, and the article that I tried to solve in other languages is introduced, so here I will try to use Java-specific methods as much as possible. However, Java is a language based on C ++, so a similar implementation is possible in C ++ ...
It is a question of the evenness of the product of two integers. It's a basic problem.
In Java, when receiving input, System.in is passed to Scanner and used.
Also, use several methods depending on the type of data received.
--For words, next ()
--nextInt () for integers
--nextLine () for a string (1 line)
This time we are dealing with integers, so we are using nextInt ().
As a side note, when dealing with integers, ʻInteger.parseInt (sc.next ())is faster thannextInt (), or Scanner` is slow in the first place, so people who use their own Scanner method. There seems to be.
If you are interested, please try google.
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
if ((a * b) % 2 == 0)
System.out.println("Even");
else
System.out.println("Odd");
}
}
It is a problem to count "1" in the given three-digit number.
It is a problem dealing with numbers, but since it is easy to solve if it is treated as a character string, next () is used.
It's a string consisting only of "0" and "1", so if you look at the length of the rest of the string without the "0", that's the answer.
Let's replace "0" with "" with replaceAll ().
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
s = s.replaceAll("0", "");
System.out.println(s.length());
}
}
The problem is how many times you can divide several integers at the same time when you divide them by 2 until one of them is not divisible.
The fact that a number is divisible by 2 is the same as the fact that the 1s place is 0 when expressed in binary. In other words, how many times a number is divisible by 2 can be found by examining the number of 0s that continues from the bottom. You can do this for all numbers or values to find the answer for the smallest number that can be divided by two. You can find the number of 0s following the bottom with ʻInteger.numberOfTrailingZeros ()`.
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int bit = 0;
for (int i=0; i<N; i++) {
bit |= sc.nextInt();
}
System.out.println(Integer.numberOfTrailingZeros(bit));
}
}
It is a question of how many ways to pay a certain amount using 500-yen coins, 100-yen coins, and 50-yen coins.
Determine the number of 500-yen coins and 100-yen coins with a for statement, and calculate the number of 50-yen coins by the difference from X. Since the condition of the problem states that X is a multiple of 50, there is no need to consider the case where the number of 50-yen coins becomes a decimal.
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int A = sc.nextInt();
int B = sc.nextInt();
int C = sc.nextInt();
int X = sc.nextInt();
int res = 0;
for (int a=0; a<=A; a++) {
for (int b=0; b<=B; b++) {
int c = (X - a * 500 - b * 100) / 50;
if (c >= 0 && c <= C)
res++;
}
}
System.out.println(res);
}
}
For numbers less than or equal to N, the problem is to find the total number of numbers A or more and B or less.
Here, we will obediently examine the sum of each digit for each value between 1 and N.
It is the while statement that calculates the sum of each digit.
n% 10 adds the least significant value to digSum, and n / = 10 discards the least significant digit.
Decimal numbers are more cumbersome to handle than binary numbers, and I hate them ...
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int A = sc.nextInt();
int B = sc.nextInt();
int sum = 0;
for (int i=1; i<=N; i++) {
int n = i;
int digSum = 0;
while (n > 0) {
digSum += n % 10;
n /= 10;
}
if (digSum >= A && digSum <= B)
sum += i;
}
System.out.println(sum);
}
}
Consider a game in which you have several cards with numbers on them, and two people take them alternately and compete for the total. At this time, the problem is to find out how many numbers the first player can take than the second player.
In order to get the cards that maximize each other's points, we will take the card with the largest number of cards in play. In other words, the cards are sorted in descending order, and the cards are taken alternately from the beginning.
Use ʻArrays.sort ()to sort the arrays. Also, this time we want to sort in descending order, so passComparator.reverseOrder ()as the second argument. By the way, if you want to sortList, use Collections.sort () . Java uses List` more often than arrays, so you may be more likely to use it.
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
Integer a[] = new Integer[N];
for (int i=0; i<N; i++) {
a[i] = sc.nextInt();
}
Arrays.sort(a, Comparator.reverseOrder());
int Alice = 0;
int Bob = 0;
for (int i=0; i<N; i+=2) {
Alice += a[i];
}
for (int i=1; i<N; i+=2) {
Bob += a[i];
}
System.out.println(Alice - Bob);
}
}
When there are several rice cakes of various sizes, it is a question of how many stages of kagami mochi can be made using only rice cakes of different sizes.
Set is useful for problems dealing with non-duplicate numbers.
Set can store any number of objects like List, but duplicates will be ignored.
You can easily find the answer by adding the size of all rice cakes to Set and finally counting the number of data that Set has.
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
Set<Integer> num = new HashSet<>();
for (int i=0; i<N; i++) {
int di = sc.nextInt();
num.add(di);
}
System.out.println(num.size());
}
}
There are 10000 yen bills, 5000 yen bills, and 1000 yen bills, and the problem is to find a combination that makes the total of N and Y yen.
It's a similar problem to Question 4. The solution method is similar, such as using a double for statement.
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int Y = sc.nextInt();
for (int a=0; a<=N; a++) {
for (int b=0; b<=N-a; b++) {
int c = N - a - b;
int total = a * 10000 + b * 5000 + c * 1000;
if (total == Y) {
System.out.println(a + " " + b + " " + c);
return;
}
}
}
System.out.println("-1 -1 -1");
}
}
It is a problem to judge whether a certain character string can be made by concatenating a combination of "dream", "dreamer", "erase", and "eraser".
If you apply the character string from the beginning, the beginning of "dreamerase" will match "dreamer", or the beginning of "dreamererase" will match "dream", so check from the back. From behind, such mistakes do not occur.
Use ʻendsWith ()to find out if one string matches the bottom of another. Of course, there is alsostartsWith ()`, which checks if one string matches the beginning of another.
import java.util.*;
class Main {
static String[] strs = {
"dream",
"dreamer",
"erase",
"eraser"
};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String S = sc.next();
while (true) {
boolean endsWithStr = false;
for (String str: strs) {
if (S.endsWith(str)) {
endsWithStr = true;
S = S.substring(0, S.length() - str.length());
break;
}
}
if (!endsWithStr) {
System.out.println("NO");
break;
}
if (S.length() <= 0) {
System.out.println("YES");
break;
}
}
}
}
I tried to write it, but in fact, I can't pass it with AtCoder in this answer. It's MLE ... Apparently the cause is too much string generation. I made some improvements and made the code without ʻendsWith ()` and it passed, but it's not interesting to put it, so I'll put another solution.
Simply replace each string and delete it. In this method, devise the order of the character strings to be deleted so that accidental deletion does not occur. Delete dreamer before dream, eraser before erase, erase and eraser before dreamer.
[Addition] With this method, you will mistakenly think that a string like "dreameraseer" can be composed of erase and dreamer. When replacing, replace it with an unused character without an empty string, and finally delete that character to get the correct result. Thank you to @ CuriousFairy315 for pointing this out!
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String S = sc.next();
S = S.replaceAll("eraser", "-");
S = S.replaceAll("erase", "-");
S = S.replaceAll("dreamer", "-");
S = S.replaceAll("dream", "-");
S = S.replaceAll("-", "");
if (S.length() == 0)
System.out.println("YES");
else
System.out.println("NO");
}
}
The problem is to start at coordinates (0, 0) and determine if we can be at (xi, yi) at time ti.
If it is possible to reach the target coordinates by the time, you can adjust the time by wandering around, but if you arrive at the target coordinates before the odd time of the time, it will be at the exact time. Note that you cannot be at the desired coordinates.
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int preT = 0;
int preX = 0;
int preY = 0;
for (int i=0; i<N; i++) {
int postT = sc.nextInt();
int postX = sc.nextInt();
int postY = sc.nextInt();
int dt = postT - preT;
int dist = Math.abs(postX - preX) + Math.abs(postY - preY);
if ((dt < dist) || ((dist - dt) % 2 != 0)) {
System.out.println("No");
return;
}
preT = postT;
preX = postX;
preY = postY;
}
System.out.println("Yes");
}
}
I'm a chick who has been in the competition for about a month, so there are likely to be many better solutions. (Please let us know in the comments!)
Java isn't that slow at the moment, but it's still slower than C or C ++ and consumes more memory. In fact, if I wrote the former implementation in C ++, I could pass the 9th question normally. It would be nice if there were relaxation of time and memory restrictions for each language like AOJ, but with AtCoder, all languages are equal.
I feel that using C ++ is the best way to compete with AtCoder. (Of course, it's fun to solve in other languages!) I myself am currently studying C ++ for a competitive professional. If you are a competitive professional other than C ++, let's start C ++ at this time! (What is the recommendation of C ++ in Java articles ...)
Recommended Posts