AtCoder Beginner Contest 194

A. I Scream

milk solid와 milk fat을 비교하여 ice cream, ice milk, lacto ice, flavored ice로 나누는 문제

입력으로 주어지는 milk-solid-not fat과 milk fat을 더하면 milk solid의 값을 알 수 있다.

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("input.txt","r",stdin);
    int A,B;
    cin>>A>>B;
    int ans=4;
    if(A+B>=15 && B>=8) ans=1;
    else if(A+B>=10 && B>=3) ans=2;
    else if(A+B>=3) ans=3;
    cout<<ans;
    return 0;
}

---

B. Job Assignment

A와 B가 일을 동시에 하게 될 때 오래 걸리는 시간의 최솟값을 구하는 문제이다.

만약 혼자서 두 일을 연달아 하게되는 것이 시간이 덜 든다면 그것이 정답이 된다.

$N$의 범위가 1000이내이기 때문에 완전탐색으로 계산하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("input.txt","r",stdin);
    int n;
    cin>>n;
    vector<int> a(n), b(n);
    for(int i=0;i<n;i++) cin>>a[i]>>b[i];
    int ans=1e9;
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            if(i!=j) {
                ans=min(ans,max(a[i],b[j]));
            }
            else ans=min(ans,a[i]+b[j]);
        }
    }
    cout<<ans;
    return 0;
}

---

C. Squared Error

$\sum_{i=2}^n\sum_{j=1}^{i-1}(A_i-A_j)^2$의 값을 계산하는 문제이다.

n의 범위가 $3\times10^5$까지 이므로 $O(n^2)$은 TLE를 발생시킨다. 위의 식을 다음과 같이 정리하면 $O(n)$에 해결할 수 있다.

$\begin{matrix} \sum_{i=2}^n\sum_{j=1}^{i-1}(A_i-A_j)^2 &=& \frac{1}{2}(\sum_{i=1}^n\sum_{j=1}^n(A_i-A_j)^2) \space(\because (A_i-A_i)^2=0) \\ &=& \frac{1}{2}(\sum_{i=1}^{n}\sum_{j=1}^{n}(A_i^2+A_j^2-2A_iA_j)) \\ &=& \frac{1}{2}(2N\sum_{i=1}^{n}A_i^2-2\sum_{i=1}^n(A_i\sum_{j=1}^{n}A_j)) \\ &=& N\sum_{i=1}^nA_i^2-(\sum_{i=1}^nA_i)^2\end{matrix}$

#include <iostream>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("input.txt","r",stdin);
    int n;
    cin>>n;
    ll sum=0, sum2=0;
    for(int i=0;i<n;i++) {
        ll x;
        cin>>x;
        sum+=(x*x);
        sum2+=x;
    }
    cout<<n*sum-sum2*sum2<<endl;
    return 0;
}

---

D. Journey

N개의 정점이 존재하고 어떠한 간선도 없는 경우 Takahashi가 1번 정점에서 어떠한 정점으로 $\frac{1}{N}$의 확률로 이동가능하고 간선도 만들 수 있을 때 그래프를 연결시키기 위한 평균 횟수를 구하는 문제이다.

다음 증명은 editorial을 보고 정리했다.

어떠한 X를 기댓값으로 가정하자. 이동에 성공하면 다음 정점으로 이동하고 실패하면 현재 정점에 있어야 하므로 다음과 같은 식을 만들 수 있다.

• $X=1+(1-p)X$

즉, $pX=1$이므로 $X=\frac{1}{p}$이다.

이 문제에서 Takahashi가 이동에 성공하면 두 정점이 이어지는데 이것을 집합 $S$으로 표현할 수 있다. 또한, $\left\lvert S \right\rvert$는 $S$의 원소 개수라고 정의한다.

$\left\lvert S \right\rvert$의 값이 1이 증가하는 것은 집합 $S$에 포함되지 않은 정점에 Takahashi가 확률을 뚫고 이동에 성공한 것과 같다.

그렇다면 우리는 집합 $S$에 포함되지 않은 정점을 처음으로 선택할 때 예상되는 횟수는 $\frac{1}{\frac{N-\left\lvert S \right\rvert}{N}} = \frac{N}{N-\left\lvert S \right\rvert}$이다.

우리는 정점 1개부터 시작하므로 $\frac{N}{N-1}+\frac{N}{N-2}+…+\frac{N}{1}$이 답이 된다.

따라서 $O(N)$의 시간 복잡도로 문제를 해결할 수 있다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("input.txt","r",stdin);
    ll n;
    cin>>n;
    double ans=0;
    for(ll i=1;i<n;i++) {
        ans+=(double)n/(n-i);
    }
    cout.precision(6);
    cout<<fixed;
    cout<<ans;
    return 0;
}