[Codeforces] Round 987

https://codeforces.com/contest/2031
199등으로 간신히 100등대 선방완료
11시에 조기퇴근
신난다

사실 9시 28분까지 침대에 붙어서 릴스 보다가

9시 32분쯤에 일어나서 분주하게 컴퓨터 키는데 레지를 안 걸어놨더라

 

망했는데? 그러니까 팀원이 엑스트라 레지 걸고 D부터 ㄱㄱ 이러길래 ㅇㅋ 하고 시작했다

(내가 팀원 중 최약체인 관계로 코포를 안 치면 고로시를 당한다)

 

일단 내가 A,B,C 미는 속도가 남들보다 많이 느리다는 거를 알아서 오렌지를 가려면 그냥 E를 꾸준히 풀어야겠다는 생각을 요즘 한다

 

E번

그래서 E부터 읽고 시작했다.

 

E를 읽고 5분~10분 정도 고민한 것 같다.

그냥 아무 생각이 안 들어서 멍때리다가, isomorphic의 정의가 root가 고정된 상태에서 정의된다는 거를 뒤늦게 알았다.

그리고 뭐, 이진트리에서 주어진 트리를 만드는건지 주어진 트리에서 이진트리를 만드는건지 좀 헷갈리다가 일단 D로 넘어갔다.

 

D번

D를 좀 읽었는데 약간 밀림점프(#) 같은 느낌이 들었다.

느낌은 느낌인거고 사실 별 관련성은 없다.

이것도 그냥 아무 생각이 안 들어서 멍때리다가, 밀림점프 접근처럼 막대기를 그리고서 점프 가능한 관계를 좀 그려보는 시도를 했다.

 

점프 시퀀스가 단순하지 않다면 애초에 해결 불가능한 문제일 것 같은 느낌이 들어서, 점프 시퀀스를 복잡하게 꼬아보는 실험을 했다.

 

그려보니까 대충, 점프 시퀀스는 무조건 그림과 같은 형태로만 이루어질 수 있다는 사실을 깨달았다.

 

그래서 적당히 세그를 꺼내들고, 코딩해서 생각보다 손쉽게 맞힐 수 있었다.

 

코드

https://codeforces.com/contest/2031/submission/291606804

const ll N = 5e5+3;
ll n;
ll a[N], mxh[N];
PURQ<ll,N> ds;

void precalc() {}
void solution(size_t tc) {
    cin >> n;
    rep(i,1,n) cin >> a[i];
    
    priority_queue<ll> pq;
    pq.push(0);
    rep(i,1,n) {
        mxh[i] = max(a[i],pq.top());
        pq.push(a[i]);
    }
    
    ds.set(n+1,0,[](ll x, ll y){ return max(x,y); });
    per(i,1,n) {
        Mup(mxh[i], ds.query(1,mxh[i]-1));
        ds.update(a[i], mxh[i]);
    }
    
    rep(i,1,n) {
        cout << mxh[i] << ' ';
    }
    cout << '\n';
}

 

C번

D를 풀고 나니 사람들이 A,B,C 솔브를 꽤 해놓은 것이 보였다.

C가 좀 쉬운가? 싶어서 일단 C를 봤다.

 

지문을 읽다가 하나의 bread에 정확히 하나의 filling이 대응된다는 말이 안 보여서 이해에 어려움을 겪었는데, 나만 그런 것 같다.

 

일단 짝수일 경우에는 너무 자명하게 11/22/33/... 꼴이 답이 되는 것이 보였다.

홀수일 경우가 문제인데, 당연히 가능한 최소의 길이 이후에 ii/jj/...를 덧붙여서 구성해야 할 것으로 보였다.

 

그래서 최소의 경우를 좀 고민해봤는데, 아무래도 피타고라스 삼원쌍을 이용한 접근이 필요한 것 같았다.

C에 웬 씹덕정수론이 나오지? 하면서 이게 맞나 살짝 돌이켜봤는데, 이거 말고는 말이 안 되는 것 같아서 인터넷에 피타고라스 삼원쌍 리스트를 검색했다.

 

확실히 (3,4,5) 튜플보다 괜찮은거는 없는게 확실해보여서 일단 이걸 그리고.. 남는 숫자를 잘 끼워넣어서 연속부분이 전부 짝수가 나오도록 조정을 해봤다.

그러다 보니까 하한이 정확히 27에 걸렸고, 확실히 27이 맞는지 좀 더 신중하게 고민해본 뒤 짜서 냈다.

다행히 한 번에 맞힐 수 있었다.

 

코드

https://codeforces.com/contest/2031/submission/291621850

void solution(size_t tc) {
    ll n;
    cin >> n;
    if (n%2==0) {
        rep(i,1,n) {
            cout << (i+1)/2 << ' ';
        }
        cout << '\n';
    } else {
        if (n<27)
            cout << "-1\n";
        else {
            cout << "3 1 2 2 3 ";
            rep(i,4,9) cout << i << ' ' << i << ' ';
            cout << "1 ";
            rep(i,10,13) cout << i << ' ' << i << ' ';
            cout << "1 ";
            rep(i,1,n-27) {
                cout << (i-1)/2+14 << ' ';
            }
            cout << '\n';
        }
    }
}

 

E번

생각보다 C,D를 풀었는데 시간이 남길래 불확실한 A,B보다 E를 먼저 택하기로 결정했다.

아까 읽을때는 뭔가 지문의 감성을 잘못 이해해서 파라매트릭 뭐 이런거 하라는건가? 싶었는데,

다시 이해하니까 그냥 sublinear 시간에 트리 DP로 깔끔하게 끝나야 할 것 같다는 느낌이 들었다.

 

그래서 뭐 정의는 대충

$\mathrm{dp}(u):=u^{\downarrow}$를 완전이진트리로 바꿀때, 가능한 최소 높이

로 내리고 예제를 따라 그려봤다.

 

자식들 dp값을 늘어놓고, 작은 dp값들부터 합치는 그리디가 성립한다는 것을 깨달았고, 코딩해서 맞혔다.

자주 해본 것 같은 것들이라 쉽게쉽게 구현할 수 있었다.

 

코드

https://codeforces.com/contest/2031/submission/291636069

const ll N = 1e6+3;
ll n, dp[N];
vi C[N];

void dfs(ll s=1, ll e=0) {
    priority_queue<ll,vector<ll>,greater<>> pq;
    for (auto u : C[s]) if (u!=e) {
        dfs(u,s);
        pq.push(dp[u]);
    }
    while (siz(pq)>2) {
        ll x = pq.top(); pq.pop();
        ll y = pq.top(); pq.pop();
        pq.push(max(x,y)+1);
    }
    if (siz(pq)==0) {
        dp[s] = 0;
    }
    else if (siz(pq)==1) {
        dp[s] = pq.top()+1;
    }
    else {
        ll x = pq.top(); pq.pop();
        ll y = pq.top(); pq.pop();
        dp[s] = max(x,y)+1;
    }
}

void precalc() {}
void solution(size_t tc) {
    cin >> n;
    rep(i,1,n) C[i].clear();
    rep(i,2,n) {
        ll p; cin >> p;
        C[p].push_back(i);
    }
    dfs();
    cout << dp[1] << '\n';
}

 

A번

C,D,E를 푼 시점이 1:13 시점이라서, 설마~ 풀겠지 하면서 마음놓고 A를 봤다.

A를 딱 보고서 그냥 생각없이 적당히 찍어서 냈다가 WA를 받았다.

오늘 컨테에서 적립한 유일한 오답이 A에서 나왔다 ㅋㅋ

 

시작할때 A부터 순서대로 봤으면 멘탈 흔들릴 뻔 했다 ㅋㅋㅋㅋ

 

코드

https://codeforces.com/contest/2031/submission/291639549

const ll N = 53;
ll n, h[N];
ll cnt[N];

void precalc() {}
void solution(size_t tc) {
    cin >> n;
    rep(i,1,n) cnt[i]=0;
    rep(i,1,n) {
        cin >> h[i];
        cnt[h[i]]++;
    }
    ll c = *max_element(cnt+1,cnt+n+1);
    cout << n-c << '\n';
}

 

B번

그냥 적당히 적당히 푼 것 같다.

무난하게 AC를 받았고, 1:27에 5솔브한 뒤 퇴근을 조질 수 있었다!

 

코드

https://codeforces.com/contest/2031/submission/291642648

const ll N = 2e5+3;
ll n, p[N];
ll mx[N], mn[N];

void precalc() {}
void solution(size_t tc) {
    cin >> n;
    rep(i,1,n) cin >> p[i];
    rep(i,1,n) {
        mx[i] = max(mx[i-1],p[i]);
    }
    mn[n+1] = n+1;
    per(i,1,n) {
        mn[i] = min(mn[i+1], p[i]);
    }
    rep(i,1,n-1) {
        if (mx[i]>mn[i]+1) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

 

감상평

개인적으로는 괜찮은 셋인 것 같다.

모든 문제가 최소한의 생각을 요구하고 있었고,

난이도 밸런스는 이 정도가 딱 div.2 참가자들한테 좋은거 아닐까 하고 생각해본다.

 

체감 난이도?

A: S5

B: S4

C: G3

D: P3

E: P3