Codeforces Round #622 (Div. 2) - B. Different Rules

codeforces.com

概要

n人の参加者がいる2回コンテストが行われた。Senくんは1回目ではx位、2回目ではy位であった。総合順位は、2回のコンテストで取った順位の和を、全員分広義単調減少になるようにならべて、前からの順位とする。
ほかの参加者が1回目と2回目でどのような成績を取ったのかは不明だが、Senくんの取りうる最高順位と最低順位を答えよ。
同列で並んでる場合は、最後尾の同列者の前から数えての順位を同列の人全員に与えるとする。
制約：　1 <= x, y <= n <= 10^9

考察

(今回は大分時間かけて長考して人の解説とかもいっぱい見たのでACするまでは書かない)

このような問題は、うまく数学の条件でいいかえる必要がある。
答えから言うと、次のように言い換えて考えるとわかりやすい。

総合順位をできるだけわるくする＝順位の和がx+y以下になる人をできるだけ多く作る。
総合順位をできるだけよくする＝順位の和がx+y+1以上になる人をできるだけ多く作る。

参加者は一定で、総合順位は2つの順位の和によって決まるので、もちろん参加者全員の2つのコンテストの順位の和も一定である(n*(n+1))。そして、手元でマッチングさせてみるとわかるが、1~nと並ぶ2つの数列で、和が一定になるようにできるマッチングの数が最大化されるのは和がn+1のときである。

つまり、そろえる和がn+1に近ければ(絶対値的な意味で)、作れるペアの数は多くなるということである。作れるペアの数が多くなるということは、条件を満たす(最大化するor最小化する)ためのペアの数を多くできるということである。

これらの考察から、集めたい値の範囲にn+1が入ってるのならば、n+1を集める！というが最も効率が良いことだとわかる。入ってない場合は、その集めたい値のボーダーの値を集めるのが、一番よい。(一番n+1と絶対値が近いので)

つまり、x+yやx+y+1がn+1との大小で場合分けして、考察するとうまくいく。

x+y>=n+1のときの順位最大化と、x+y+1<=n+1の時の順位最小化

上の条件を満たすとき、n+1は範囲に入ってるといえる。よって、n+1を目安に集めればよい。
そのときは、1とn、2とn-1と組めるものを組み、ペアがすでに使われてるなどで組めなかった残り物同士を合わせれば簡単に和がn+1以下(最大化)or以上(最小化)のペアがn-1ペア作れる。

下に2つの例を置く。

n=5, x=3, y=4のとき

第1回	第2回	合計
1	5	6
2	?	?
3(本人)	4(本人)	7
4	2	6
5	1	6

とまずは、xとyの影響がないところで、和がn+1になれるように組む。そして、残った1つは、残り物同士(今回は3)を合わせればよい。残り物同士は、簡単な証明でn+1以下になるとわかる。

第1回	第2回	合計	総合順位
1	5	6	4
2	3	5	1
3(本人)	4(本人)	7	5(n位)
4	2	6	4
5	1	6	4

n=5, x=1, y=3のとき

第1回	第2回	合計
1(本人)	3(本人)	4
2	4	6
3	?	?
4	2	6
5	1	6

とまずは、xとyの影響がないところで、和がn+1になれるように組む。そして、残った1つは、残り物同士(今回は5)を合わせればよい。残り物同士は、簡単な証明でn+1以上になるとわかる。

第1回	第2回	合計	総合順位
1(本人)	5(本人)	6	1
2	4	6	4
3	5	8	5
4	2	6	4
5	1	6	4

x+y<=nのときの順位最大化と、x+y+1>=nの時の順位最小化

先ほどの余事象にあたるのだが、これはx+y or x+y+1が和になるように集めるべきである。

具体的には、次のようにする。(さきほどのn+1で集める部分も、別アプローチでやってるが)

ACソースコード：
Submission #72145488 - Codeforces

一言

この記事をきっかけに競プロやる気がまた再燃期に入ったからがんばる。

Special Thanks

https://www.bilibili.com/video/av91242850?p=2

https://blog.csdn.net/qq_45458915/article/details/104472157

对以上的两位大师表示衷心感谢！