#682 div2 11/13

codeforces.com/contest/1438

Dashboard - Codeforces Round #682 (Div. 2) - Codeforces

코포후기를 항상 몇솔 몇솔 이런식으로만 적었었는데 과연 그게 나에게 무슨 의미가 있을까 싶어서 

좀 더 구체적으로 써볼까 한다.

 

그러면 좀 더 기억이 생생할 때 써야할것 같다. 당일은 솔직히 너무 힘들꺼 같고 다음날 정도?

 

A 

 

수열이 존재하고 그 수열의 모든 부분수열의 합이 갯수로 나누어 떨어지게끔 그 수열을 만드는 문제이다.

이제까지 느낀 코포 A의 전형적인 문제 문제를 위한 문제라고 표현할 수 있지 않을까 가장 쉬운 방법을 생각하는 것이다. 

 

만약에 서로 다른 수들로 이루어졌다고 한다면 계산이 너무 복잡해진다. 이 복잡함에 대해서 불편함을 느낄때 문제의 조건을 다시 바라보면 서로 다른 수들로 이루어졌다는 조건이 주어지지 않았다. 따라서 모두 같은 수들로 만들어버리면?

 

임의의 n개로 이루어진 부분수열은 모두 동일할 것이고, 그 수들의 합/ 그 수들의 갯수는 당연하게도 나누어 떨어진다. 

 

3분솔

 

B

 

B를 풀면서 실력이 늘었다는걸 느꼈다 코포 실력은 아니고 그냥 앞으로는 투포인터 알고리즘을 쓸 수도 있겠는데라는 생각?

 

l1<=r1 < l2 <= r2 를 만족하고, 이 l1, r1사이의 수열 합과 l2 r2 사이의 수열 합이 같아지는 경우가 존재하는지 여부를 묻는 문제였다. 

 

처음에는 1에서 무조건 시작, 마지막에서 무조건 시작인줄 알고 투포인터를 생각했었다. 하지만 이렇게 계산을 하게되면 bool check[]가 10^9승개가 필요하다고 생각을 했고, 메모리 초과때문에 계속해서 안되겠다는 생각을 했다. 하지만 10^7이었으면 1에서 시작 마지막에서 시작인 경우에도 풀 수 있지 않을까 생각한다. 

 

최고차항만 기억하고, 더 작은 쪽에서 뽑고, 그게 큰쪽에 있으면 지우고 그런식으로 하면 가능할 것 같다.

 

그러던 중 언레선언 공지 .. 

여유가 생겨서인지 풀이가 떠올랐다.

 

보니깐 무조건 l1이 1에서 출발이 아니었고, l1과 r1은 같을 수도 있었다 따라서 그냥 같은게 존재하냐 라는 문제랑 동일한 문제였다. 

 

그래서 코드를 짰지만 계속해서 pretest2에서 걸렸다. 

 

보니깐 입력도중에 정답을 출력하는 답안으로 짜서 그랬던것 같다. 15분 고민끝에 이 오류를 발견하고, 45분솔

 

그리고 내일 일찍 일어나야되서 바로 운좋다 생각하고 잤다. 

 

 

-------------------------------------------------------------------

C

 

이거는 튜토리얼을 확인하였다. 

처음에 모두 같은 경우에 답안과 같이 대각방향만 처리하면 된다고 생각을 했지만, 그러면 다른 경우에는 ? 이 경우에 대해서 홀짝을 생각하지 못하였다. 그래서 빠르게 튜토리얼을 확인하였고 그냥 홀짝으로 구분지어서 생각하면 되는 문제였다. 

 

참 문제가 깔끔하다고 느꼈던게 

 

바꿔야 하는 최소갯수라고 하였을때는 완전히 다른문제가 된다. 만약에 내가 이 풀이를 모른다면 이 두문제는 같은 문제라고 생각할 수도 있었을 거라고 생각한다. 

 

간단한게 존재한다. 딱 맞는게 존재하고, 그 이상은 사치일 때가 있다는 걸 많이 느낀다.