Foreword & Result
Sleeping is evil.
A: パ研合宿 2103 (100 marks)
Output .
B: 多数決 (100 marks)
Count the number of black
and white
, and output the one with more counts.
C: カラオケ (100 marks)
Calculate the score for the group for all pairs of songs then output the maximum.
D: パ研軍旗 (100 marks)
Vacation DP. Compute the cost of red, blue and white for each column beforehand, then apply DP.
E: 大きなクリスマスプレゼント (78 marks)
For subtasks 1, 2 and 3, a DFS/BFS to count the number of cells in each component will do.
For subtasks 4, 5 and 6, we can precompute the number of connected squares of size for each . Then we can perform a DFS/BFS to count the number of connected squares, considering each size separately.
Combine the two solutions and we can get 78 marks.
From Twitter, it seems that we can solve the problem by computing the largest square that each cell can store using 2D partial sum and binary search, then use union-find tree to merge the cells after sorting the queries...
F: クリスマス飾り 2 (38 marks)
For subtasks 1, 2 and 4, we can simply exhaust the 2 starting points and count the number of ornaments we can preserve . Then the answer is . The time complexity is . (How do I modify this idea to be ...)
For subtasks 3, we can simply scan the array to count the number of distinct segments after each modification, and the answer is .
G: プレゼント配り 2 (22 marks)
Implemented greedy and DP for subtasks 1 to 3. (How do I pass subtask 4...)
H: パ研王国を守れ! (38 marks)
I implemented a greedy algorithm to check that if there are 'X'
in each direction of each 'Q'
, and block them if there is.
Conclusion
The problems are interesting, and the subtasks are quite helpful. Thanks to @e869120, @square10011, @tatyamprime and @noimikyopro.