본선 전날
eggx50000님이 본선 전략을 세워주셨다.
0:00 ~ 0:30 : 1,2번 풀기
0:30 ~ 1:00 : 3번 관찰
1:00 ~ 1:10 : 3번 구현
1:10 ~ 1:30 : 4번의 자명한 섭테 ac
1:30 ~ 2:00 : 5번의 자명한 섭테 ac
만약 k번이 그래프나 dp라면
2:00 ~ 3:00 : k번의 비자명한 섭테 고민
3:00 ~ 3:20 : k번의 비자명한 섭테 구현
3:20 ~ : 9-k번을 최대한 긁기
본선
0:00 ~ 0:05 : 100점
qi가 낮은 몬스터부터 사냥하는게 최적이므로 몬스터를 qi기준으로 정렬하고 몬스터를 사냥한 후 최종 레벨을 출력하면 된다.
0:05 ~ 0:26 : 200점
P는 반드시 T의 접두사이거나 T의 접두사를 뒤집은 문자열이라는 관찰을 할 수 있고,
P로 가능한 모든 경우를 시도해보면 P의 개수가 2K이고 한번 시도하는데
걸리는 시간복잡도가 O(NK)이므로 총 시간복잡도 O(NK^2)에 해결할 수 있다.
2번을 맞았을 때 4등 정도였다.
0:26 ~ 0:40 : 3번 고민
지금까지 봤던 NYPC 3번은 전부 실중위~골하위 정도의 난이도여서 올해도
그정도일거라 생각했는데 너무 어려웠다.. 계획을 수정해서 3번도 섭테를 긁기로 했다.
(알고보니 3번이 제일 어려운 문제였다)
0:40 ~ 1:06 : 227점
3번이 너무 어려워서 4번으로 넘어갔다. 문제를 읽어보니 이상한 그리디? dp? 느낌이 났다.
섭테 1은 N,Q 제한을 보니 백트래킹 같았고, 월드컵 느낌으로 구현하니 바로 27점을 받았다.
1:06 ~ 1:30 : 249점
다시 3번으로 돌아갔다. 1,2번 섭테는 유실된 라운드의 모든 경우를 시도해
만약 유실된 라운드가 R일때 가능한 경우가 하나도 없다면 B, 유실된 라운드가
B일때 가능한 경우가 하나도 없다면 R, 둘다 아니라면 ?을 출력해서 22점을 추가로 얻었다.
1:30 ~ 1:46 : 260점
5번의 섭테를 긁었다.
2번 섭테의 조건은 wi=1, ci=0이므로 그냥 다리를 옮기는 횟수만 출력하면 되고,
다리를 옮기는 횟수는 다리의 연결 요소의 개수 - 1과 같다.
금방 구현을 끝내 11점을 추가로 얻었고, 이때 3등이였다.
1:46 ~ 2:40 : 비자명한 섭테 고민
이제 3,4,5번의 자명한 섭테는 전부 긁었고, 비자명한 섭테 하나를 긁으면 동상 확정이였다.
해볼만한 섭테는 3번(?가 20개 이하,K=2), 4번(N,Q<=1000)이 있었다.
4번의 2번 섭테는 섭테 점수가 너무 높고 어려워 보여서 3번 섭테를 긁기로 했다.
?가 20개 이하인 섭테를 잡았고, 풀이가 떠올랐다.
현재 가능한 점수차의 최댓값, 최소값을 저장해서 반복문을 돌리면 O(N)에 이 경우가 가능한지 판단할 수 있고,
각 유실된 라운드에 대해 유실된 라운드가 R일때 불가능하면 B, B일때 불가능하면 R, 둘다 가능하면 ?을 출력해 O(20N)에 문제를 해결할 수 있다.
2:40~ : 맞왜틀
3번 섭테를 구현하는데 예제가 전부 맞는데도 계속 틀려서 결국 260점으로 마무리했다. 동상 커트라인은 275였다고 한다..
결과
전체 8~9등으로 특별상(레벨업상)을 수상했다.