Codeforces Round #849 (Div. 4)

한달에 한번씩 열리는 div4 참여해봤습니다.

 

 

A(00:03)

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

주어진 문자가 codeforces 중 하나인지 확인한다.

if문 이용해서 구현

 

B(00:06)

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

0,0 에서 주어진 경로대로 따라가되 1,1 지날시 flag on

 

C(00:11)

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

주어진 문자열에서 양 옆 끝에서 0,1 또는 1,0 제거 

 

D(00:56 +2)

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

문자열 안에 쓰인 문자의 종류의 개수를 세는 함수 f(x) 가 있을때 두개의 부분문자열의 f(x)의 합이 최대가 되도록 하라.

여기서 부터 난항을 겪었는데

문자열을 일일이 나눠서 f(x)값을 set으로 구현해서 넣으면 O(N^2)으로 시간초과가 난다.

 

slicing 하는 느낌으로 map 두개에  
ABCDEFG 를 A | BCDEFG
이런 식으로 나눠놓은후  | 를 오른쪽으로 한칸 한칸 옮기며 추가하고 제거하는 느낌으로
map의 사이즈의 합을 ans로 갱신 시켜준다.

 

N크기를 잘못보고 맞았다고 생각하고 넘어간 후 다시 생각해 내는데 시간이 조금 걸렸다.

 

E(01:48 +2)

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

애드혹 문제, 생각하기 너무 힘든것 같다.

수열이 주어졌을때 숫자 한개와 그 오른쪽 숫자에 -를 붙일 수 있다.

이 때 합이 최대가 되도록 하는 값을 구하시오

 

연속한 숫자 두개에 -를 붙인다는 것은 - 를 옮긴다 라고 해석할 수 있고 연속한 음수 두개는 둘다 양수로 만들 수 있다.

따라서, 음수의 개수를 센 후 나머지가 0일때는 다 더하고 1일때는 가장 작은값을 음수로 만든다.

 

G1(01:32 +1)

https://github.com/sjmjys954646/Algorithm/blob/master/CodeforcesRound849_Div4_G1_Teleporters(EasyVersion).cpp 

거리와 cost를 미리 계산하고 가장 적은값부터 방문하면 최적의 값을 얻을 수 있다.

그리디한 풀이

 

패널티가 많아서 좋은 성적을 거두지는 못했지만 전 보다 나은 성적인것같다.

F번 같은 경우에는 읽어봤더니 세그인것같아서 건너뛰었는데

다른 사람들은 이분탐색을 이용하여 구현하였다.