Codeforces Round #830 (Div. 2)

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

서론

조졌다.

 

A - Bestie

이것이 정말 A번이 맞는가.

감이 안 와서 B번으로 넘어갔다가 다시 A번으로 돌아왔다.

2년 전의 나라면 도망갔을텐데 레이팅에 목숨 걸지 말고 열심히 풀어보기로 하였다.

 

각 인덱스별로 한 번씩만 검사하는 풀이를 짰는데 예제가 안 나왔다.

연산이 2회 이상 필요한 경우도 있었다.

또 다시 B번으로 넘어갔다가 다시 A번으로 돌아왔다.

최대 연산 횟수는 2회이며 이를 마지막 인덱스에서 수행 시 비용은 3 이하가 됨을 깨달았다.

00:22 AC

조졌다.

 

B - Ugu

B번 역시 A번과 마찬가지로 감이 잘 오지 않았다.

N이 작은 경우에 대하여 일일이 계산해보니 규칙을 찾을 수 있었다.

00:35 WA

코너 케이스를 처리해주었다.

00:36 AC

 

지금 다시 보니 B번이 크게 어려운 문제가 아니었다.

대회 중에 B번을 조진 이유를 생각해보았다.

다음 세 가지 이유 중 하나일 것이다.

첫 번째는 15분 전에 이미 2시간 대회를 뛰고 와서 두뇌 컨디션이 좋지 않았다는 것이다.

이러한 이유라면 5시간 ICPC는 가망이 없다.

두 번째는 A번에서 받은 멘탈 충격에서 벗어나지 못하였다는 것이다.

이러한 이유라면 대회에 많이 참가함으로써 멘탈 수련을 하여 극복할 수 있을 것이다.

세 번째는 PS 하기에는 이미 두뇌가 굳어버렸다는 것이다.

이러한 이유라면 이번 생에는 답이 없다.

 

D1 - Balance (Easy version)

C번도 도저히 감이 안 와서 C번과 D번을 들락날락 하고 있었다.

문득 캐싱이라는 아이디어가 떠올랐다.

01:15 AC

이후 아무 문제도 풀지 못하고 대회가 끝나버렸다.

 

C1 - Sheikh (Easy version) (not solved)

f(l, r + 1)이 f(l, r)보다 작아질 수 없음을 알면 쉽게 풀 수 있는 문제였다.

놀랍게도 1시간 넘도록 이를 눈치채지 못하였다.

따라서 f(1, N)은 항상 최댓값이고 구간의 길이만 최소로 줄이면 된다.

이는 투 포인터 또는 이분 탐색으로 해결할 수 있다.

 

C2 - Sheikh (Hard version) (not solved)

모든 원소가 0이 아니라고 가정하면 l과 r의 범위를 다음과 같이 줄일 수 있다.

L <= l <= L + 30

R - 30 <= r <= R

이 범위를 벗어나면 분명히 겹치는 비트가 존재하여 더 이상 값이 최대가 아니게 된다.

0에 대하여 적절한 처리가 필요하다.

 

D2 - Balance (Hard version) (not solved)

캐싱과 동시에 특정 원소 x가 어떠한 K에서 사용되었는지도 기록한다.

x가 제거되면 x를 사용한 모든 K에 대하여 x가 제거되었음을 알려준다.

x가 다시 추가되면 x를 사용한 모든 K에 대하여 x가 다시 추가되었음을 알려준다.

 

놀라운 사실은 특정 원소 x에 대하여 x를 사용한 K의 개수는 매우 적다는 것이다.

x가 K에서 사용되려면 K는 x의 약수여야 한다.

또한 x 미만인 모든 K의 배수가 적어도 한 번 이상 추가되었어야만 한다.

이러한 K의 개수는 엄밀히 증명하지 않아도 매우 적음을 알 수 있다.

 

E - Location (not solved)

Pass

 

끝

끝