Solving problems like AtCoder and recording my thoughts and learnings.#competitiveprogramming
-
Selected 100 Problems https://qiita.com/e869120/items/eb50fdaece12be418faa
- I haven’t written about problems before 18, but I solved them.
- Binary Search
- 19 Pizza - I was using a Set type and it took O(log N) every time I inserted. I solved it by changing it to Vec.
- 20 Snuke Festival - A problem of selecting one element from three arrays vec
a, b, c. It’s easier if you fix the middle element (typical). - 21 Shooting King - Change the wording of the problem and think about simplifying it. Requires thinking skills.
- Depth-First Search
- 24 ALDS1_11_B - Basic DFS, implemented with a recursive function. It’s easier if you can create a template.
- 25 How Many Islands? - DFS on a grid graph, the point is to move in eight directions instead of four.
- 26 Ki - Note that DFS has a considerable computational complexity. Record it with a cumulative sum-like approach and then add it.
- POINT: Think about how to solve it if it’s not a tree but a one-dimensional array.
- Breadth-First Search
- 28 ALDS_11_C - Implement a normal BFS with a queue.
- 29 Breadth-First Search - Implement grid BFS normally.
- 30 Cheese - BFS on each factory in order.
- 31 Illumination - Since it’s a hexagon, change dx, dy for even and odd rows.
-
Educational DP https://qiita.com/drken/items/dc53c683d6de8aeacf5a#c-問題---vacation#dynamicprogramming
- 1 Frog 1 - Look at the previous two and one step, DP.
- 2 Frog 2 - Just generalize Frog 1.
- 3 Vacation - The point is to realize that it doesn’t affect anything except the previous one.
- 4 Knapsack - Knapsack Problem, the key is to increase the dimension of the index as needed.
- 5 Knapsack 2 -