We will hold AtCoder Regular Contest 231.
- Contest URL: https://atcoder.jp/contests/arc231
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20261004T2100&p1=248
- Duration: 120 minutes
- Writer: Mitsubachi
- Tester: Nyaan, maspy
- Rated range: 1200 ~ 2799
- Point Values: 500-500-600-700-800-800
We are looking forward to your participation!








I hope I can AC AB
Me too
I hope AC ABC lets go
no……Awa,Bwaeeeeeeeeeeeeeee
I hate B
Anyone hack for this qwq
btw, D's samples gave me a wrong impression that when N=3,K=2 the first wins... Until I wrote a brute force and discovered that it's wrong. wtf...
I used the exact same way to solve this problem.
One possible proof is that I noticed that in this procedure, the number of non-empty piles is always greater than the number of stones in the largest pile.
After trying $$$K=1$$$, we take a leap of faith and extrapolate to guess that
Secondwins every time.Let us experiment with which positions are "better" for
Secondand which are "better" forFirst. One direct winning position forFirstthat we can construct is one tall pile of stones. If we "flip" this configuration, having many piles of stones of size $$$1$$$,Secondwins.This suggests that it is beneficial to
Secondto have a large number of piles of stones, with the piles themselves being very short. Thus, we will try to remove stones from the $$$K$$$ piles with the largest number.Note that unlike the above solution by L_Wave, this fails since we remove $$$M$$$ stones rather than $$$j$$$ stones (where $$$j$$$ is the number taken by
First). This solution ends up removing piles of $$$1$$$ stone each, and such piles are beneficial for us (e.g. $$$K=2$$$, pile sizes are $$$[2,1]$$$, then this strategy makes the pile sizes $$$[1,0]$$$ and allowsFirstto win). Failed submissionTo address this, we only remove stones from piles with $$$M$$$ stones, where $$$M$$$ is the maximum number of stones in any pile. Intuitively, this allows the size of the piles to decrease faster than
Firstdecreases the number of piles.However, this reasoning is somewhat bogus because the solution is incorrect. Take the following example with $$$N=4$$$ and $$$K=2$$$.
Where $\rightarrow^1$ and $$$\rightarrow^2$$$ represent moves by
FirstandSecondrespectively.Submission
My solution was based on that, but specially dealt with the case when $$$M=1$$$ (in this case we have an obvious winning strategy). I don't know whether that is correct.
An alternative interpretation to "D — Choose Your Role" https://atcoder.jp/contests/arc231/editorial/26560
How would one solve B if the constraints only allowed the elements of sets to be < 1024
In problem D, I noticed that there are only $$$N-1$$$ stones in each pile. So I wondered why it wasn't $$$N$$$. Since $$$N \times (N-1)$$$ is even, I guessed that maybe the second player should choose the number of piles depending on the number of stones the first player chose in the last turn. So this can make sure that the number of stones in total will always be even after the move of the second player. So I guessed that the second player can always win. In addition, if there are $$$N$$$ stones in each pile at first, if the first player chose to remove $$$N$$$ stones in a pile, the second player couldn't remove the same number. Those give me the idea to remove the same number as the first player, starting from biggest pile to smaller.
Sadly, I didn't think I could solve 700-points problem during the contest. So I only solved A and B, and losed a lot of ratings. ^_^
Maybe I need to be more confident in myself, and dare to look at D, E, F in the contest.
In D, it seems removing stones from the $$$K$$$ largest piles almost works. This submission gets AC and passes hundreds of thousands of small stresstests where the 1st player moves randomly.
We play as the 2nd player, removing stones from the largest $$$K$$$ piles (all non-empty piles if there are $$$\lt K$$$ of them) with two exceptions. This aims to preserve the invariant "the number of piles is greater than the size of largest pile" at the beginning of 1st player's moves.
Special case 1: If the largest pile has more than one stone, we don't remove stones from piles with size 1 — it doesn't benefit us. In other words we don't reduce the number of piles if we don't have to, and when we do, it's a trivial winning state already.
Special case 2: We avoid moving to a state "$$$K+1$$$ piles with size $$$\gt K$$$ and one pile with size $$$\le K$$$" from a state "$$$K+2$$$ piles, all with size $$$\gt K$$$". For $$$K=1$$$ we don't have to worry about it. Since we were trying to remove $$$K$$$ stones, such a move can be fixed by removing one less stone, and as long as the invariant held before, it also means the fixed move gives $$$K+2$$$ piles with size $$$K+1$$$ each.