Codeforces Round #486 (Div. 3)

이번엔 D까지 풀었지만, D 문제의 레이팅이 1800이라 엄청 잘 본 라운드였다.

 

A - Diverse Team

Problem - A - Codeforces

이해하는데 8분, 코드짜는데 1분 걸린 문제다. 역시 이해빨 문제

그냥 하라는 대로 하면 된다. ㅋㅋ

자세한 건 코드 참고. 9분에 AC

딥3 A번치곤 너무 늦게 푼듯. ㅜㅜ

#include <bits/stdc++.h>
#define MEM 200006
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll MOD = 1e9+7;
ll n,m;
ll cnt[MEM], a[MEM];
set<ll> s;
int main()
{
    sanic; cin.tie(0);
    cin >> n >> m;
    for(int i=0; i<n; i++){
        ll q;
        cin >> q;
        a[i] = q;
        s.insert(q);
    }
    if(s.size()>=m){
        cout << "YES\n";
        ll b=1;
        for(int i=0; i<n; i++){
            if(cnt[a[i]]) continue;
            cnt[a[i]] = 1;
            cout << i+1 << ' ';
            if(b==m) return 0;
            b++;
        }
    }
    else cout << "NO";
}

B - Substrings Sort

Problem - B - Codeforces

그냥 정렬하고 헤당 스트링이 바로 뒤 스트링에 포함되주는지만 판별해주면 된다.

그렇게 어려운 문제는 아닌듯. 15분 AC.

#include <bits/stdc++.h>
#define MEM 200006
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll MOD = 1e9+7;
bool c(string a, string b){
    return a.size()<b.size();
}
ll n,m;
string s[MEM];
int main()
{
    sanic; cin.tie(0);
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> s[i];
    sort(s,s+n,c);
    for(int i=0; i<n-1; i++){
        if(s[i+1].find(s[i])==string::npos){
            cout << "NO";
            return 0;
        }
    }
    cout << "YES\n";
    for(int i=0; i<n; i++)
        cout << s[i] << '\n';
}

C - Equal Sums 

Problem - C - Codeforces

아니 이번꺼 지문은 왤캐 이해하기 힘드냐 ㅠㅠ

그냥 배열 두개를 골라서 원소 하나씩 뺐을때 원소들의 총합이 같은지 묻는 문제이다.

그냥 모든 경우를 생각하고 정렬한다. 그리고 거기서 합이 같고 배열이 다르면 답이다.

아 그리고 옛날에 총합을 쉽게 구하는 함수를 어쩌다 보게 됬었는데, 진짜 개꿀이더라. ㅎ

35분 AC. NO를 안써서 두 번이나 틀렸다. 

#include <bits/stdc++.h>
#define MEM 200006
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll MOD = 1e9+7;
ll n,m;
string s[MEM];
ll a[MEM];
vector<pair<ll,pi>> v;
int main()
{
    sanic; cin.tie(0);
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> m;
        for(int j=0; j<m; j++)
            cin >> a[j];
        ll sum = accumulate(a,a+m,0);
        for(int j=0; j<m; j++)
            v.push_back({sum-a[j],{i,j}});
    }
    sort(v.begin(), v.end());
    for(int i=0; i<v.size(); i++){
        if(v[i].first==v[i+1].first && v[i].second.first!=v[i+1].second.first){
            cout << "YES\n";
            cout << v[i].second.first+1 << ' ' << v[i].second.second+1 << '\n';
            cout << v[i+1].second.first+1 << ' ' << v[i+1].second.second+1 << '\n';
            return 0;
        }
    }
    cout << "NO";
}

D - Points and Powers of Two

Problem - D - Codeforces

어려운 문제인 줄 알고 거르려고 했는데, 남은 시간이 1시간 25분이라 그냥 해봤다. 

한 원소당 모든 경우를 찾는다. 이때 이 값 중 하나가 원소에 포함되는 것만 체크해주면 된다.

이는 이분탐색을 통해 할 수 있다. 그래서 이분탐색을 구현하려 하는데 이미 그런 함수가 있어서 걍 그거 썼다. ㅎ

이왜1800? 1시간 7분 AC. 끝나고 문제 레이팅 보는데 진심으로 놀랬다. 내가 이런 사람이 아닌데;;;

자세한 건 코드 참고.

#include <bits/stdc++.h>
#define MEM 200006
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll MOD = 1e9+7;
ll n,m;
string s[MEM];
ll a[MEM];
vector<pair<ll,pi>> v;
int main()
{
    sanic; cin.tie(0);
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> a[i];
    sort(a,a+n);
    vector<ll> ans={a[0]};
    for(int i=0; i<n; i++){
        for(int j=0; j<31; j++){
            ll l=a[i]-(1<<j);
            ll r=a[i]+(1<<j);
            //cout << l << ' ' << r << '\n';
            bool lr=binary_search(a,a+n,l);
            bool rr=binary_search(a,a+n,r);
            if(ans.size()<3 && lr && rr) ans = {l,a[i],r};
            else if(ans.size()<2 && lr) ans = {l,a[i]};
            else if(ans.size()<2 && rr) ans = {a[i],r};
        }
    }
    cout << ans.size() << '\n';
    for(int i=0; i<ans.size(); i++)
        cout << ans[i] << ' ';
}

E는 문제를 보고 이걸 2,5,7,0 있는지 확인하고, 각각 경우에 이걸 바꿔놓는 아이디어를 생각했는데, 구현하다 보니 개빡쳐서 접었다. F는 문제도 안 읽음 ㅋㅋㅋㅋ

D 풀었을 때 캡쳐한 현황. 랭킹이 미쳤다 ㄹㅇ

버추얼 레이팅 그린 -> 민트로 승급. 이때 실제로 했으면 역대급으로 올랐을 듯.