Codeforces Round #855 (Div. 3)

div4만큼 잘 안열리는 div3 참여해봤습니다.

 

A(00:09)

https://github.com/sjmjys954646/Algorithm/blob/master/CodeforcesRound835_Div4_A_MediumNumber.cpp

A번 걸린 시간을 보면 알 수 있듯이 보자마자 어려움을 겪고 탈주각을 봤다. 소문자 대문자 섞인 문자열이 들어오는데 이것이 meow가 연속으로 쓰이느냐? 를 물어보는 문제이다. 예시를 보면 이해하기 편하다.

mmmeeeooww => YES

moew => NO

들어온 입력을 lowercase로 바꾼후 입력 string을 중복된 애들을 제거해서 meow면 YES 아니면 NO를 출력하게 코드를 짰다.

 

B(00:22)

https://github.com/sjmjys954646/Algorithm/blob/master/CodeforcesRound855_Div3_B_CountTheNumberOfPairs.cpp

소문자 대문자의 개수를 각각 배열에 집어놓고 이를 매칭시켜 ans에 더해준다.

그리고 K번만큼 돌면서 소문자 대문자 개수 / 2 만큼 제거하면서 ans에 더해주는 그리디 구현문제였다.

 

C1(00:36)

C2(00:37)

https://github.com/sjmjys954646/Algorithm/blob/master/CodeforcesRound855_Div3_C_PoweringTheHero(Easy%26Hard).cpp 

문제 이해하는데 조금 어려움을 겪었다. 0이 나오면 이전에 나왔던 수들중 가장 큰 값을 답에 더해주면 된다는 그리디 문제이다. priority queue를 이용하여 간단하게 구현했고 이는 Hard도 통과하는 코드이다.

자료형을 long long 으로 안해서 틀린 친구도 있다. 주의하도록하자

 

D(01:32 +2)

https://github.com/sjmjys954646/Algorithm/blob/master/CodeforcesRound855_Div3_D_RemoveTwoLetters.cpp

대망의 D번에서 매우 어려움을 겪었다. 

주어진 단어에 연속한 두개의 알파벳을 제거 했을때 나오는 단어의 종류의 개수를 구하는 문제이다.

처음에 드는 생각은 모든 string을 나눠서 브루트포싱으로 map에 집어놓고 개수 출력하면 되는게 아닌가했더니 string 길이가 2*10^5이었고 이는 메모리초과를 냈다.

핵심 아이디어는 2,3 index 제거 단어와  5,6 index 제거 단어가 같을려면 어떤 단어여야 될까 이다.

 

결론적으로는 제거 하기로 한 두개의 단어를 

i i+1 이라고 했을 때

  i+1 i+2 값이 같으면 같은 단어가 되고

다르면 다른 단어가 된다.

i != i + 2 인지 확인하면 되는 문제이다.

 

E1(01:59 + 1)

E2(02:00)

https://github.com/sjmjys954646/Algorithm/blob/master/CodeforcesRound855_Div3_E_UnforgivableCurse(Easy%26Hard).cpp 

개인적으로 D번보다 생각하기 쉬웠던것같은데 아마 비슷한 문제를 다른 div에서 풀어봤던 기억이있었다.

특정 index의 문자를 K, K + 1칸 뒤의 문자와 교환 할 수 있다. 이 뜻을 다시 생각해보면 5번 index의 문자를 5 + K로 움직였다가 5 + K - (K + 1) 이렇게 움직이면 4로 도착한다. 즉 버블소트처럼 바로옆으로 움직이게 만들 수 있다는 뜻이다.

하지만, 움직일 수 없는 숫자들 역시 존재하는데 이 역시 예제에 존재한다.

abcba K = 3일때 c는 움직일수가 없다 K 또는 K+1이 문자 밖으로 벗어나기 때문이다. 따라서 이러한 숫자의 범위

N - K ~ K - 1 인덱스는 결과 물과 같아야하고 이외에 알파벳들은 sorting을 통해 정답으로 만들 수 있는지를 판단하면 되는 문제이다.

 

F, G는 진짜 어떻게 풀어야할지 감도 안잡히고 생각도 안났다. 다른 사람풀이를 봐도 잘 모르겠다; bitwise사용해서 풀던데 무슨의미가 있는지 잘 모르겠었다.