CodeTON Round 5 (Div. 1+2)

6월 24일에 진행한 코드포스 코드톤 대회 일지입니다. 3번째로 퍼플에 왔습니다. 다음에는 퍼플을 유지할 수 있을까요?

0:00~0:03

• A번을 잡았습니다.
• 스택을 사용해서 문제에 있는 것을 그대로 시뮬레이션하면 되는 문제였습니다.

  발상에 1분, 구현에 2분을 사용했습니다.

0:03~0:07

• B번을 잡았습니다.
• bitwise or 연산은 순서가 상관없기 때문에 그냥 되는 숫자를 다 때렸을 때 나오는 숫자가 주어지는 숫자와 같은지 확인하면 됩니다.

  발상에 1분, 구현에 3분을 사용했습니다.

0:07~0:25

• C번을 잡았습니다.
• 문제가 DP라는 것을 4분 정도 후에 알았고, 3분 정도 구현했습니다. 틀렸습니다.
• 같은 수가 여러 개 있을 때 예외처리가 더 개선되어야 한다는 것을 찾았고, 이를 개선하는 아이디어를 찾는 데 8분 정도를 사용했습니다.
• 분명 이런 예외처리를 접해본 적이 한번쯤 있었던 것 같습니다. 그런 것치고는 살짝 오래 걸린 것 같아 아쉽습니다.
• 컴프 수업의 심화 문제로 어울릴 것 같습니다쌤은 좋아하실 것 같은 문제입니다

  발상에 4분, 구현에 3분, 디버깅에 10분(아이디어 8, 구현 2) 정도를 사용했습니다.

0:25~1:11

• D번을 잡았습니다.
• 재미있는 아이디어 문제였습니다. 게임을 계획할 수 있는 uniform한 방법을 찾는 문제였습니다.
• 각 동물을 정점으로 하는 weighted graph를 만들 때, n번 동물까지의 최단거리가 그 동물이 참여할 수 있는 게임의 수입니다.
• 1번 동물이 모든 게임에 참여해야 한다는 점을 사용하면, 위가 성립하도록 각 동물을 잘 배정할 수 있습니다.
• 여기까지의 발상에 20분을 사용했고, 구현하는 데는 10분 정도를 사용했습니다.
• 이때, 같은 동물들이 참여하는 경우가 여러 개 생기지 않도록 해서 서로 다른 게임의 수를 최소화해야 합니다. (하지 않으면 게임의 수가 많아져 TLE가 뜰 수 있습니다)
• 이를 알아내는 데에 5분, 구현하는 데 10분 정도를 더 사용했습니다.
• 문제의 퀄리티가 매우 높다고 생각하는 문제 중 하나였습니다. 마음에 들었습니다. (근데 생각해보면 그래프 문제라는 것을 매우 당연하긴 합니다)

  발상에 20분, 구현에 10분, 디버그에 15분(아이디어 5, 구현 10)을 사용헀습니다.

1:11~1:40

• E번을 잡았습니다. 참고로 못 풀었습니다.
• 기하가 살짝 묻기는 했지만 어쩄든 구간 처리 비슷한 문제였습니다. 구간을 그리디하게 고르는 방법을 제시하는 문제로 보였습니다.
• 구간 처리라는 점에서 세그 생각도 했고, 구간 그래프를 그리는 생각도 했습니다.
• 방법을 찾지 못했습니다.
• 참고로, 세그가 맞다고 하네요.

1:40~2:00

• F와 G를 구경했습니다.
• F는 트리+그리디 문제였습니다. 어려워 보였습니다.
• G는 조합론 수학문제였습니다. 역시 어려워 보였습니다.

2:00~

• 숙면을 취했습니다.

후기

CodeTON 문제들은 확실히 퀄리티가 좋은 것 같습니다. 솔브수 분포도 적당하게 나왔고, 최소한 앞의 네 개 문제들은 확실히 재미도 있었습니다. 특히 D번 문제는 좋은 문제라고 생각합니다.
E번 문제가 세그라고 하니, 시험이 끝나면 정올 2차 전에 업솔빙을 해 보아야겠습니다.
퍼플에 세 번쨰로 달성했습니다. 이번에는 얼마나 오래 퍼플을 유지할 수 있을지 싶습니다.