[CF] Educational Codeforces Round 131

https://codeforces.com/contest/1701

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

A. Grass Field (00:05)

\( 2*2 \) 의 4칸 중
4칸에 모두 잔디 있으면, 답은 2
0칸에 잔이 있으면, 답은 0
나머지는, 답은 1

처음 제출시에 오타나서 한번 틀렸었다. 일주일만에 하는거라 조금 떨렸었나보다. 다음부터는 침착하게 해보자.

 

구현할 때에 직접적으로 \( 2*2 \)배열을 만들어서 했는데, 그럴 필요없이 그냥 잔디 있는 칸의 수를 세기만 하면 된다.

B. Permutation (00:19)

순열 p의 비용이 최대가 되게하는 d와 그 순열을 찾는 문제이다.
\( d = 2 \)여야 비용이 최소임을 쉽게 알 수 있다.

처음 제출 시에는 순열을 \( 2^i \) 인 것들만 고려해 만들어서 틀렸는데, 다시 생각해보니 남은 것들도 \( p[i]*d=p[i+1] \)을 성립하게 만들어 주어 비용을 더 크게 만들어 줄 수 있다는 것을 알게 되었다. 처음부터 이 생각을 했었어야 하는데, 머리보다 손으로 코드 쓰는거에 급급해서 그랬던 것 같다.

따라서, 만약 \( n=18 \) 이라면, 1 2 4 8 16 3 6 12 5 10 7 14 9 18 11 13 15 17 로 비용이 최대가 되는 순열을 만들 수 있다.

C. Schedule Management (upsolved)

라이브 참여 후 있었던 코드포스 스터디에서 dong_gas 형의 설명을 듣고 업솔빙했었다.

나는 처음에 시간을 차근차근 늘리면서, 일하는 사람들을 일에 매칭시키는 식으로 풀려했었는데, 역시 어떤 식으로 매칭시킬지 명확한 기준이 없어서인지 못풀었다.

문제를 보고 t시간 안에 일을 할 수 있다면, t보다 크거나 같은 시간 안에는 무조건 일을 할 수 있다라는 것을 파악 한 후, 파라메트릭 서치를 이용해 해결 할 수 있다는 것을 떠올릴 수 있었어야 했다.

 

또 t시간 안에 일을 할 수 있는지 여부를 구현할 때에, 순차적으로 생각하려는 편견을 깨고, 한꺼번에 생각해야 한다. t초동안  각자 능숙한 일을 한다고 생각하고, 남는 시간, 남는 일을 조사해서 비교해주면 된다. 이때 남은 시간을 남은 일에 사용할 때에 능숙하지 않음을 반영해서 구현해야 한다.