Codeforces Round #479 (Div. 3)

코포 버추얼을 매일 돌릴 예정이다.

 

이번 라운드가 쉬워서 그런지 F 빼고 다 풀었다.

 

A - Wrong Subtraction

Problem - A - Codeforces

걍 구현. 

2분에 AC

#include <bits/stdc++.h>
#define MEM 100
#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;
int main()
{
    sanic; cin.tie(0);
    cin >> n >> m;
    for(int i=0; i<m; i++){
        if(n%10) n--;
        else n/=10;
    }
    cout << n;
}

B - Two-gram

Problem - B - Codeforces

애도 구냥 구현.

STL 오류 때문에 시간을 많이 뺏겨 아쉬웠던 문제

17분 AC

#include <bits/stdc++.h>
#define MEM 100
#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;
map<string, ll> p;
set<pair<ll, string>> d;
int main()
{
    sanic; cin.tie(0);
    cin >> n;
    cin >> s;
    for(int i=0; i<n-1; i++){
        string o=s.substr(i,2);
        p[o]++;
    }
    for(auto it=p.begin(); it!=p.end(); it++)
		d.insert({-(it->second), it->first});
    for(auto const &it : d){
        cout << it.second << '\n';
        return 0;
    }
}

C - Less or Equal

Problem - C - Codeforces

진짜 실수하기 좋은 문제.

문제를 잘 읽는게 중요하다.

a_i<a_(i+1)임을 가정했을 때

a_k<=x<a_(k+1) 을 만족하는 x를 구하라는 건데, x가 존재하지 않을 경우는 바로 a_k==a_(k+1)인 경우이다.

그러므로 a_k==a_(k+1)이면 -1, a_k!=a_(k+1)이면 a_k를 출력하면 된다.

34분 AC

#include <bits/stdc++.h>
#define MEM 200005
#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,k;
ll a[MEM];
int main()
{
    sanic; cin.tie(0);
    cin >> n >> k;
    for(int i=0; i<n; i++)
        cin >> a[i];
    sort(a,a+n);
    if(n==k) {
        if(a[n-1]<=1e9)cout << a[n-1];
        else cout <<-1;
        return 0;
    }
    else if(k==0){
        if(a[0]-1>0) cout << a[0]-1;
        else cout << -1;
        return 0;
    }
    if(a[k-1]!=a[k])
        cout << a[k-1];
    else cout << -1;
}

D - Divide by three, multiply by two

Problem - D - Codeforces

www.acmicpc.net/problem/16936

16936번: 나3곱2

이 문제와 동일한 문제였다. 이 문제의 존재를 알고 있었지만 생각조차 해보지 않은 문제라 다행이었다.

일단 경로가 되는 것들끼리 이어줘서 그래프를 만들자.

이때 bfs를 통해 각 상태를 저장해주면서 답을 구해주면 된다.

자세한건 코드 참고.

여담으로 N<=100이여서 저렇게 해도 시간이 충분하다. 

59분에 AC

#include <bits/stdc++.h>
#define MEM 108
#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,k;
ll a[MEM];
vector<ll> g[MEM];
void bfs(ll x){
    queue<pair<ll, vector<ll>>> q;
    q.push({x, {x}});
    while(!q.empty()){
        ll c=q.front().first;
        vector<ll> v=q.front().second;
        q.pop();
        if(v.size()==n){
            for(int i=0; i<n; i++)
                cout << a[v[i]] << ' ';
            exit(0);
        }
        for(int i=0; i<g[c].size(); i++){
            ll nxt=g[c][i];
            bool b=1;
            for(int j=0; j<v.size(); j++)
                if(nxt==v[j]) b=0;
            if(b){
                v.push_back(nxt);
                q.push({nxt, v});
            }
        }
    }
}
int main()
{
    sanic; cin.tie(0);
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> a[i];
    sort(a,a+n);
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            if(a[i]*2==a[j]) g[i].push_back(j);
            else if(a[j]/3==a[i] && !(a[j]%3)) g[j].push_back(i);
        }
    }
    for(int i=0; i<n; i++)
        bfs(i);
}

E - Cyclic Components

Problem - E - Codeforces

그냥 전형적인 사이클 갯수를 출력하는 것이다.

문제에서 주어진 사이클의 특징은 이렇다.

-모든 노드의 degree가 2다.

이를 이용해서 degree가 2인 걸 모두 표시하고, 맘편하게 DFS 돌리면 끝난다.

자세한건 코드 참고.

1시간 39분에 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;
vector<ll> g[MEM],a;
ll d[MEM], v[MEM];
 
void dfs(ll t){
    v[t] = 1;
    a.push_back(t);
    for(int i=0; i<g[t].size(); i++)
        if(!v[g[t][i]])
            dfs(g[t][i]);
}
int main()
{
    sanic; cin.tie(0);
    cin >> n >> m;
    for(int i=0; i<m; i++){
        ll q1,q2;
        cin >> q1 >> q2;
        g[q1].push_back(q2);
        g[q2].push_back(q1);
    }
    for(int i=1; i<=n; i++)
        if(g[i].size()==2) d[i]=1;
    ll ans=0;
    for(int i=1; i<=n; i++){
        if(!v[i] && d[i]){
            dfs(i);
            bool h=1;
            for(int i=0; i<a.size(); i++)
                if(!d[a[i]]) h=0;
            if(h) ans++;
            a.clear();
        }
    }
    cout << ans;
}

F는 풀 수 있었으나 귀찮아서 안 풀었다. 쫄아서 안 푼거 아님. 아무튼 아님 ㅡㅡ

쨌든 신기록이니 기분 좋다.

1시간 46분에 캡쳐한 현황

실제로 했으면 +107이었다. 와...