- This paragraph, the question read wrong.
- Thoughts.
- This is a maximum two-part matching because the even-oddness of the pair is different, and a pair is a matching of a bipartite graph.
- But I’m not sure if it’s safe to have 10^5 vertices.
- If you have multiple cards with the same number, you can simply increase the capacity.
- Official Explanation
- There is a linear order solution.
- I still don’t get the maximum two-part matching.
- Dinic was no good because O(V^2E)
- Thoughts.
- I realized I read the problem wrong.
- Since the absolute value of the difference is “less than or equal to 1”, it is a pair even when the difference is 0.
- It’s fundamentally wrong to use an even-odd, two-part graph.
- Based on this, I’m thinking from the small side.
- Up to three clumps have the same result no matter how they are taken.
- When four, there is a pattern of loss when taken vertically (left).
- So should we always prioritize taking it sideways? There’s a counterexample to that too, at 6 (right).
- Bad behavior common to both patterns: “There are cards that are isolated to one once the left-most pair is taken.”
- So is it OK if you “pack and take from the edges so that nothing is isolated”?
- I should be able to prove that this is OK, but if I’m in a contest, I’ll implement it and try it out in a test case.
- Official Explanation: When the number of sheets is divided into non-zero intervals, it can be shown that there is no better way to get the maximum value than the above method, with at most one sheet left over.
- fill in the blanks (at the end of a task)
- Since the absolute value of the difference is “less than or equal to 1”, it is a pair even when the difference is 0.
This page is auto-translated from /nishio/AGC003B using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.