Codeforces Round #627 (Div. 3) Solution

2020.03.12 저녁 (한국 기준)에 열린 라운드 627의 문제 풀이를 해볼려합니다.

 

이번에는 총 6문제가 출제되었고 5문제를 풀었습니다.

 

푼 문제

대회 문제 목록:

http://codeforces.com/contest/1324

Dashboard - Codeforces Round #627 (Div. 3) - Codeforces

 

대회 에디토리얼:

https://codeforces.com/blog/entry/74714

Codeforces Round #627 (Div. 3) Editorial - Codeforces

 

저번에도 말씀드린것과 같이 에디토리얼을 빠르게 보는 편이 아니라 

아직 에디토리얼은 안봤습니다. 더 정확한 풀이를 원하신다면 에디토리얼을 봐주시는게 좋을 것 같습니다.

 

A. Yet Another Tetris Problem

쉽게 말하면 주어지는 모든 숫자가 짝수 혹은 홀수인가를 확인하면 되는 문제입니다.

왜 그렇게 판단되는지는 그림을 한번 그려보고 문제의 조건에 맞게 확인해보세요

 

제출코드: https://github.com/shinkeonkim/Today_PS/blob/master/codeforces/Round%20%23627/A.py

 

B. Yet Another Palindrome Problem

부분 배열(문자열이라 생각하고) 중에 길이가 3이상인 팰린드롬이 있는지 확인하는 문제입니다.

그럼 쉽게 생각해보면, 주어지는 문자마다 위치들을 저장해놓고 저장된 위치의 개수가 2개 이상이고 그 위치 중 최대값과 최소값의 차이가 2이상인지 검사하면 됩니다.

 

제출코드: https://github.com/shinkeonkim/Today_PS/blob/master/codeforces/Round%20%23627/B.py

 

C. Frog Jumps

처음 이 문제를 봤을 때는 "이게 뭔소리야" 라는 생각을 했습니다. 알고보니 간단한 문제였습니다.

일단 개구리가 마지막 지점에 도착을 해야 그 중에서 최대를 찾을 수 있기 때문에 출발점과 도착점에 임의로 R을 부여합니다. 예를 들어 s가 "LRLRRLL"라면 "RLRLRRLLR" 로 말이죠. 그리고 나서 R 과 R 사이의 거리중 최대값을 찾아내면 끝납니다.

 

제출코드: https://github.com/shinkeonkim/Today_PS/blob/master/codeforces/Round%20%23627/C.py

 

D. Pair of Topics

이 문제에서 2번이나 틀렸는데, 하나는 TLE였고 하나는 long long으로 답을 도출 안해서였습니다.

생각보다 이 문제는 쉬우면서 어려웠는데, 문제의 형태를 비꼬니 백준에 있는 문제였습니다. 그리고 유명한 시리즈의 문제였습니다.

https://www.acmicpc.net/problem/13537

13537번: 수열과 쿼리 1

바로 이문제입니다.

이 문제의 풀이는 merge sort tree라는 살짝의 변태적인 문제이긴한데, 그럭저럭 알아두면 많이 유용한 알고리즘입니다. 아, 이제 어떻게 D번 문제가 수열과 쿼리1과 같아지냐를 설명해보자면, i<j 일때 Ai + Aj > Bi + Bj 인 (i,j)의 개수를 세야하는데 Ai - Bi > -Aj + Bj 로 바꾸고 임의의 k에 대해 A_k - B_k = C_k로 치환한다면, Ci > -Cj의 순서쌍을 찾는 것입니다.  그러면 이제 그대로 위의 문제 풀이를 적용하고 쿼리의 범위를 조정하면 끝납니다.

 

제출코드: https://github.com/shinkeonkim/Today_PS/blob/master/codeforces/Round%20%23627/D.cpp

 

 E. Sleeping Schedule

DP 문제 입니다.

DP 배열을 다음과 같이 선언하면 됩니다.

D[i][j]: i번째 과정까지 진행하고 현재 시간이 j일 때, good time의 최대 갯수

자세하게 구현된 내용은 코드를 보시면 될 것 같습니다.

 

제출코드: https://github.com/shinkeonkim/Today_PS/blob/master/codeforces/Round%20%23627/E.cpp

 

F: Maximum White Subtree

대회 시간이 부족해 풀지 못했습니다 :(..

 

 

이번 Div3는 다른때보다 쉬웠던 것 같습니다.

꽤 쉬운 생각으로 풀리는 문제들이었습니다.

Rmx