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

私を青コーダーにしてくれた、思い出の一問になりました。

問題

https://codeforces.com/contest/1313/problem/B

問題概要

コンテストは二つのラウンドからなり、各ラウンドの順位を足したものがポイントとなる。「自分を含む自分以下のポイントを持つ参加者の人数」が、最終的な順位として与えられる。なお、各ラウンドの順位については同点はなく、それぞれ独立した順位がつくとする。

今回のコンテストはn人が参加し、あなたは各ラウンドでそれぞれx位とy位となった。あなたが取りうる最終的な順位として、最悪の場合と最高の場合を答えよ。

考察

まず最悪のケースを考えます。この場合、自分のポイント以下の人数を最大化する必要があります。

例えばサンプル1のケース、5人の参加者に対して順位が1位と3位だった場合、ポイントは4です。よって4以下のポイントを持つ参加者を最大化する必要があります。

ここで、仮に両方1位の参加者がいたとすると2ポイントとなり確実に自分を上回りますが、これは言うまでもなくもったいないです。貴重な1位を無駄に消費してはいけません。無駄にしないためには、できるだけ高順位を消費しないように、4ポイントちょうどをたくさん作るのがいいということになります。

じゃあ4ポイントをどう作るかということになるわけですが、これは(1, 3)(2, 2)(3, 1)の3通りですね。要するに自分のポイントから1引いた分だけ（自分を含めて）同ポイントの参加者が作れるので、最悪のケースの順位は「自分のポイント - 1」となるわけです。

が、自分のポイントが参加人数 + 1より大きかった場合、この計算では順位が参加人数を上回ってしまうので、この場合の最悪の順位は参加人数と同じ、つまり最下位とします。

次に最高のケースを考えます。この場合、自分のポイントより大きい人数を最大化する必要があります。

サンプル1のケースで考えると、自分のポイントは4なので、５以上のポイントを持つ参加者を最大化しなければなりません。また先と同様に、両方5位の参加者がいたとしてポイントは10ですが、これはもったいないです。*1　なので、ちょうど5を作るのがいいということになります。

これは(1, 4)(2, 3)(3, 2)(4, 1)のように作れて、下位のほうが余りますが適当に足し合わせれば5より小さくなることはありません。なので、このケースでは最高は1位となります。

ではサンプル2ではどうなるでしょうか。6人の参加者に対して、3位と4位で7ポイントです。8をたくさん作りたいので作ります。(2, 6)(3, 5)(4, 4)(5, 3)(6, 2)が作れます。しかし、どちらかが1位の参加者については、もう一方がたとえ最下位の6位となっても7ポイントなので、自分を下回らせることができません。つまり、どちらかのラウンドで「自分のポイント - 参加人数 」以上の順位を取っている参加者については、どうしても自分を下回らせることができないわけです。

よって、自分の取りうる最高の順位は、「自分のポイント - 参加人数 + 1」となるわけです。ただし、これが0以下になる場合は自分が1位になれるケース（自分のポイントが十分に小さい）なので、1位とすればよいです。

実装的には、maxとminを駆使すると簡潔に書けますけど、慣れてないとわかりづらいかもしれません。（少なくとも私は仕事ではこういう書き方はまずしません。競プロでは好んで使用しますが。）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, x, y;
        cin >> n >> x >> y;
        int m = x + y;
        cout << max(1, min(n, m - n + 1)) << " " << min(m - 1, n) << endl;
    }
}

*1:実はこのサンプルだと(5, 5)で作っても問題ないですけど。