2021 국가대표 멘토링 교육 - 1주차

JOISC Day1에서 미친 난이도의 셋에 거하게 맞고 똑-떨당한 뒤 국대교육을 받게 되었다. 많이 안타까웠고 멘탈도 많이 나갔지만 뭐 어쩔 수가 없다;;

 

1주차 셋은 백준 네 문제 앳코더 한 문제로 다섯 문제를 받았다. 그 중에 한 문제밖에 못 풀었다;; 나 뭐지

 

1. Trous de Loup

 

이분탐색을 하고 싶게 생겼으니 이분탐색을 한다. 어떤 고정된 구간을 본다면 그 내부에서 길이가 d이고 합이 최대인 구간을 뽑아내는 것이 이득이다. 이때 앞쪽 구간부터 본다고 하면 덱으로 문제를 최적화할 수 있다. (현재 구간 내에서 가장 합이 최대인 구간을 앞에 두고 자신 뒤에 있는 구간들 중에서는 자기보다 합이 큰 애가 없는 구간들을 인덱스가 단조증가하게 배치하면 된다.) 그럼 결정문제가 O(N)에 풀리고 문제가 O(NlogN)에 풀린다.

 

2. Highway Modernization

 

음... 잘 모르겠다. 최대인 케이스는 dp를 하면 되지 않을까 싶다. 최소인 케이스는 이분탐색을 하면 되지 않을까 싶다. 근데 확신도 안 들고 잘 정리가 안 되서 망했다.

 

3. Cow Optics

 

내가 제일 싫어하는 유형의 어지럽고 막막한 문제다. 마치 JOISC 2021 Day1 2번을 마주한 느낌... 아마 놓여지는 거울은 뭔가 현재 이미 등장한 x좌표와 y좌표에서만 나오지 않을까 싶다. 그럼 좌표압축을 할 수 있고, x축 방향으로 구간을 압축하고 y축 방향으로 구간을 압축해서 간선을 잘 이어보면 되지 않을까 싶지만 애초에 첫 관찰부터 확신이 안 되고 정리도 잘 안 되서 망했다.

 

4. 애완 트리

 

딱 봐도 트리 dp로 풀릴 거 같이 생기긴 했다. dp값을 dp[v][a][b]=(정점 v 아래의 서브트리에서 v에서 가장 먼 점과의 거리가 a고 지름이 b인 경우의 수)로 정의해보니까, 당연하게도 시복이 터질 거 같았다. 그러고 나서는 다이아2라는 난이도에 쫄아서, 뭔가 내가 모르는 이상한 테크닉을 쓸 거 같아서(출제자 이름값도 있어서...) 그냥 던졌다.

 

5. Dam

 

문제를 잘못 이해하고 쉬운 문제인 줄 알고 코딩했는데, 마지막 예제가 안 나왔다. 그리고 다시 고민해보니 풀이가 잘 안 나왔다. 그래서 포기.

 

후기:

내 실력이 그냥 딸리는 거 같다... jjang36524는 세 문제 풀었던데 국대할만한 거 같다.