[CF] Codeforces Round #809 (Div. 2)

https://codeforces.com/contest/1706

Dashboard - Codeforces Round #809 (Div. 2) - Codeforces

A. Another String Minimization Problem (00:09)

그리디하게 가능한 경우만 앞에서부터 B 대신 A를 출력해주면 된다.

이때, 가능한 경우는 다음과 같다.

chk[i] = a배열에서 i의 개수라 할 때, chk[i]>0 또는 chk[m+1-i]>0 인 경우이다.  

B. Making Towers (01:27)

색 i가 연속해서 쌓이려면, 직전에 나온 i와의 인덱스 차이가 홀수여야 한다.

 

그래서 나는 처음에 마지막 나온 i를 저장하는 변수를 만들어서 풀려고 했는데, 그렇게 되면 반례가 생긴다. 마지막으로 나오지 않은 i와 연속해서 쌓이는 경우가 그 경우이다. 그래서 그다음으로 dp를 생각했었는데, 어떻게 dp를 짜야할지 떠올리지 못했다.

다음으로는 마지막으로 나오지 않은 i와 연속해서 쌓이는 경우를 어떻게 처리할 지 생각했었다. i색 탑을 최대로 쌓으려면, 항상 마지막으로 나오지 않은 i는 현재 i와 인덱스 차이가 홀수이고, 마지막 i와 인덱스 차이가 짝수인 경우뿐임을 발견했다.

 

구현은 인덱스가 홀수, 짝수인 경우를 따로 생각해서 해당 인덱스를 포함시에  최대 i색 탑의 크기를 구했다.

나는 아래와 같이 구현했는데, 지금 다시 보고 생각해 보니, pair로 홀수, 짝수 인덱스를 구분하는 역할을 cnt 배열에 덧붙여서 1차원 배열을 2차원 배열로 사용하면 일반적으로 익숙한 dp형태가 된다. 당시에는 생각하지 못했지만, 알고 보니 내가 짠 코드도 dp 코드였다.

#include <bits/stdc++.h>
#define ll long long int
#define pll pair<ll, ll>
#define pii pair<int, int>
#define X first
#define Y second
using namespace std;
const int INF=987654321;
const int MOD=1e9+7;
int dx[]={-1, 1, 0, 0};
int dy[]={0, 0, -1, 1};
void solve()
{
    ll n; cin>>n;
    vector<ll> c(n+1);
    vector<pll> cnt(n+1, {0, 0}); //홀로 끝, 짝으로 끝
    for(ll i=1;i<=n;i++) 
    {
        cin>>c[i];
        if(i%2) //홀로 끝
            cnt[c[i]].X=cnt[c[i]].Y+1;
        else //짝으로 끝
            cnt[c[i]].Y=cnt[c[i]].X+1;
    }
    for(ll i=1;i<=n;i++) cout<<max(cnt[i].X, cnt[i].Y)<<' ';
    cout<<'\n';
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int tc=1; cin>>tc;
    while(tc--) solve();
    return 0;
}

실버, 골드 dp 문제들을 좀 더 많이 풀어봐야겠다.

C. Qpwoeirut And The City (upsolved)

B를 해결하는데 거의 80분이라는 많은 시간을 써서 C번을 해결할 충분한 시간이 없었던 점이 아쉬웠다.

 

주어진 n개의 빌딩 높이 배열 h 중 양 옆 빌딩보다 큰 빌딩의 개수가 최대가 되도록 추가할 최소 빌딩 층 수를 구하는 문제이다.

 

n이 홀수면, 무조건 2번 인덱스에서 1칸씩만 건너 뛰어서 추가할 빌딩 층 수의 누적합을 만들면 된다.

n이 짝수면, 2번 인덱스에서 1칸씩만 건너 뛰어서 추가할 빌딩 층 수의 누적합을 일단 만들어 두자.

하지만 중간에 2칸씩만 건너 뛰는 부분이 1개 있어도 된다. 다만, 2칸 건너뛴 이후에 1칸씩만 건너뛰는 부분도 같이 밀거나 당겨줘야한다.

 

n이 짝수인 경우를 시간 안에 정확히 구현하지 못해서 못 풀었던 것 같다. 

 

에디토리얼 보고 구현하는 부분을 배웠다.

2칸 건너뛴 이후에도 1칸씩 건너뛰는 거 유지하는 것을

반복문을 i=n-1부터 2씩 줄이면서 get(i-1) 빼고, get(i)를 더하는 작업으로 처리한 부분이 배울만한 점인 것 같다.

아래는 이 문제의 코드이다.

#include <bits/stdc++.h>
#define ll long long int
#define pll pair<ll, ll>
#define pii pair<int, int>
#define X first
#define Y second
using namespace std;
const int INF=987654321;
const int MOD=1e9+7;
int dx[]={-1, 1, 0, 0};
int dy[]={0, 0, -1, 1};
vector<ll> h(100005);
ll get(int i)
{
    return max((max(h[i-1], h[i+1])-h[i]+1), (ll)0);
}
void solve()
{
    ll n; cin>>n;
    for(ll i=1;i<=n;i++) cin>>h[i];
    //n이 홀수면, 무조건 2번 인덱스에서 1칸만 건너뛰어야 한다.
    ll ans=0;
    if(n%2)
        for(ll i=2;i<n;i+=2) ans+=get(i);
    else //n이 짝수면, 2칸 건너뛰는 것 1번 또는 0번 해도 된다. 단, 2칸 건너뛴 이후에도 1칸씩 건너뛰는거 유지하는 것 빼먹지 말고 구현에 포함하자.
    {
        ll tot=0;
        for(int i=2;i<n;i+=2) tot+=get(i);
        ans=tot; //2칸 건너뛰는 부분 0번
        for(int i=n-1;i>1;i-=2) //2칸 건너뛰는 부분 1번
        {
            tot-=get(i-1);
            tot+=get(i);
            ans=min(ans, tot);
        }
    }
    cout<<ans<<'\n';
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int tc=1; cin>>tc;
    while(tc--) solve();
    return 0;
}