2023 IOI 멘토교육 3주차

ROI18에서 4문제 뽑아서 5시간동안 돌았다.

1. Decryption 2. Quick sort 3. Quantum teleportation 4. Addition without carry

0:00 ~ 0:14

1번 읽고 바로 짜서 맞았다.

0:14 ~ 1:52

234번을 읽고 3번을 고민했다. 대충 다익스트라를 이용한 세제곱/64 풀이랑 제곱로그/64 풀이를 냈다. 일단 나이브인 세제곱/64를 짜고 디버깅을 했더니 67점이 긁혔다. 제곱로그/64를 짜고 100점을 받을까 생각해봤지만 x좌표나 y좌표 같은 점이 있으면 안 되는 풀이라는걸 깨닫고 그냥 넘어갔다.

1:52 ~ 2:07

4번은 섭태가 너무 많아서 일단 2번 버블소트로 50점을 긁었다.

2:07 ~ 2:54

2번을 좀 더 고민하니 대충 로그복잡도 풀이가 나왔고 80점을 받았다.

2:54 ~ 3:18

4번은 잘 모르겠어서 대충 maxL이 매우 작을 때 정수로 바꾸고 다 시도해보는 방식으로 점수를 긁었다. 14점을 받았다.

3:18 ~ 4:15

정수일 때 체크하는 방식을 그대로 bigint로 구현하면 대충 네제곱/64 정도의 풀이가 나왔다. 그걸 구현해서 300정도까지 점수를 긁었고 50점을 받았다. 이때 시간을 왜 한 시간이나 쓴건지는 잘 모르겠다.

4:15 ~ 4:24

297점이길래 긁을만한 4점 섭태가 없는지 찾아봤고 모든 값이 2의 거듭제곱인 1000짜리 섭태가 있길래 따로 예외처리해서 긁었다.

4:24 ~ 5:00

딱히 더 긁을만한게 없기도 했고 풀이 떠오르는 것도 없어서 점수를 더 받지는 못했다.