181111 - practice 1

mashup 링크: https://codeforces.com/contests/232667

실력을 늘리기 위해 스스로 풀기 어렵다고 느껴지는 난이도의 문제를 시도해야할 것 같아서 코드 포스의 문제 레이팅 기능을 사용하기로 마음먹었다.

이전에 연습해본 바로는 1900~2000대 문제도 풀기가 쉽지 않았고, 그래서 일단 4문제를 1900-2000-2000-2100짜리 문제로 고른 다음 이걸 2시간동안 푸는 연습을 하기로 했다. 4문제를 시간안에 다 풀게 되면 문제 레이팅을 하나씩 높여나가는 식으로 할 예정. 주말에 2셋 정도 돌고 평일에 못 푼 문제 업솔빙을 하면 될 거라고 생각중(좀 더 시간을 쓰고 싶지만 그럴 여유는 없으니...)

두 문제밖에 못 풀 줄 알았는데 다행히도 3문제를 풀어서 생각보다 괜찮은 스타트를 끊었다.

A. Writing Code(1900)

실제 대회 링크를 가서 보니 다들 엄청 잘 풀었다.. div1 A고 459 솔브.

쉽게 식을 유도할 수 있는 DP고, 단지 메모리 문제 때문에 토글링을 해야하는데 이런 류의 DP 문제를 안 푼지 오래됐다보니 감을 완전히 잃어서 한참 헤매다가 풀었다. 최근에 DP 문제를 많이 안 풀어서인지 조금만 난이도 있는 DP가 나오면 말리는 느낌이 있다. 연습이 많이 필요할 듯...

B. The Values You Can Make(2000)

div1 C인데 무려 414솔브고 B보다 많이 풀렸다. 실질적으로 div1 B 정도의 난이도인 듯. A번이랑 마찬가지로 식을 세우긴 어렵지 않은데 메모리 때문에 토글링해야하는 DP... 전혀 의도지 않게 연속으로 문제 연습을 한게 됐다. 조금 익숙해져서 A번보다 빨리 풀었는데, 처음에 19분정도 걸려서 코드를 짰으나 굉장히 기본적인 케이스 처리를 잘못해서 11분의 디버깅이 추가로 필요했다. 역시 연습 부족.. DP를 바텀업으로 푸는 연습을 좀 해야 할 것 같다.

C. Money Transfers(2000)

문제를 읽고 조금 고민해본 후 접근법이 마땅히 떠오르지 않아 D로 넘어갔다. D는 보자마자 접근법이 잘 떠올라서 바로 D를 풀었는데, D는 웰노운 짬뽕이고 C는 아이디어가 좀 필요한 문제인 듯 해서 꼭 풀고 넘어가야 할 것 같다. 이 문제는 div2 C인데 푼 사람이 170명... 난이도 조절에 실패한 문제인 듯.

D. Mike and Feet(2100)

여러가지 웰노운 짬뽕으로 시간복잡도를 줄이면 되는 문제였는데, 내가 푼 방식이 정해인지는 모르겠고 아무튼 여러 가지 아는 방법들을 총 동원해서 풀었다. div1B인데 무려 582명이 풀었고.. 해당 라운드에서 가장 많이 풀린 문제. 정리하고 찾아보니 정말 그 라운드에서 비교적 쉽다고 여겨지는 문제들만 해결하는데 성공했다. 

div1에서 각 문제를 푼 사람 수와 푸는데 걸리는 시간을 보니 div1에서 오렌지권이 되려면 오늘 푼 A,B,D 전부 푸는데 걸리는 시간이 20분내외여야할 것 같다. 갈 길이 멀다.