I actually experienced an engineer's sports "competition programming"
"Competition programming"Is a competition that fights the speed of preparing a program to solve the questions to be presented within the time limit,Solving puzzles using programming SportsIt is sometimes expressed as a competition. In this time I tried to set up an environment to participate in the competition programming and solve the past question of the contest.
AtCoder
http://atcoder.jp/
This timeAtCoderI use a site called.top pageAccess ", and click" New registration "in the upper right.
User ID, fill out e-mail address, password, etc., and then click the check "was confirmed for the handling of personal information", "new registration".
When registration is completed, the button "participate in practice contest" is displayed, so click on it.
Confirm that the letter "Joined in ~" appears at the top of the screen and click "Problem" from the upper tab.
Then click on "First Letter".
When you move to the problem page, "Problem statement" is displayed. The problem sentence of this time is "The integers a, b, c and the character string s are given. Show the integer a + b + c and the character string s side by side". Competition programming is a contest that contests the speed of making programs that solve problems that are presented in this way.
Below the problem sentence, the detailed form of "input" and the form which should have "output" are displayed respectively.
Even if you can not understand problem sentences well, "input examples" and "output examples" at the bottom of the page will help you understand. As you can see from the image below, you can see that you can combine the last three digits and the last three strings and output.
Examples because usually are three degree prepared, I also recommend to see the first example if you do not know well read the problem statement. I understood what I should do this time, so I will organize a program right away.
I wanted to enter straight into programming, but to execute the written program I need software called a compiler. This time I will use the compiler called MinGW.MinGW official websiteGo to "Download Installer" in the upper right corner.
Then, it automatically transits to the download page of SourceForge, and "mingw-get-setup.exe" download begins.
Double click on the download to complete the file.
When the installer starts up, click "Install".
Confirm the setting and click "Continue" as it is. Basically there is no need to change the setting.
Wait for a while as the download starts.
The download progress is completed if the green progress bar goes to the right end. Click "Continue".
"MinGW Installation Manager" starts up, click the check box next to "mingw32 - gcc - g ++", and click "Mark for Installation".
In the same way also mark the "mingw32 - base" checkbox. This marks the two check boxes.
Next, click "Apply Changes" from the "Installation" menu on the upper left.
"Since confirmation screen appears, click" Apply ".
Installation takes about 10 minutes. When installation is completed click the "Close" button in the upper right to close the window.
Next, I will go through the process of "passing through the path". Open the Explorer with "Win key + E", right click on "PC" on the left and click "Properties" at the bottom of the menu that appears.
Click "Advanced System Settings" from the left menu.
As the menu "System Properties" appears, click the "Environment Variables" at the bottom.
The "Environment Variable" menu opens, click "Path" to select it, then click "Edit".
In the upper right, click "New", enter "MinGW installation folder \ bin" and click "OK". If you installed MinGW with the default settings, you can enter "C: \ MinGW \ bin" as shown in the image below.
Open the "Run with file name" menu with "Win key + R", type "cmd" for the name and click "OK".
Since the command prompt opens,
[code]g++ -v[/code]
And press the Enter key. It will be successful if a character string like the image below is displayed. If 'sentence' or 'g ++' is an internal command or ~ "comes out, it is highly likely that the environment variable setting is incorrect, so please check again.
Leave the command prompt open, and then create a working folder. Create a folder called "kyopro" on the desktop, right click inside the folder and click "Create New" → "Text Text" from the menu that came out.
In this case, select "Display" from the tab above the Explorer and check "File name extension". If you already have it, it is OK as it is.
With the text document created, press "F2" key and rename to "practice.cpp".
A warning will appear when changing the extension, so click "Yes".
When you double click "practice.cpp", a pop-up "Please choose a method to open this file" is displayed. Select "Notepad" and click "OK". This time we will continue with this memo pad, but it is not easy to use as a text editor, so if you use your favorite text editor OK.
First copy the following code ......
[code]#include
using namespace std;
int main () {
/////////////////////////////////////
I will write the code in this part
/////////////////////////////////////
return 0;
} [/ code]
Paste it in "practice.cpp" I made earlier.
Basically, if you edit the part of "Write code to this part" OK. For example, the program that outputs the entered number directly is as follows.
[code]int a;
cin >> a;
cout << a << endl;[/code]
At the command prompt
[code]cd Desktop/kyopro[/code]
And go to the "kyopro" directory created earlier. After moving
[code]g++ practice.cpp[/code]
, Compile the source code and generate an executable file.
Looking at the "kyopro" folder, you can see that an executable file named "a.exe" was generated.
Return to the command prompt,
[code]a[/code]
"A.exe" will be executed. Because it automatically enters the input wait state, if you press some Enter number and press the Enter key, the input number will be returned. Entering "0" returns "0", "1000" means "1000", "3456789" returns "3456789".
Ready. I will immediately address the problem. After reconfirming the problem, we got three numbers in order, so add them together and output them with the last input string.
Write down the code that will be the answer.
Once the code is ready again
[code]g++ practice.cpp[/code]
And compile it. continue
[code]a[/code]
Then, execute a.exe. When entering the input wait state, according to the "example of input" which was on the problem page of AtCoder
[code]1
twenty three
test [/ code]
When I input it, there was "6 test" on the line below. This is the "output example" so it is considered that the previous code is correct.
Besides inputting directly at the command prompt, you can also input from the text file. Create a file called "input.txt" in the working folder and write and save the contents you want to enter ... ....
When executing "a"
[code]a < input.txt[/code]
You can input from a text file by entering as shown.
Well, when we have the correct and confident code, we will submit it to AtCoder. Copy the contents of practice.cpp in full ... ...
Paste the "submission" tab on AtCoder to the "source code" part on the side where you opened it. Confirm that the problem is "A - First Letter" and the language is "C ++ 14", then click "Submit source code" at the bottom.
Submission was accepted. "WJ" stands for "Waiting for Judge", meaning waiting for grading.
After reloading the page after about 1 minute, the state that was "WJ" changed to "AC". "AC" stands for Accepted, that is, it is correct answer.
I will challenge the problem which was actually presented in the past contest. I opened the "Contest" page from the above navigation bar, selected "AtCoder Beginner Contest" from "Past Contest" and clicked "AtCoder Beginner Contest 081" displayed.
"AtCoder Beginner Contest" is a contest for beginners, and easy and educational problems are entered. I will immediately go to the Problem tab and see the problem.
Firstly from "A" problem. Click "Placing Marbles" at the top.
Although the problem name was English, since the problem sentence is Japanese, it is safe even for people who are not good at English.
Below the problem sentence, input and output formats are defined.
Every problem has "input and output example", so even people who are not good at Japanese can be safe as well. According to Example 1, the output when the input is "101" is "2". It also has an explanation that "marbles are placed at trout 1,3."
Looking at the second example, "0" is output when the input is "000". In other words, it seems that it is good if three "0" or "1" are input to the input, and the number of "1" is output.
I write up the code where the problem was solved.
Save the code of the image above as "beginner081a.cpp"
[code]g++ beginner081a.cpp[/code]
And compile it. Then I got an error like something. "1" "is underlined and there seems to be a problem here.
When examining it,A double quotation marks a pointer indicating an address where characters are storedAnd it is correct to enclose it with single quotes.
I recompiled and compiled it, I ran the generated a.exe and entered "101" as it was in the example, it returned "4201133".
The reason is that "0" was not substituted when declaring ans. Next time I will initialize properly.
After compiling the corrected code and entering "101" and "000" as in the example, the answers "2" and "0" are returned, respectively. This seems to be OK.
Copy all the code ......
AtCoder problem Click the "submit" button at the bottom of the page.
Paste the code in the "Source code" field and click "Submit source code".
After waiting for scoring for a while, reloading it was "AC". With this one correct answer.
Again from the Problems tab, click on the problem B "Shift only".
Problem statement and ... ...
The input and output formats are given.
Even if the problem sentence is difficult, there are examples, so it is safe. How many times can you do "divide all numbers by 2"? It seems to be a problem.
Operation can not be performed even if there is an odd number.
Problem A was three digits, but this time it seems that sometimes a large number is given.
I created a part to capture input for the time being. We will add each input value to the array a.
We calculated "how many times each input is divided by 2" and decide to output the minimum value. Make sure that the return value of half (x) contains "How many times x broke with 2".
The half function prepared in translation is kore. If it is an odd number, 0 is returned, if it is an even number, it is sent again to half and 1 is added to the return valueRecursive functionis.
Copy the input example 1 for testing at hand ... ...
Save it as "input1.txt".
I have created "input2.txt" and "input3.txt" in the same way.
I compiled it, I got an error. It was because "}" is missing ... ...
Add the missing closing parenthesis.
Once compiled and executed again, if you pour the input of each of the three examples, "2" "0" "8" was output. This looks good.
AtCoder problem Click the "submit" button at the bottom of the page ... ...
Paste the source code and click "Submit source code" button.
After waiting for a while and reloading the result page, it was displayed safely "AC". This is 2 correct answers.
In this condition I try to challenge the C problem "Not so Diverse".
The problem sentence is this street. "How many balls need to be rewritten to make K types of numbers written on N balls?"
Below the question sentence is the form of input and output.
In input example 1
[code]5 2
1 1 2 2 5 [/ code]
, And when three types of characters, "1" "1" "2" "2" "5", are written in five balls, "5 "It is enough to rewrite only one ball in which it is written, so" 1 "is output.
I will also look at Example 2. I have to set the number type of the number to 4 or less, but since there are only 2 kinds originally, "0" is output.
There was also a third example. For the moment, I will save all the examples in "input1.txt" "input2.txt" "input3.txt" just as before.
While struggling, I managed to finish the code.
When compiling and running it, the answer I was asking "1" "0" "3" returned. I will submit it as it is.
AtCoder problem Click the "submit" button at the bottom of the page ... ...
Paste the source code and click "Submit source code" button.
After waiting for a while and reloading the result page, "AC" has been displayed safely. However, the execution time takes "1271 ms" as well. Actually, competition programming has limitation on execution time, and many problems become incorrect when execution time exceeds 2000 ms (2 seconds). In the top problem, a different dimension fight called "how to calculate the answer with a small amount of calculation" will be unfolded.
In the case of the completed contest, all the codes submitted by other people are published, so we can look at that code and study. Click "All Results" from the "Results" tab.
Set the problem name to "C - Not so ~", language to "C ++ 14", state to "AC", click "Search", then click "execution time" I will sort in the order from. Try looking at the code of the person who came to the top of the page for the time being, so click "Confirm Details" at the top.
A code like the one below is displayed. I will try to decipher this.
In addition, when clicking "commentary" on the "commentary" tab ... ...
You can download the PDF file that explains the problem.
A commentary on the C problem was briefly written.
The source code of the results scorer and the official commentary Summary of what you learned from the PDF as an example of inputs "5" "2" "5" "3" "1" "2" "5" "5" It is the image below. I am considering the case where you set the 8 inputs to 2 types or less. "Cnt [a] ++;" under "cin >> a;" of the superior source code counts which number has appeared. This is the block written as "second in the figure, cnt at the left end". In the example shown in the figure, it is recorded such that "1" appears once, "2" twice, "3" once, "4" appears 0 times, "5" appears 4 times. Then sort cnt using the sort function and record the number of numbers that appeared more than once in g. By subtracting k from the number of types now, calculate how many kinds of numbers must be changed, and the answer will be the sum of g - k from the smaller one of cnt's nonzero part. In this example, the answer is the number obtained by adding 4-2 = 2 from the bottom of the non-zero part of the sorted cnt, that is, 1 + 1 = 2.
Since I understood the algorithm of how the answer is derived, I will write the code with reference to the superior source code.
When I compiled it, I got an error "There is no function called sort" and an error saying "There is no variable called g".
"G" is the name written as "types" in my own code, so modify it to "types".
C ++ sortAs for the source code
[code]#include
[/ code]
It seems necessary to write.
That's why I fixed it.
Since I compiled it when I fixed it, I tried input of "example" on problem page. The output of "Example 1" must be "1", but somehow it has become "0".
In order to investigate the cause, I will try to output "cnt [a]" each time I read a number.
When compiled and run it, a mysterious number "4199636" was outputted.
Observing the code often caused an out-of-sequence reference.
[code]int cnt[5] = {};[/code]
If you declare it, the number used to access cnt [0] ~ cnt [4] will be 0 from 4, so a bug occurred trying to use cnt [5].
I fixed it and recompile it and run it again. Since I forgot to erase the output sentence for debugging, it has been output a lot, but since it is the answer that comes out at the end, it is still something is wrong that it is "0".
When checking the number of types of numbers, it was only possible to check from 0 to n-1. Fix to check up to the nth. Also delete the output for debugging.
Once compiled and run again, the numbers that should be "1" "0" "3" are outputted next time.
Submit the source code.
Looking at the result, the execution time which took "1271 ms" earlier is reduced to "80 ms".
As you can see from the "Rank table" tab, there are only 25 people who can solve D problem within the time limit of this contest. D problem is pretty difficult, so it may be better to look at the commentary if you do not understand for the moment at first.Dynamic programmingYaPottery method,treeYaBinary searchFrequent algorithms will appear in competition programming such as. There were 397 people who could solve C problem.
Looking at the problem statement of problem D, the constraint of "2N or less" is imposed on the manipulated variable, it seems to be a problem how how to clear this constraint. If you are confident, please challenge.
AtCoder Beginner ContestIt is held every Saturday or Sunday from 21:00 to 22:40.Explanatory broadcastAlso it is a contest that beginners are easy to challenge, such as being done, so it is a recommendation for those who would like to start competition programming.
Related Posts:
