Codeforces Round 918 (Div. 4)

간만에 열리는 Div.4

턱걸이 그린이라 강등 될까봐 부계정으로 쳤다.

아마 Div.4 올솔 할 수 있는 실력이 될 때까지는 부계로 칠듯하다.

블루까지는 찍어보고 싶다.

 

D번까지는 쉽게 풀었는데 E번부터 막혔다. E번까지는 풀어야 그린 퍼포가 나오는데..

E번은 누적합으로 어떻게 하면 되지 않을까 삽질하다가 못풀었고

F번은 a_i < a_j && b_i > b_j인 (i, j) 순서쌍 개수 구하는 문제인데 inversion counting을 사용하면 되는걸 생각하지 못했다.

G번은 읽어보지도 않았다.

그래도 간만에 코드포스를 하니 재밌었다.

 

콘테스트가 끝나고 E, F번은 다시 풀어보며 업솔빙을 했고 G번은 다익스트라 문제라는데 풀고 싶을 때 풀어봐야겠다.(라고 하면 대게 안푼다)

 

https://codeforces.com/contest/1915

Dashboard - Codeforces Round 918 (Div. 4) - Codeforces

 

A번

A번 답게 정말 쉬운 문제다. 코드는 생략.

 

B번

문제를 처음 봤을 때 스도쿠인가 생각이 들었는데 크기가 3x3이라 바로 브루트포스 코드를 짰다.

https://codeforces.com/contest/1915/submission/239233671

 

C번

나무 조각의 합이 자연수의 제곱인가를 묻는 문제다.

나무 조각의 합을 sum이라 하면 i가 sqrt(sum)일 때까지만 i * i == sum 인지 검사해주면 된다.

https://codeforces.com/contest/1915/submission/239251176

 

--> 시스텟이 끝나니까 시간초과로 터졌다.

그냥 sqrt * sqrt == sum 인지만 확인해주면 됐는데 for문을 돌려서 그런 것 같다...

 

D번

문자열이 주어지는데 문자들을 자음 + 모음 또는 자음 + 모음 + 자음인경우로 끊어야 한다.

무조건 쪼개지는 경우만 주어지므로 문제가 쉬워진다.

첫 번째 문자는 무조건 자음이고 두 번째 문자는 무조건 모음이다.

그러면 세 번째 문자는 모음이 올 수가 없기 때문에 네 번째 문자가 자음인지 모음인지만 확인하며 문자를 쪼개면 된다.

https://codeforces.com/contest/1915/submission/239284150

 

E번

홀수면 값을 더하고 짝수면 값을 빼는 식으로 나온 값들을 저장한다. 나중에 계산하다가 나온 값이 이미 저장돼있는 값이면 YES, 나오지 않으면 NO를 출력하면 된다. 생각보다 간단한 문제였다. 다음번에 비슷한 문제가 나오면 풀 수 있기를..

https://codeforces.com/contest/1915/submission/239450004

 

F번

백준 1517번과 동일하게 inversion counting을 통해 풀 수 있다. 다만 E번은 시작지점, 도착지점으로 값을 2개씩 입력 받는 반면 1517번은 그냥 위치 하나만 입력을 받는다는 점이다.

그래서 어떻해야 1517번과 동일한 환경으로 만들 수 있을까 고민하다 inversion counting으로 푼 다른 사람의 코드를 보니 입력 받은 {i, j} 순서쌍을 i를 기준으로 정렬한 뒤 j를 기준으로 1517번과 같이 풀었다. 정렬을 한 것만으로 동일한 환경이 된다는게 신기했다.

https://codeforces.com/contest/1915/submission/239458871

 

F번과 비슷한 문제가 백준에도 있었는데 1615번이다. 태그에 세그먼트 트리도 있던데 1615번은 좌표 범위가 1~n으로 고정돼있지만 F번은 그렇지 않기 때문에 insersion counting으로 푸는게 좋아보인다.

pdbs인가 그런 외부헤더파일로 푼 사람들도 있던데(튜토리얼에도 pbds로 풀었다) 고인물들은 역시 보법이 다르다.