A - CatCoder Double Contest 解説 by evima
Let’s consider the set \(S\) of pairs \((X,Y)\) such that we can form \(X\) sets of Div.1 and \(Y\) sets of Div.2.
Let \(X_1, Y_1\) be the number of Div.1 and Div.2 contests held when we maximize Div.1 first, then maximize Div.2 with the remaining problem proposals. Similarly, let \(X_2, Y_2\) be the number of Div.1 and Div.2 contests held when we maximize Div.2 first, then maximize Div.1 with the remaining problem proposals.
The maximum possible value of \(X+Y\) is \(X_1+Y_1\). This is because reducing Div.1 by one set can increase the number of Div.2 sets by at most one. Also, \(X_1+Y_1 = X_2+Y_2\).
Any \((x,y)\) between \((X_1,Y_1)\) and \((X_2,Y_2)\), i.e., satisfying \(x \le X_1 \land y \le Y_2 \land x+y=X_1+Y_1(=X_2+Y_2)\), is included in \(S\).
Proof
We show that for \((x,y)\) satisfying \(X_2 \lt x \le X_1 \land Y_1 \le y \lt Y_2 \land x+y=X_1+Y_1\), we can rearrange to \((x-1,y+1)\).
There must be a writer whose Div.2 count is not at its limit. By breaking down one Div.1 set from this writer, we get one extra Medium problem proposal. Since the Div.2 count is not at its limit, there is also one extra Easy problem proposal, so we can form one new Div.2 set.
Also, when \((X,Y)\) is included in \(S\), clearly any \((x,y)\) satisfying \(0 \le x \le X \land 0 \le y \le Y\) is also included in \(S\). That is, \(S\) has the shape shown in the figure below.
The answer is the maximum \(k\) such that \((k,k)\) is included in \(S\), which is \(min(\frac{X_1+Y_1}{2}, X_1, Y_2)\).
投稿日時:
最終更新: