ferinの競プロ帳

競プロについてのメモ

2018-2019 ACM-ICPC, Asia Seoul Regional Contest G - Secret Code

codeforces

問題ページ
(t_A, t_B, t_C) の順列6通り全てについてそれぞれ確率を計算し足し合わせることで答えが求められる．以下では 0 \leq t_A \leq t_B \leq t_C \leq S について考える．

t_B を固定したとき，A,B が出会う確率 P(A|B) は

  • w_A/S\ (s_A \leq t_B)
  • t_B/S\ \ (t_B \lt w_A)

となる．B,C が出会う確率 P(C|B) は

  • (S-t_B)/S\ (S-w_B \lt t_B)
  • w_B/S\ \ \ \ \ \ \ \ \ \ \ (t_B \leq S-w_B)

となる．t_B がその時刻である確率は 1/S で求められる．P(A|B),P(C|B) は独立であるから，A,B,C が出会う確率は P(A|B)P(C|B) で求められる．あとは t_B を0から S まで動かしたときどうなるか積分で求められればよい．制約から w_A+w_B \lt S \iff w_A \lt S-w_B である．

\int_0^S P(A|B)P(C|B)/S\ dt_B
= 1/S (\int_0^{w_A} w_Bt_B/S^2\ dt_B + \int_{w_A}^{S-w_B} w_Aw_B/S^2\ dt_B + \int_{S-w_B}^{S} w_A(S-t_B)/S^2\ dt_B)
= 1/2S^3 \times (w_A^2w_B + w_Aw_B^2 + 2w_Aw_B(S-w_A-w_B))

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll q;  
    cin >> q;  
    vector<tuple<ll, ll, ll>> ret;  
    REP(loop, q) {  
        ll s;   
        vector<ll> w(3);  
        cin >> s;  
        REP(i, 3) cin >> w[i];  
  
        ll ans = 0;  
        ans += 2 * (w[0]*w[0]*w[1] + w[1]*w[1]*w[0] + 2*w[0]*w[1]*(s-w[0]-w[1]));   
        ans += 2 * (w[0]*w[0]*w[2] + w[2]*w[2]*w[0] + 2*w[0]*w[2]*(s-w[0]-w[2]));   
        ans += 2 * (w[2]*w[2]*w[1] + w[1]*w[1]*w[2] + 2*w[2]*w[1]*(s-w[2]-w[1]));   
  
        ret.emplace_back(loop, s, ans);  
    }  
  
    sort(ALL(ret), [&](auto x, auto y) {  
        ll id1, s1, v1, id2, s2, v2;  
        tie(id1, s1, v1) = x;  
        tie(id2, s2, v2) = y;  
        v1 *= s2 * s2 * s2;  
        v2 *= s1 * s1 * s1;  
        if(v1 == v2) return id1 < id2;  
        return v1 < v2;  
    });  
    REP(i, q) cout << get<0>(ret[i])+1 << (i==q-1?'\n':' ');  
    cout << flush;  
  
    return 0;  
}