[PYTHON] AtCoder To become light blue

0. Introduction

Hi, this is HIROSHI0635. I wrote a simple article when it turned green, but I managed to turn it light blue about 9 months after it turned green. To be honest, I think it's been a long time. That is why I am writing with the hope of writing something that will give some hints to those who are struggling with green or brown. With that in mind, I dared to give it the title "To become AtCoder light blue" instead of "Until it becomes light blue" (I love the fact that the green has faded while writing the article ...).

1. Self-introduction

・ Third year of working people in finance. ・ AtCoder started once in C ++, but I couldn't do anything and was frustrated in about a month. ・ I changed the language to Python and tried again and reached light blue in a year and a half. ・ In college, I was a liberal arts student. I have no experience in programming. ・ There is no weakness in mathematics at the university entrance exam stage.

It's roughly like this. If you want to know the details of how you started AtCoder, please see the past article (AtCoder until it turns green). Please refer to the

2. Thinking about the problem

2-1. Thinking from sluggish growth

While the first green performance was the 11th contest, the first light blue performance took up to the 38th (actually the 41st because the 38th Hitachi contest just happened to be addicted to 100-200 quick answers). Certainly, at the 11th time, I did not know the so-called "standard algorithms" such as DFS, BFS, Dijkstra's algorithm, binary search etc, but by the 25th time, all of them can be implemented and copied several times. It was a situation where AC could be done for such problems. Even so, I think that the reason why I couldn't solve the problem of green Difficulty [^ 1] was that I was weak in the consciousness of the computational complexity [^ 2] and the consciousness of reducing the problem.

2-2. Raise awareness of computational complexity

Suddenly, let's replace solving AtCoder's problem with curry making (curry doesn't mean anything, I just thought about it). Suppose you are asked to make curry for less than 2000 yen as a limit. I don't think ordinary people buy more than 2000 yen for supermarkets, but this is what happens when you unexpectedly become a TLE in competitive programming. It's a little better if you are aware that you don't know how much this ingredient costs, but if you go to the cash register without considering the price, or if you think that this is 100 yen, it's actually 5000 trillion yen. is. ** If you don't know the amount of calculation of your answer, you should get into the habit of grasping the amount of calculation of your answer first, instead of trying various algorithms ** (I think it looks great) As I said, it wasn't until just before it turned green that I became aware of the amount of calculation and the answer.) In the first place, the motive for using the algorithm is to reduce the amount of calculation because the full search is not in time, and if the amount of calculation is not known, the treasure will be lost.

Then, when asked how to improve the ability to grasp the amount of calculation, if there is a situation where you do not know how much this amount of calculation is at the practice stage, you should check the amount of calculation or make a habit of changing to a writing style that determines the amount of calculation. I think there is no choice. If you are a Python user, this article (Embarrassing computational complexity if you don't know Pythonista) will be very helpful.

2-3. Raise awareness to reduce problems

Suddenly (again), AtCoder is often referred to as a math game. Certainly, there are cases where people with a strong background in mathematics seem to reach blue in a blink of an eye after participating around 10 times. My theory is that this is half correct and half incorrect (I'm sorry if I misunderstand it because I only do math for entrance exams). That's because there aren't many problems where you can use your math knowledge as it is with AtCoder, but you can still use the thinking method of finding a formula that can be applied by abstracting the problem, which is required when solving math problems. For example, suppose you learned how to solve a linear equation of "5x = 10" → "x = 2" when you were in junior high school. If you remember this as it is, even if you are asked to solve "3a = 6", it will be "I don't know because I haven't learned it". The degree of abstraction differs depending on whether the first problem is regarded as a transformation of only x or x is regarded as a container of numbers in algebra in the first place, and the more abstract it is, the more it can be applied to many problems. I will. I dared to give a simple example to give an example of abstraction, but even in a real problem, the difficulty may change significantly even though the implementation amount is not so different using the same algorithm. For example (please be careful if you want to solve it first as it includes spoilers below), AtCoder Beginner Contest 177 D - Friends [AtCoder Regular Contest 107 C - Shuffle Permutation] (https://atcoder.jp/contests/arc107/tasks/arc107_c?lang=ja)

The two problems use the same algorithm, but the Difficulty differs by more than 500. The problem with 177-D is that the word "group" comes out, and there is an air of Union-Find-like, so I feel that there are many people who managed to AC. I think that the difference in the consequences of the problem is the difference between those who can AC the upper problem and not the lower problem. The problem below seems to be trivial at first glance, but since there is no duplication of elements, you can see that it can be considered separately vertically and horizontally (when vertical and horizontal come out, it can be considered separately). It is a fairly typical thinking pattern to think about it). Also, if you consider that the rows / columns that can be swapped are bordered, you can see that the rows / columns that are connected can be swapped freely. If you can do so far, you can solve the problem by reducing the data structure that manages whether it is concatenated → Union-Find. The biggest point is whether "swap" can be paraphrased as "stretching", but this is how abstract the problem can be considered. From now on, I will explain how to improve the ability to abstractly reduce the problem.

2-4. Training to improve the ability to return

① Solve problems of the same genre together

By doing this devotion, you will find that each algorithm can be applied to a variety of problems, increasing the impact of the problem. Also, in order to increase the power of consequence, each algorithm needs to be understood in a more abstract dimension (as shown in the example of the linear equation). However, it is difficult to think abstractly suddenly (if you suddenly try to understand a mathematically strict definition / theorem, you will be surprised, right?), So get noticed while thinking about concrete examples (concrete problems). I think this method is easy to do. For those who are smoldering in brown or green, I would especially like to recommend Guidelines for improving competition professionals and AtCoder taught by Red Coder [Intermediate Edition: Aim for Light Blue Coder! ] is to solve the 100 questions listed. I have solved about 80 questions, but I feel that I have gained considerable strength. There are some difficult problems, so if it's really difficult, you can skip it.

② Solve the same problem with a different method

If method (1) is a vertical skewer, method (2) is a horizontal skewer. For example, problems that can be solved with BFS can be solved with DFS. Also, problems that can be solved by the scale method can be solved by a binary search. Solving the same problem in a different way leads to a different perspective on the problem, increasing the paraphrasing power of the problem, that is, the ability to reduce it. In addition, there is a solution that says that either one can be solved, but which one is easier to solve (although it may change depending on the person), and there is a guideline to adopt this algorithm for such problems, speeding up and certainty. It leads to improvement. I myself think that BFS is easier to understand than DFS, and that binary search is faster than the scale method without causing bugs, so if you have a problem that seems to be applicable to either, use BFS and binary search, respectively. I am doing it. As a recent discovery, I learned one way to reduce the problem to the following problems (which also include spoilers).

[AtCoder Grand Contest B - Graph Partition] (https://atcoder.jp/contests/agc039/tasks/agc039_b)

From the conclusion, this problem is a question as to whether it is possible to paraphrase "can it be separated into a set of vertices" → "bipartite graph judgment". When I thought about this problem myself, I thought that it would be possible to separate it if there were no odd-length cycles, but I couldn't write the code and looked at the explanation and ACed it with a solution method using a bipartite graph. I did not end here, but since it was a big deal, I also wrote a code based on the idea that "it can be separated if there is no odd-length cycle" and confirmed that AC can be obtained. [Method using bipartite graph judgment] (https://atcoder.jp/contests/agc039/submissions/17673050) [Method focusing on the presence or absence of odd-length cycles] (https://atcoder.jp/contests/agc039/submissions/17673603)

As you can see by comparing them, it is easier to use the bipartite graph judgment. However, by doing this work, I think that when you come up with a solution that focuses on odd-length cycles in the same way, you will be able to reduce it to bipartite graph judgment. I don't think it's necessary to do this for all problems, but if you have a hard time and can do AC on your own, look at the explanation, and if you're taking a different approach, try that as well. I think that is good.

2-5. Summary

In addition to summarizing the story so far, I will explain a little the flow of thinking about the problem.

I'm thinking about the problem with a flow that's more or less like the slide above. As you can see, the key is to be able to correctly grasp the amount of calculation in ④ and ⑥, and to be able to reduce to a typical algorithm that can solve the problem in ② and ⑤. When you enter the branch of ①, think of a way to somehow "struggle" and understand the problem as described in ②. Here, we consider an algorithm that can be solved for the time being, disregarding the amount of calculation. It would be nice if the calculated answer seems to be in time, but if it does not seem to be in time, try to reduce it by the method described in ⑤. Among them, the typical struggle is well organized in this article (Typical way of thinking for coming up with solutions in competitive programming). .. I think that the more people who are not conscious of reducing the problem to the typical, the more they can get by looking at it once.

3. Other devotion contents

I wrote some devotion in Chapter 2, but here are some other things I did.

3-1. JOI devotion

Guidelines for improving AtCoder, a competition professional taught by Red Coder [Intermediate Edition: Aim for Light Blue Coder! ] There are quite a few JOI problems, but there are many good questions about JOI problems, especially the DP / shortest path problem. I'm not very good at DP myself, and I also did the Educational DP Contest / DP Summary Contest, but it wasn't very well established, so it was quite useful. .. AOJ / AtCoder-JOI is convenient because you can manage the problems you solved while arranging the problems by level. I think it's best to solve from level 4 or level 5 for brown coder, and level 5 or level 6 for green coder.

3-2. Kodofo devotion

I think many people are doing this. However, many of the Kodofo contests are held late at night, and it is difficult for working people to participate. If you use Codeforces Anytime, you can get a virtual rating even in a virtual contest, so you can work with a sense of tension.

3-3. Participation in team battles

Recently, I participated in a contest held by volunteers from universities such as WUPC and KUPC. It was a good opportunity to learn other people's thinking patterns by participating in groups of three. Both of my teammates were blue coders, so I couldn't contribute much to the team, but by thinking "I want to solve even one question by the next time" and "I want to catch up with these people", I can do it. I think I was able to extend it.

4. Going around in the contest

4-1. Use the standings

Do you guys see the standings during the contest? I will see. In the case of ABC, I try to solve up to D without looking at the standings, and when I can solve it, I look at the standings, and when I see E and F, I try to solve F when they are solved as much. This is because F is likely to be easier to solve because F is solved as much as there are people who solve a certain number from the front without looking at the standings. Also, if the proof seems to be solved by the greedy method but the proof is not so confident, I will take the plunge and submit it if I can see that it is solved considerably by looking at the standings or the WA rate is low. However, I don't think this method can be honest, so I think it's better to read the explanations and understand the proof after the contest is over.

4-2. There may be hints in the problem statement

It's not that versatile, but it can be used occasionally. Recently, the problem of HHKB Programming Contest 2020 E --Lamps is AtCoder Beginner Contest 129 D --Lamp If you know the problem of / contests / abc129 / tasks / abc129_d), you can copy and paste the preprocessing. In recent years, ABC seems to have completed the field of honest questions, and it is important to be aware of past questions to some extent. Also, does this problem, AtCoder Beginner Contest 166 D --I hate Factorization, seemingly require mathematical formula transformation? I thought, but when I look at the problem statement, it says "I hate factorization" and there is no guarantee, but I think it can be solved by a simple search rather than advanced formula transformation. It was an opportunity to get around.

4-3. When the amount of calculation is suspicious

Even if you know the amount of calculation, you may be wondering whether to make it in time or submit it as a delicate amount of calculation. In such a case, you can create your own test case with the maximum amount of calculation and submit the code to the code test on the AtCoder page to get the guarantee that you will be in time without sacrificing the penalty.

5. Convenient links

So far, I've listed quite a few websites, but here are some other websites that I found helpful. I think you should look only at the things you care about.

Passing by reference and passing by value in Python arguments ... I had a hard time understanding the structure of such a language because I didn't have the opportunity to systematically learn programming languages. If you are using Python, this is the first thing you should master.

[Floating point geeks try to explain the C problem of AtCoder Beginner Contest 169] (https://qiita.com/mod_poppo/items/910b5fb9303baf864bf7) ... Otaku is a god because he is familiar with a specific field. The joke is the treatment of floating point, which seems to have become more frequent these days, but this was also a weak field for me, who had no chance to systematically learn programming languages. I'm not good at it yet, but I'm starting to notice suspicions.

[How to use Python defaultdict] (https://qiita.com/xza/items/72a1b07fcf64d1f4bdb7) ・ ・ ・ It is often used to judge whether it came out once while using a loop. If the maximum value that comes out is about $ 10 ^ 6 $, there is no problem with a list initialized with zero, but when the value is up to $ 10 ^ 9 $, the amount of spatial complexity is exceeded and the list is initialized with zero. Is not usable, so defaultdict comes in handy. Once you get used to it, it's very easy and convenient, so I definitely want you to master it.

[A special feature on how to find "too much divided by 1000000007"! ~ From inverse element to discrete logarithm ~] (https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a) ... Mod processing is frequent, but I've always been a weak field. After reading this article, I was able to understand Fermat's Little Theorem as much as I could, so I felt less weak.

[^ 1]: Difficulty level display in AtCoder Problem.

[^ 2]: There are two types of computational complexity, time complexity and spatial complexity, but the frequency of bottlenecks is overwhelmingly time complexity, so I think it is time complexity unless otherwise specified. please.