Codeforces Round #719 (Div. 3) (virtual)

2021.10.10

조져쓰...

D번에서 index설정때문에 너무 많이 틀려서 시간을 다 잡아먹었다...

A

Problem - A - Codeforces

숙제를 한 순서에 대한 string이 입력으로 들어오는데 한 숙제를 시작했으면 한숙제가 끝나고 다른 숙제를 잡으라고 선생님이 시켰는데 선생님의 말씀대로 하였는지 안하였는지 묻는 문제였다.

숙제는 alphabet으로 이름이 정해져있으므로 26개의 배열을 미리 만들어 해당 배열이 이미 이전에 나왔는지 확인하고 나왔으면 바로 직전에 나온건지만 확인해주고 직전에 안나왔으면 말씀대로 안한거고 나왔으면 말씀대로 한거로 체크하고 나머지를 전부 진행해 주면 되는 문제였다.

B

Problem - B - Codeforces

특정 수 n이하의 모든 ordinary 라는 수를 찾는 문제였다.

ordinary는 모든 자리수가 같은 수를 의미한다.

걍 한자리 올라갈때마다 9개가 추가되므로 9 * (전체자리수 - 1) + 이번 자리 수에서의 개수를 구해주면 된다.

C

Problem - C - Codeforces

행렬을 재구성하는데 특정 요소 양 옆, 위, 아래가 해당 수와 1차이가 나선 안되게 배치를 해야하는 문제였다.

일단 2x2인 경우를 제외하곤 모두 다 가능하다.

가능한 경우에는 홀수와 짝수를 나눠 홀수 먼저 배치하고 짝수를 배치하면 된다.

그 외에도 여러 풀이가 있을수 있을것 같으나 이게 제일 쉬운것 같음

D

Problem - C - Codeforces

특정 배열 내에서 $a[j] - a[i] = j - i$ 인 쌍의 개수를 구하는 문제다.

처음에는 어케하징 했는데 잘 생각해보니 $a[i] - a[0] - i = k$일때 같은 $k$인 수들은 전부다 쌍으로 묶일 수 있다. 그래서 갯수를 세서 $nC_2$를 해주면 되는 문제였다.

근데 음수도 나올 수 있고 해서 인덱스 문제가 좀 나에게는 복잡했던 문제였다. 5번이나 인덱스 때문에 틀려서 시간을 다 잡아먹었다..

E

Problem - E - Codeforces

양들의 위치들이 한 배열 위에 주어지는데 이 양들을 전부 붙이는데 필요한 cost의 최솟값을 구하는 문제였다.

모든 양을 중심으로 하여 비용을 계산하여 비교를 할떄 계산하는 시간을 이전 데이터에서 빠르게 얻어올수있게 하면되는 문제였다.

최종 비용 = left에서 오는 비용 + right에서 오는 비용

위와같이 결정이되는데 이번에 left에서 오는 비용은 바로 직전에 계산한 양을 중심으로 할때 left에서 오는 비용 + 그렇게 해서 뭉친 양들이 전부다 이번양 옆으로 오는 비용으로 계산 가능하다.

right또한 비슷하게 직전 양의 right에서 오는 비용에서 이번에는 뭉친양들이 굳이 직전양까지 안가도 되니까 가는 비용을 빼주면 된다. 그림으로 설명 가능하지만 귀찮으므로 패스..

F1

Problem - F1 - Codeforces

이 문제까지는 그래도 풀어줬어야 했는데 정말 아쉽다.

처음 만난 Interactive 문제이라서 또 Interactive 문제가 뭔지 몰라서 이해하느라 시간을 잡아먹었다..

0과 1로 이루어진 특정 배열이 시스템 내부적으로 정해지고 k가 주어진다.

이때 나는 특정 구간의 합을 질문할 수 있는 기회가 20회 주어진다.

이때 k번째 0의 인덱스를 구하는 문제다.

이해하자마자 binary search를 구현하려했으나 시간이 없어 실패..