1번

선수들의 실력을 가장 많이 포함하는 길이가 K이하인 구간을 찾았다고 합시다. 

이 구간에 포함되는 선수들을 다른 버스를 타야하고 나머지 선수들은 구간에 포함된 선수 중 한명과 같은 버스를 탈 수 있습니다. 

따라서 찾은 구간에 포함되는 선수들의 수를 출력하면 됩니다. 

투포인터 테크닉을 써서 O(N)에 가능합니다.


2번 

n=10000까지 회문인 수는 몇 개 안됩니다. (300개?) 

모든 조합을 시도 해보는데 이분 탐색같은 걸로 시간을 줄여줍시다. DP도 가능할 듯 합니다.


3번

초기 상태에서 '>' 모양을 붙여서 나가는 대신 완성된 상태에서 가장 많이 떼내는 방법을 생각해봅시다. 

떼내는 정점은 Degree가 2여야 하고 그 정점과 연결된 정점을 u, v 라고 하면 그래프에 uv간선이 그래프에 포함되어 있어야 합니다.

 생각해보면 어떤 정점을 떼내었을 때 다른걸 떼낼 수 없는 경우가 존재하지 않기 때문에 보이는대로 다 떼면 됩니다. 

떼낼때 마다 그래프 갱신(Degree 수정, 간선 지우기)을 빠르게 하는게 관건입니다.


4번

Simulated annealing (SA)을 이용해서 만점을 받을 수 있습니다.

https://en.wikipedia.org/wiki/Simulated_annealing


예제로는 검증하기 힘드니 문제에 나와 있는 데이터 생성 방식을 참고하여 데이터를 많이 만듭니다.

처음에는 랜덤 순열부터 시작하여 랜덤하게 두 수의 자리를 바꾸는 방식으로 SA를 합니다.

상수를 조절하면서 변화를 관찰하고 제일 좋은 상수를 찾으면 됩니다. step횟수를 늘리기 위해서 새로운 상태를 계산하는 부분을 빠르게 구현해야 합니다.


5번은 결정문제로 바꿔서 이분탐색하면 될 거 같은데 어렵네요 ㅎ..