#684 div2 11/17

codeforces.com/contest/1440

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

 

직전에 바로 운동을 하고 피곤해서 던질까 했는데 뭔가 핑계인것 같아서 그냥 참가하였다

 

A 

 

1과 0으로만 이루어진 수열에서 1을 구매하는데 비용 c1, 0을 구매하는데 비용 c0

1->0 0->1로 바꾸는데 드는 비용 h가 있다고 할때 

 

수열을 구매하는데 드는 최소비용을 구하는 문제이다

 

최소비용으로 구매하려면 바꾸고 구매하는 비용이 원래꺼를 구매하는 것보다 합리적일때 바꾸면 된다. 

근데 두가지 케이스만 존재하니깐 간단히 케이스로 나눠서 계산 가능하다. 

 

9분솔브

 

B

 

n개로 이루어진 수열이고, 그 n/2의 rounding up의 자릿수의 합들이 최대가 되는 값을 구하는 문제

규칙 찾는거는 예시보면 엄청 쉽게 찾을 수 있었지만 주기를 통해서 원하는 대로 만드는게 index랑 갯수랑 섞이다 보니깐 구현이 꽤 까다로워서 오래걸렸다. 

 

단순히 주기를 잘 찾고 최초에 어디서부터 더하는건지를 찾으면 된다.

 

44분 솔브

 

C1

 

n*m개의 1,0으로 이루어진 수들이 있고,

이 수들은 2*2의 정사각형 안에 있는 것중 세개를 반전시킴으로만 변경할 수 있다. 

모두 0으로 만드는 문제

 

3*n*m에 집중을 하였다 

총 n*m개의 수들이 존재한다. 그래서 3은 어디서 나올까 생각했다.

 

그냥 하나를 바꾸는데 최대비용은 3개이다. 이 경우에는 나머지는 바뀌지 않고 그것만 변하게 하는 비용이다. 

따라서 그냥 구현을 좀 하면 된다.

 

1:08분 솔브

 

C2

 

시간적 여유가 있어서 

C1에서 어떤 걸 변경하면 될까 생각하였다.

n*m이므로 그냥 하나당 한번이면 변경할 수 있을까에 대해서 생각을 하다가

2*2의 네모가 자꾸 날 꼬셨다 계속해서 2*2의 네모로 계속 채운뒤에 만약 홀수일 경우 가장자리를 따로 케이스분류해서 

계산한다고 생각을 하였다

 

구현을 하려는데 절대로 쉬운 구현은 아니었고, 잘하는 사람들은 절대 이렇게 안 할거라는 생각, 문제의도 또한 이것이 아닐 것 같았다. 

 

그래서 D를 슬쩍 봤는데 clique? 구글링해보니깐 뭐라는지 모르겠어서 그냥 다시 C2로 넘어와서 딴짓을 하면서 생각을 했던 것 같다. 

 

곰곰히 생각을 하다가 든 생각인데

 

2*2로 계속 처리하다가 만약에 가장자리가 남을 경우에 앞선 2*2들이 모두 1로 채워져 있으면 그 갯수만큼의 연산이 필요하니깐 가장자리가 연속 두개가 아닌 하나 띄워서 하나 이런식으로 되어 있게된다면 세번의 연산이 필요하니깐 뭔가 불가능할 것 같은 기분이 많이 들었다. 

 

그렇게 그냥 계속 멍하니 있다가 중얼거리다가 반복해서 10분정도 남았을 때 

 

하나씩 ㄱ으로 계속 처리를 하면 맨 마지막줄 하나 냅두고 가능하다는 것을 알았다. 

 

그래서 맨 마지막줄에 ㅣㅡ 이런식으로 처리할 생각을 했는데 그러면 또 그전에 변화를 뭉개니깐 더 좋은 방법이 있지 않을까 생각만 하고...

 

종료 후 물어보니깐 학회 Green55님이 케이스 분류를 기가막히게 하셨다.. 

 

n-2까지만 ㄱ으로 처리,(m-1에서는 ㅢ)

m-2까지 ㄴ,ㅢ, ㄱ으로 처리  

 

마지막 2*2 정사각형 처리 

 

시간이 없어서 생각을 멈췄을지도 모르겠지만 뭐가 중요한지 뭘 한건지 뭘 하고 싶은건지에 대해서 잘 생각해보자 

그러면 지난 것은 상관안하면서, 지금꺼에 영향을 주는 방법을 찾으면서 아마 케이스 2,3을 찾기 좀 수월했을지도 모른다. 

 

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

 

아쉬움이 많이 남는 라운드였다

 

멍청하게 문제를 제대로 안 읽고 index의 최대범위를 틀려서 RTE가 두번이나 떴고, 

sum*3인데 sum을해서 pretest1에서 틀리고.. 

 

코드포스 레이팅은 등수랑 직접적인 연관이 있는 것 같다. 대충 보니깐 내가 맞춘 문제들 사이에 사람뎁스가 엄청나고 그래서 더 실수하면 안되는 실력인 것 같다. 

 

봄색을 찾았으니 여름색으로 빨리 갈수 있으면 한다.