[PYTHON] Competitive programming starting with LetCode, which I recommend after solving 150 questions in 8 weeks

Introduction

Hello. Are you a competitive pro? Until recently, I've been doing "competitive professional scams" (laughs).

Although I am interested in competitive programming, it has been two years since I found an excuse such as "the hurdle to participate in the contest is high" and continued to run away. It was because I started to be pressed by.

Now it is in the following state.

--Participate in the contest as much as possible, mainly LeetCode / AtCoder (ABC) --Solve LeetCode Problems at other times --AtCoder ABC is limited to 4 completes, LeetCode is limited to 3 completes

This time I started competitive programming from scratch

――What kind of process did you go through? ――Recommended learning method for those who will enter competitive programming from now on

I would like to explain mainly about.

TL;DR --Recommended to solve from LeetCode's Easy problem --By continuing competitive programming, you will have the following benefits: -** You can write code that is conscious of time complexity / spatial complexity ** -** Improves the speed of assembling logic in the brain ** -** Studying the language itself ** -** Competitive programming is still fun (important) **

What is competitive programming?

It is a competition to solve problems with an algorithm written by yourself.

For example, the following questions will be asked.

There are games that win when you say 0.
Playing a game with two players, a number n to 1~We will reduce the number up to 3.
I am always ahead.
Also, you and your partner will always do their best.

For example n=In case of 4, the result is as follows.
Self: 3 (reduced by 1)
Opponent: 2,1,0 (decrease by 3 and declare 0 to win)

Write a program that determines whether you can win against n with boolean.

Competitive programming is also good because it has a lot of problems that you can tackle with interest.

Difference between AtCoder and LeetCode

Personally, I think the main differences between AtCoder and LeetCode are as follows:

AtCoder Data structure, algorithm, mathematics, thinking ability, knowledge etc ... are required in a well-balanced manner.

LeetCode Many problems specific to data structures and algorithms

AtCoder is more difficult to feel on the skin. Since LeetCode specializes in data structures and algorithms, I think that if you solve a certain number of problems, especially Easy problems, you will be able to solve other problems as well.

Therefore, ** If you start with the Easy problem of LetCode, you can realize the fun of competitive programming in a relatively short time. ** **

Language selection in competitive programming

C ++ is popular, but I'm writing in Python3. The reason is that ** I use Python for business and I like it as a language **.

Python3 is inferior to C ++ in speed, but it also has the advantage of ** reducing the amount of description **.

You may be able to solve the problem to some extent and change to another language when you decide to master competitive programming.

Competitive programming process

Here's a brief description of how you've grown over the eight weeks.

Begin to solve

――It takes a lot of time to solve each question --Implementation speed itself is slow --I can't be aware of the amount of time complexity and space complexity ――It's fun to solve, but I can't solve at all

Until you solve 50 questions

--You can now solve really simple problems --Getting familiar with data structures such as Binary Search Tree --Understand concepts such as Dynamic Programming / Depth First Search / Breadth First Search ――Become able to participate in the contest without worrying about your grades (important)

Until you solve 100 questions

――You can solve solvable problems, but you can't solve unsolvable problems no matter how much you think --By becoming LTE (Limit Time Exceeded), you will be semi-forced to worry about the amount of time calculation. ――I realize that thinking power is a bottleneck (important)

to date

--Easy problems can be solved --Implementation speed has improved --Be aware of time complexity and space complexity --The fun of solving problems has increased

In my case, I feel that ** every 50 questions came a small breakthrough **. This led to ** "solving the number of problems" described later **, and I was convinced.

How to solve

Currently, I am solving the problem with the following solution.

  1. Understand the problem properly
  2. Consider all methods (3 or more if possible)
  3. Wash out the corner case
  4. Be aware of the amount of time calculation
  5. Write code

I think steps 1,2,3,4 above are important. ** In other words, the game is before implementation. ** **

――If you neglect step 1, a simple problem will turn into an unsolvable problem (laughs). ――If you neglect step 2, you will continue to refactor the detailed implementation with a policy that you can never solve, and in the end you will not be able to solve it frequently. --If you neglect step 3, the number of WA (Wrong Answer) will increase. --If you neglect step 4, the number of LTE (Limit Time Exceeded) will increase.

How to improve the power of competitive programming

I think the following guidelines are important.

  1. Even if the problem is solved, the data structure and algorithm are not ** completely understood, **
  2. On the contrary, even if you can't solve it **, be sure to look back on whether there was a part you understood **

This idea is, after all, not limited to competitive programming. I think it can be applied to any field.

Based on the above, what kind of action should be taken is described below.

Do the number of problems

In order to fully understand the data structure and algorithms, it is important to review the exact same problem, but I think it is important to solve a large number of problems that are asked from various angles **.

Know a different solution

If you can't solve the problem, you'll see the answer. Or you might think about solving it yourself without looking at the answer. The important thing here is ** to recognize the difference between your own way of thinking and the way of thinking of the answer **.

If you can solve the problem, ** read the various answers. ** **

I think it was very effective to continue this from the beginning.

Do not touch problems that do not need to be solved, problems that do not need to be solved

** The former is "a problem that is too difficult for your current level". ** So what is the latter problem?

Do you remember the following problems introduced in "What is Competitive Programming?"

There are games that win when you say 0.
Playing a game with two players, a number n to 1~We will reduce the number up to 3.
I am always ahead.
Also, you and your partner will always do their best.

For example n=In case of 4, the result is as follows.
Self: 3 (reduced by 1)
Opponent: 2,1,0 (decrease by 3 and declare 0 to win)

Write a program that determines whether you can win against n with boolean.

If you solve this problem in a certain way, you can solve it in an instant. Conversely, if you try to solve it with an algorithm, it may result in LTE (Limit Time Exceeded) (as was the case with LeetCode).

If ** only the former can be solved, the problem cannot be solved (although the idea is correct), and there is a risk of misrecognizing that it is not correct. ** ** ** This is very dangerous. ** **

From an educational point of view (although it may be a good medicine), such problems do not seem to be very effective. It's not good to spend too much time without solving.

Be aware of your habits and weaknesses

If you can solve the problem to some extent from the initial stage, you will see the kind of problem that you are not good at. This time, how we can solve the problem will lead to the next breakthrough.

On the contrary, any problem can only be solved by continuing to think about how to solve it.

** Solution Step 2 The more you can "consider every method", the more likely you are to solve the problem, so reducing your own habits and weaknesses will directly improve the accuracy rate of the problem. ** **

Participate in the contest without worrying about your grades

Grades are just results. It may be an extreme argument that professionals are enough to pursue results, but ** for beginners, "a place to check the results of practice" is the most important thing. ** **

I personally think that if you continue "practice for practice", your motivation will drop and it will not lead to results.

Therefore, the most important thing is ** "to increase the chances of production", which is "to participate in the contest without worrying about the results" in competitive programming **.

at the end

I recommended LeetCode this time, but if you can solve ** AtCoder, you should solve the problem with AtCoder. ** ** Above all, the realization that "competitive programming is fun" is important.

If you read this article and more people start competitive programming alone, you wouldn't be so happy. See you in the contest!

Recommended Posts

Competitive programming starting with LetCode, which I recommend after solving 150 questions in 8 weeks
I participated in competitive programming in a week after I started programming
I made a competitive programming glossary with Python
I tried competitive programming
Competitive programming with python