Educational 99 div2 11/30

codeforces.com/contest/1455

Dashboard - Educational Codeforces Round 99 (Rated for Div. 2) - Codeforces

처음으로 4솔을 해봤다. 

운동도 쉬고, 컨디션도 좋게 만들어놓고 코포를 기다렸는데 그래서 그런지 A부터 집중이 잘 되었다. 

 

A 

 

수를 받고, 뒤집고, 처음에 있는 0들을 제거 한 함수를 f(x)라고 한다

 

어떤 범위 안에 값에서 x/f(f(x)) 값의 갯수를 구하는 문제인데, 대충 보니깐 자릿수랑 상관이 있었다. 

그래서 그냥 예시에 나온거 세보니깐 자릿수 맞는것 같아서 제출 

 

4분 솔브

 

 

B

 

아무리 생각해도 div2B인데 분명 쉬울텐데 왜 bfs로 풀 수 있는 문제가 나올까 했다. 짤수는 있겠지만 시간초과 날 것같고, 의도한게 이것이 아닌것 같아서 5분정도 고민하다가 C로 넘겼다.

 

C

 

여기에서 시간을 진짜 많이 잡아먹었는데 

게임이론 문제인것같다. 탁구를 하는데 이기는 횟수가 최대가 되게끔 하는 문제이다. 

근데 문제를 잘못 읽어서 서브한거는 무조건 받아야 한다고 생각을 했다. 

 

서브한거를 받아야 하면 케이스분류가 상당히 까다로워서 일일히 케이스 분류하고 이제 코드를 돌려보는데 예시에서 틀리길래 .. 보니깐 서브를 꼭 받을 필요가 없는 문제였다. 

 

그 와중에 알림도 이기는 횟수 최대로 만드는게 우선이라고 하길래 그것대로 생각하니깐 엄청 간단한 문제였다. 

 

46분 솔브

 

B

 

다시 돌아와서 이건 무조건 쉽다라고 최면을 거니깐 걸렸다. 그냥 10까지 해보니깐 그냥 무조건 x == n(n+1)/2-1

인 경우를 제외하고는 

 

1 2 3 4 

에서 

10, 8, 7, 6, 5 를 만들수 있었다. 

 

그런데 6은 

1, 2, 3으로 만드는게 더 최선이니깐 패스하고 

 

암튼 이렇게 하니깐 되길래 코드 짜고 

 

1시간 1분 솔브

 

D

 

처음에 하나를 갖고 시작을 하고, 그걸 이미 있는 수열과 바꿔치기 하면서 정렬을 시키는데 최소 횟수를 구하는 문제이다. 그래서 생각을 해보니깐 index 오름차순으로 방문하면서 만약 내가 갖고 있는 것보다 수열에 있는 값이 더 크면 무조건 바꾸는 방법으로 구현을 하면 되지 않을까 생각을 하고 짜보았다. 

 

만약에 무조건 바꾸지 않으면 만약 처음에 안 바꾸고 다음에 바꾸면 무조건 정렬이 되지 않는다. 그래서 그냥 최소횟수 정렬을 위해서라면 이 방법밖에는 없다고 생각을 하였지만 WA

 

반례를 생각해보았는데 생각보다 단순했다. 그냥 처음부터 바꿀 필요가 없는 경우에도 무조건 바꾸게끔 해서 WA가 나왔었고, 이걸 수정했지만 단 한번만 조사를 해서 다시 WA

 

그냥 N번 돌때마다 조사하면 되겠다 싶어서 그렇게 코드를 다시 바꾸고 

 

1시간 29분 솔브

 

E

 

처음으로 E번을 시간내에 풀생각을 해보았는데 뭐 좌표를 갖고 무언가를 해야하는 것 같았다. 왜냐 좌표에 관한 문제이기 때문에 그래서 사각형의 중심, 길이를 생각해보았는데 아무리 생각을 해보아도 뭐 어떻게 해야할지 네 점을 그려보고 내가 직접 눈으로 보아도 어떤 사고를 통해서 내가 최소이동거리를 구하는지도 잘 모르겠어서 그냥 멍하니 있었다. 

 

그렇게 마무리 .. 

 

끝나고 풀이를 들었는데 너무 어려워서 일단 삼분탐색문제를 한문제 풀어볼 생각이다. 

 

금요일에도 또 열리니깐 그때도 운동안하고 컨디션 좋게 준비해야겠다.