[버추얼 매일 돌리기 프로젝트 #3] Codeforces Round #549 (Div. 2)

프로젝트 3일차

 

2020. 01. 03

등수 1528, 3솔, 퍼포 1483으로 민트 퍼포가 나왔다. 이러면 블루 못가는데 망했다

뇌절만 조심하면 진짜 안정적인 블루가 될 텐데, 항상 뇌절 + 구현 약점 때문에 별 고생을 다한다.

 

구현 연습 좀 하자. 제발 ㅠ

 

A.

여기서 내가 왜 뇌절을 쳤는진 모르겠지만

그냥 문제에서 요구하라는 대로 문제를 풀면 된다. 근데 그게 개같다. 그래서 5번이나 틀리고 갔다. 거의 C 뇌절급

#include <bits/stdc++.h>
#define MEM 200005
#define sanic ios_base::sync_with_stdio(0)
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll INF = 1e9+7;
const ll MOD = 1e6+7;
ll gcd(ll a, ll b){
    if(a%b) return gcd(b, a%b);
    return b;
}
ll t,n,m;
ll a[MEM], b[MEM];
ll dp[MEM][2];
main()
{
    sanic; cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
    ll j=n-1;
    while(a[j]==a[n-1]) j--;
    cout << j+1;
}

 

B. 

진짜 쉬운 그리디 문제이다.

자연수 n이 주어졌을 때 n보다 가장 작은 자연수의 각 자릿수의 곱의 최댓값을 구하는 문제이다.

그냥 이건 간단하다. 먼저 우리가 생각할 수 있는건 9가 많아야 된다는 생각을 할 수 있는데 n보다 작아야 한다는 조건이 있다. 

그러면 9만 채워놓고 자릿수가 원래것보다 더 작은 수를 만들어 놓고 마지막 자리부터 9로 바꾸면서 최대를 찾도록 그리디를 설계하면 쉽게 풀립니다. 
저번처럼 맘대로 가정해서 또 한번 틀리고 갔다. 제발 막 가정하지 말자 2트

#include <bits/stdc++.h>
#define MEM 200005
#define sanic ios_base::sync_with_stdio(0)
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll INF = 1e9+7;
const ll MOD = 1e6+7;
ll gcd(ll a, ll b){
    if(a%b) return gcd(b, a%b);
    return b;
}
ll power(ll a, ll b){
    ll r=1;
    for(ll i=0; i<b; i++)
        r *= a;
    return r;
}
ll t,n,m;
string a;
main()
{
    sanic; cin.tie(0); cout.tie(0);
    cin >> a;
    ll n=a.size();
    ll ans=power(9,n-1);
    ll d=1;
    for(int i=0; i<n; i++){
        ans = max(ans, d*power(9,n-i-1)*(a[i]-'1'));
        d=d*(a[i]-'0');
    }
    cout << max(ans,d);
}

C.

쉬운 트리 문제다. ㅋㅋ!

그냥 그 노드와 그 노드의 자식이 모두 1이면 출력하면 된다

쓸데없는 dfs는 왜 돌렸을까ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

#include <bits/stdc++.h>
#define MEM 100005
#define sanic ios_base::sync_with_stdio(0)
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll INF = 1e9+7;
const ll MOD = 1e6+7;
ll gcd(ll a, ll b){
    if(a%b) return gcd(b, a%b);
    return b;
}
ll t,n,m;
ll rs[MEM];
string a;
vector<ll> g[MEM];
ll d[MEM];
void dfs(ll a, ll b){
    d[a] = b+1;
    for(int i=0; i<g[a].size(); i++){
        ll nt = g[a][i];
        if(d[nt]) continue;
        dfs(nt, b+1);
    }
}
main()
{
    sanic; cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i=1; i<=n; i++){
        ll q,q2;
        cin >> q >> q2;
        if(q==-1) {
            m = i;
            continue;
        }
        g[q].push_back(i);
        rs[i]=q2;
    }
    dfs(m, 0);
    ll p=0;
    for(int i=1; i<=n ;i++){
        ll b=1;
        if(!rs[i]) continue;
        for(int j=0; j<g[i].size(); j++){
            if(!rs[g[i][j]]) {
                b = 0;
                break;
            }
        }
        if(b){
            cout << i << ' ';
            p++;
        }
    }
    if(!p) cout << -1;
}

 

진짜 아쉬웠던 점은 D도 할만했는데 못건드려서 아쉬웠다. 꼭 4솔을 안정적으로 할 수 있게 하자. ㅋㅋ

버추얼 레이팅 1508->1501로 하락;;

A 점수가 아주 인상적이다. ㅋㅋ!