#688 div2 12/04

codeforces.com/contest/1453

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

 

 

 

A

 

1초에 1씩 움직이고, 축에서 동시에 출발할때, 부딪히는 기차의 갯수를 구하는 문제이다. 

문제가 진짜 길어서 문제 읽는데에 오래걸렸는데, 그림보고 예시 보니깐 축에서의 값이 같을때 부딪치는 기차가 된다

 

5분 솔브

 

B

 

이것도 문제가 이해하기 살짝 어려웠다. suffix라는 단어를 일단 검색해보았고, 예시로 이해를 했다

어떤 인덱스를 선택, 그 인덱스부터 뒤에를 1 더하거나 1 빼는 연산을 하여서, 최소연산으로 모든 원소를 같게 만드는 문제이다. 

 

아 그런데 그냥 연산을 하는 문제가 아니라 내가 일단 어떤 원소를 같은 배열에 있는 원소의 값으로 바꿀 수 있다. 

 

그 뒤에 길동이가 연산을 하는 건데 길동이가 연산을 어떤식으로 해야되는지 계산을 해보니깐 그냥 앞뒤차를 계속해서 더하면 되는 문제였다. 

 

그래서 이제 어떻게 바꿔야 할지를 생각을 했다. 그 길동이가 연산하는 방법에 맞춰서 어떻게 바꿔야 할지를 생각했다. 그냥 연산을 최대한 적게하려면

 

원래 하던 연산 -> 바꾼 뒤 연산의 값의 차가 가장 큰 곳에서 바꾸면 되었는데 여기서 문제가 발생.. 

 

분명 여기까지 했을때가 20분정도 였었는데 구현을 시작하고 계속해서 case work에 시간을 쏟았다. 그냥 case work 한번 시작하면 진짜 계속해서 하게되는것 같다. 거의 간장게장급

 

아니 진짜 너무 안풀리길래 내가 하고있는 행동을 생각해보았는데, 문제의 핵심인 원래 하던 연산 -> 바꾼 뒤 연산의 값의 차가 가장 큰 이 아니라 단순하게 앞과 뒤에 차를 구해서 내가 원하려던 문제가 아닌 다른 이상한 문제로 바꾸어서 구현하고 있었다. 

 

달관의 자세로 다시 접근하니깐 내가 뭘하는지, 그리고 뭘 구해야 하는지가 눈에 잘 들어왔고 아마도 이걸 한 뒤에 구현은 어렵지 않았던 것 같다. 

 

2시간 솔브

 

걍 이거 하고 진짜 진이 쫙 빠져서 15분 쉬다가 바로 잤다. 

대회가 2시간짜리였으면 1솔브였을듯한 시간이었다.

 

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

 

그래도 문제들이 다 내가 좋아하는 퀴즈형식(알고리즘 사용안하는)에 한국인 세터가 낸 문제였기 때문에, C,D를 업솔빙 해보았는데, 

 

아마 한 5시?부터 C를 풀었다.

 

C는 삼각형을 0~9 각각의 꼭짓점으로만 이루어진 삼각형 넓이의 최댓값을 구하는 문제로, 그 넓이를 출력한다.

단 여기서, 나머지 하나의 꼭짓점은 임의로 지정할 수 있다. 

 

왜 이렇게 오래걸렸는지 설명을 하자면 풀이는 금방 떠올랐다. 

 

그냥 각각의 최소x, 최소y, 최대 x, 최대 y를 구하고, 그걸 이용해서 삼각형을 만든다고 생각을 하였는데, 문제가 있었다. 

• At least one side of the triangle is parallel to one of the sides of the board. You may assume that a side of length 00 is parallel to both sides of the board.

이게 있는지 몰랐다. 그래서 각각의 최소 최대 x,y만을 구하는 걸로는 삼각형의 최댓값을 구하지 못한다는걸 찾아내고, 도대체 사람들은 머리가 얼마나 좋으면 이 풀이를 10분 20분만에 생각해낼까.. 이런 좌절감에 빠져서 좌표가 주어졌을때 삼각형 넓이공식을 찾아보며 점 여러개에 대해서 생각해보았다. 

 

그렇지만 아무리 생각해보아도, (N^2)^2 N^4의 풀이만 떠올랐고, 불가능했다. 도대체 어떻게 할까 2시간넘게 고민하다가 다른 사람의 풀이를 참고하면서 저게 있다는 걸 깨달았다. 

 

그래서 그냥 구현.. 

 

영어 왤케 못하지 

 

D는 쉬웠다. 

 

사실 기댓값에 대한 접근을 어떻게 할지 잘 감은 안왔지만 그냥 확률 * 횟수가 1이되도록 만드는것 같아서 그냥 그대로 구현했다. 

 

사실 아직도 홀수일때 -1이 되는 정확한 이유는 모른다. 아마도 기댓값이 정확히 1이 되어야 하는것같다. 

 

내일은 글로벌라운드? 3시간짜리인데 홧팅하자