[3일차] Codeforces Round #645 (Div. 2)

오늘의 결과.

 

A (-, 00:02)

그리디하게 생각하면, 모든 칸을 2칸씩 최대한 끼워넣으면 격자 수가 홀수인 경우 뺴고 가능하다. 

홀수일땐 마지막 한 칸에 더 놓아주면 된다

그렇게 한다면 횟수는 [(n*m+1)/2]이다.

이는 쿼리당 O(1)만에 구할 수 있다.

코드

 

B (-, 00:06)

정렬을 하고 보면, 1~N번째에 있는 할머니들이 올 수 있는 조건은 a_N<=N이다.

이걸 이용해서 답을 구해주면 정렬 O(n log n), 확인 O(n)으로 O(n log n)에 문제를 풀 수 있다.

코드

 

C (-, 00:14)

합의 가능한 경로의 수는 (합의 최대)-(합의 최소)임을 알 수 있다.

이때 최소인 경로와 최대인 경로에 있는 칸들을 각각 같은 대각선에 있는 칸들끼리 차이를 구해서 모두 더했을 때, 이가 최소경로를 세지 않은 답이 되는데, 이는 그림을 좀 그려서 관찰해본 결과, (x2-x1)*(y2-y1)이었다. 

그렇다면 최소경로까지 세서 답은 (x2-x1)*(y2-y1)+1이다.

이는 쿼리당 O(1)만에 문제를 풀 수 있다

코드

 

D  (-, 00:53)

언제가 최적해인지는 명확하게 알 수 없기에 어떤 달을 만나는 마지막으로 고정시키고 그걸 모든 날에 대해 돌리면 되겠다.

이때 만나는 달은 prefix sum+이분탐색으로 구할 수 있고, 날짜의 합은 (1~d_i까지의 합)의 prefix-sum을 이용해서 답을 구할 수 있다.

이는 모든 날에 대한 탐색, prefix sum 전처리를 O(n), 이분탐색 O(log n)으로 총 O(n log n)으로 풀 수 있다.

코드

 

E는 3틀하고 끝났다... 업솔빙하면 블로그에 올릴 예정.

하고 나서.

C를 진짜 빨리 푼 게 엄청난 효과가 있었다.

E를 N분 놓치고 못푼 게 아쉬웠지만, 정말 만족하는 성과이다.

오늘 밤 코포가 있는데, 이때도 지금과 같이 뇌절하지 않고 빠르게 풀 수 있기를...