PG BATTLE 2021 せんべい参加記

はじめに

一昨年のましゅまろ、去年のせんべいに続き今年もせんべいで3完以上を目指していましたがBの考察に時間をかけすぎて2完に終わりました。

A問題

概要

確率 で勝利する勝負を回行った時に、勝ち越す確率はいくらか。

考察

回のうち、確率 の事象が 回起こる確率は

となり、この を ~ まで総和を取ればいいので、結果的には

を求めればいいことになります。

実装

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

// Combination
long long nCr(long long n, long long r) {
    long long x = 1, y = 1;
    for(long long i = 0; i < r; i++) {
        x = x * (n - i);
        y = y * (i + 1);
    }
    return x / y;
}

int main()
{
    double p;
    cin >> p;
    p /= 100;
    double q = 1.0 - p;
    double ans = 0;
    for(int i = 4; i <= 7; i++) {
        ans += nCr(7, i) * pow(p, i) * pow(q, 7 - i);
    }
    cout << fixed << setprecision(15) << ans * 100 << endl;
    return 0;
}

B問題

概要

個のクエリに答える。
各クエリに対して が与えられる。
この時、2重辺や自己辺を作らずに 頂点 辺の無向グラフを構築した時の、連結成分の数の最小値と最大値を求める。

例 : 頂点 辺の場合

最小値は以下のように辺をつないだ場合の になります

最大値は以下のように辺をつないだ場合の になります

考察

最小値に関しては簡単で、連結成分が ある状態から辺を 本増やすと連結成分を 減らすことができるので基本的には になります。
ただ、 未満になることはないので、 と の大きい方を出力すればいいです。

次に最大値です。私は、連結成分を にすることができるか、ということへの二分探索を行いました。
連結成分が になるということは、 が 頂点の完全グラフの辺の数より少なければ良いので

を満たせばよいということになります。

実装

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

// n頂点m辺で連結成分がmid個にできるか
bool isOk(long long n, long long m, long long mid) {
    long long x = n - mid + 1;
    long long sum = x * (x - 1) / 2;
    return m <= sum;
}

int main()
{
    int t;
    cin >> t;
    while(t--) {
        long long n, m;
        cin >> n >> m;
        long long ans1, ans2;
        // 最小値
        ans1 = max(1LL, n - m);
        // 最大値
        long long ok = ans1;
        long long ng = n + 1;
        while(abs(ok - ng) > 1) {
            long long mid = (ok + ng) / 2;
            if(isOk(n, m, mid)) ok = mid;
            else ng = mid;
        }
        ans2 = ok;

        cout << ans1 << " " << ans2 << endl;
    }
    return 0;
}

おわりに

学生として出られるのは今年で最後ですが来年からも時間があれば出場出来たらなと思います。