[코포 라운드 글 #1] Codeforces Round #695 (Div. 2)

Round : Codeforces Round #695 (Div. 2)

rank : 2630

solved : 2

Performance : 1545
Rating Change : +42 (1434->1476)

 

 

그 당시 망했다고 생각했던 라운드 (실제로 그렇게 잘 본 라운드도 아니었다;;)

B의 상당한 뇌절 때문에 말렸다. 뇌절을 줄이기 위해 좀 더 버추얼을 열심히 하자.

 

A. codeforces.com/contest/1467/problem/A

Problem - A - Codeforces

지문을 죽여버리고 싶은 문제이다. 저것 때문에 A 솔브가 늦어졌다.

그리디하게 생각하여 풀 수 있는 문제다.

먼저 첫 자리가 9여야 한다는 점을 감안하여 생각하면, 두번째 자리가 8이 되도록만 만들면 그것이 최대가 된다.

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

B. codeforces.com/contest/1467/problem/B

Problem - B - Codeforces

저 배열에서 3개의 연속된 수를 고린다고 해보자. 만약 그 연속된 3개의 수가 힐 또는 벨리라면 우리는 가운데 값을 왼쪽 값 또는 오른쪽 값으로 변환하여 최소 한개~최대 세개의 힐 또는 벨리를 없앨 수 있다. (최소 같은 경우 두개를 없애고 다른 쪽에 하나가 생겨날 수 있는 경우가 있고 최대의 경우 왼쪽 오른쪽 모두 다 없어졌을 때다.)

이러한 정보를 이용해 힐 또는 벨리가 있는 3개의 연속 된 수를 찾은 다음, 없앨 수 있는 최대 갯수를 구하면 된다.  

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