#798 div2 6/27 virtual

https://codeforces.com/contest/1689

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

매일 아침 코포 버츄얼 돌린 첫날. 머리도 깰겸 

 

A 

a string, b string 에서 하나하나 뽑아서 사전순으로 가장 앞선 string c를 만드려고 한다. 

a,b 둘 중 하나가 빌때까지 반복하고, 연달아서 a,b에서 뽑는 것은 k번까지 제한이 있다. 

 

a, b 둘다 정렬하고 a, b index 앞부터 끝날때까지 반복한다. 

a index, b index 중 더 빠른 거 두고, 연달아 k번 썼는지 확인한다 

 

단순 구현문제인데 생각이 또 둥둥 떠다닌다. 잡아서 써보자

 

B

순열에서 원래 순서랑 모두 다 다르게, 사전순 가장 앞서게 배열하자는 문제 

greedy하게 지금 위치가 아니면서 가장 빠른 걸 앞으로 둔다. 

 

근데 이렇게 하다보면 맨마지막 위치에서 자기 자신이 되는 경우가 발생할 수 있다. 

이거에 대한 case만 조정해주면 된다. 

 

그리디하게 된다는 것이 증명이 어려웠다. 간단한 증명이라도 제대로 하고 넘어가는 연습을 하자.

 

C

업솔빙함 

 

문제 자체는 그렇게 어렵지는 않았음 

트리의 root부터 감염이 시작되어서 한턴에 하나씩만 연결을 끊을 수 있을 때 

감염 안되는 최대 노드 수를 구하는 문제 

 

처음에는 greedy하게 생각함 어떤 노드가 root인 subtree의 노드 수를 미리 구해두고

root부터 둘 중 큰거 선택하는 경우 

 

하지만 반례 발견 

아이디어는 괜찮지만 증명이 된것만 써먹자

 

 dp로 모든 경우를 파악하는게 가능하다. 이진트리이기 때문에 

n이 3*10^5라도 log(3*10^5) 의 선택에 대해서 확인하면 되고, 이 모든 경우의 수는 3*10^5 이기 때문에 

가능 

 

구현이 까다로웠는데 될 것 같다고 생각할 때가 제일 위험하다 생각이 루프에 빠져서 발전이 안되는데 

생각적는 연습을 하자. 간단한 거라도 증명하고, 체계화해서 문제를 풀자 어차피 알고리즘 지식이 필요해서 하는 거 아니니깐