2023 IOI 멘토교육 2주차

USACO 23 us open 골드 123번 / 플래 13번으로 구성된 5문제 셋을 5시간 동안 돌았다. 문제 번호는 순서대로 붙어있다.

0:00 ~ 1:00

초반 1시간에는 문제를 다 읽고 바로 풀이가 보이는걸 짜려고 했다. 근데 풀이가 명확히 보이는건 없어서 일단 1번을 생각해봤다. 키를 배치하는 전략을 찾는 것은 어려울 것 같아서 다른 방향으로 생각해보다가 거꾸로 돌리면 되지 않을까 라는 생각을 하게 되었다. 그 아이디어가 핵심이었고 정방향 / 역방향 탐색을 해주면 문제가 쉽게 풀린다.

1:00 ~ 1:30

2번을 고민했다. 2번과 4번이 컨셉이 같은 문제인데 2번이 요구하는게 적어서 더 쉬울 것 같았다. 조금 고민하니까 2번 풀이가 나왔고 금방 짜서 맞았다. dp를 잘 돌리면 된다.

1:30 ~ 3:00

3번과 4번은 섭태 풀이밖에 모르겠어서 5번을 좀 고민했다. 5번이랑 같은 상황인데 일반그래프이고 최종 간선 개수를 세는 문제가 USACO 22 Dec 플래티넘에 나왔기 때문에 그 문제랑 비슷한 접근으로 고민해봤다. 그러나 아무리 고민해도 떠오르는게 없었고 문제를 다시 읽으니까 트리라는 조건이 있었다. 이를 이용해서 100점 풀이를 금방 만들었지만 말도 안 되는 풀이었고 예제만 맞았다.

3:00 ~ 3:30

찾아둔 서브태스크 풀이를 모두 짜서 긁었다.

3:30 ~ 4:30

34번을 고민해봤지만 3번은 떠오르는 그리디가 없었고 4번은 나이브말고 감이 안 잡혔다. 그래서 다시 5번으로 돌아왔고 그림을 조금 그려보니 bcc를 관리하면 개수를 세기 쉬울 것 같다는 생각이 들었다. 100점을 의도하고 짰지만 bcc 갱신과정이 꼬여버렸고 일단 나이브하게 갱신해서 제곱 섭태를 긁었다.

4:30 ~ 5:00

5번에서 블록컷트리를 만들어서 관리하면 풀릴 것 같다는 추측을 했지만 너무 식이 복잡해서 코딩을 하진 못했다. 대회 끝나고 짜본 결과 맞는 풀이였다.