It's been over 10 years since I graduated from mathematics When talking to an old friend who started to get interested in programming To be honest, is high school math level knowledge useful for programming? Since it became a topic, I will write down the tips introduced at that time.
We will take up the issue of rudimentary competitive programming as a subject. AtCoder This is the first question of beginner contest26.
The contents are as follows.
Problem statement
A positive even number A is given.
x+y=Positive integer x that is A,Select the one with the maximum x × y among y, and output the value.
input
Input is given from standard input in the following format.
A
On the first line, a positive even number A(2≦A≦100)Is given.
output
Output the maximum value of x × y. Insert a line break at the end of the output.
Input example 1
10
Output example 1
25
x=5, y=When 5, x × y=It becomes 25, which is the maximum value.
Even if you are an experienced programmer, those who are not accustomed to competitive programming (I think it is quite normal) may get ready, but the basis of competitive programming is to think about a method of exploring all without thinking difficult. The power required in competitive programming and practice has many different scopes, so even if you can't do it, don't dent. Haruki Murakami's style is like, "There is no perfect programming. Don't have perfect despair."
Let's get back to the story. Written in Java. (Confirmed to be AC with AtCoder)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int max = 0;
for ( int x = 1; x < n; x++) {
if ( x * (n -x) > max) {
max = x * (n-x);
}
}
System.out.println(max);
return;
}
}
It's a method of honestly investigating one by one.
The answer will be correct and the score will come, but from the viewpoint of the amount of calculation, it is O (n). In other words, as the input size n increases, the execution time increases in proportion to n.
In fact, if you know the formula of this problem ** additive geometric mean **, you can make it O (1). If the input value is always an even number, then x = y = n / 2 is always the answer. If you look closely at the problem statement It says, "A positive even number A is given."
It will be as follows.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(n/2 * n/2);
return;
}
}
Of course, you can still get AC (correct answer). Moreover, in this case, the amount of calculation is O (1), that is, the execution time does not increase proportionally regardless of the number of n. Is it here in terms of a model answer? There shouldn't be many programs that don't care about execution time, so it's an interesting story from a practical point of view.
In fact, when programming at work or as a hobby It can be said that little specialized knowledge of mathematics is required. (Otherwise it is difficult to hire)
However, mathematics is a practical science in modern times, and it is often beneficial to know that you are in the IT society. It is a story.
Recommended Posts