오늘의 PS (24) - 221015

하루에 대회 3개를 쳤기 때문에 묶어서 정리하려고 한다.

 

BOJ - 초콜릿컵

A. 초콜릿 피라미드 (0:12, +)

차분히 식정리를 해주면 된다. 

 

B. 초콜릿과 나이트 게임 (0:32, +)

\(XY=0\)인 경우, \(X=Y\)인 경우, 그 외의 경우로 나뉜다. 앞 두 케이스는 7번, 뒤 케이스는 15번만에 게임을 끝낼 수 있다. 구현이 좀 귀찮은데, 난 그냥 cout을 29개 썼다.

 

C. 예쁜 초콜릿과 숫자놀이 (1:51, +3)

제한이 애매하게 커서 완탐도 안될 것 같고(사실 된다), \(O(N^2 MOD)\) DP는 생각이 나지 않아 그냥 \(O(N^3 MOD)\) DP에 비트셋을 박았다. 왠지는 모르겠지만 실행시간 1등이다. 비트셋 최고

 

D. 초콜릿 나눠 팔기 (2:09, +)

케이스를 나누면 어렵지 않게 해결할 수 있다. 케이스의 수가 상당히 적어지고, 제한도 작아서 어렵지 않게 해결할 수 있었다.

 

E는 빡구현, F는 옆에서 qjatn0120 선배가 맞왜틀하길래 컨디션 안배를 위해 여기까지만 풀었다.

 

AtCoder Beginner Contest 273

A. A Recursive Function (0:00, +) *11

팩토리얼을 짜면 된다.

 

B. Broken Rounding (0:03, +) *178

하라는대로 구현하면 된다.

 

C. (K+1)-th Largest Number (0:7, +1) *370

정렬해준 후 큰 것 부터 같은 수들 개수를 세주면 된다.

 

D. LRUD Instructions (0:17, +) *1119

x좌표, y좌표별로 장애물을 저장해준 후 이분탐색을 잘 써주면 된다.

 

E. Notebook (0:44, +) *1624

잘 생각하면, 각 수별로 그 수를 제거했을 때 다음에 오는 수는 정해져 있다. 따라서 DAG처럼 수들을 나타내줄 수 있으며, 이를 잘 구현하면 AC를 받을 수 있다.

 

F는 대충 알겠는데 구체화가 어려워서 풀지 못했다. 사실 그냥 놔둬도 옐로 갈 것 같아서 대충 쳤는데, 1998점에서 멈췄다. 그 덕에 다음날 ARC를 쳐야 했다.

 

 

Codeforces Global Round 23

A. Maxima (0:02, +) 

1이 있으면 YES이다.

 

B. Rebellion (0:11, +)

앞에 있는 1부터 뒤에 있는 0으로 잘 옮겨주면 된다.

 

C. Permutation Operations (0:17, +) 

\(i\)가 있는 위치에 \(N+1-i\)를 써 주면 항상 inverse를 0개로 만들 수 있다.

 

D. Paths on the Tree (0:55, +1)

루트에서 내려가면서 리프 노드들을 그리디하게 선택해줘야 하는데, 이게 좀 어렵다. 대충 해당 서브트리에서 루트 노드가 \(x\)번 호출되어야 한다면 각 자식에서 \(\lfloor \frac{x}{c} \rfloor\)번 호출한 후, 큰 리프노드를 \(x mod c\) 개 쓴 후 그 다음으로 큰 것을 위로 올려주는 식으로 구현하면 된다.

 

E는 핵심 아이디어는 빨리 찾았지만, 마무리 부분을 1시간동안 떠올리지 못해 풀지 못했다. 풀었으면 레드 퍼포라 좀 아쉽긴 했지만, 최근 있던 Div. 1에서 계속 양수 레이팅을 받아 개인 최고 레이팅인 2197까지 올릴 수 있었다.