멘토교육 4주차 - BOI 2022 Day2

결과 74 + 100 + 100 = 274

30분

• 문제를 읽었다. 1번 문제가 인터렉티브였고, 나머지 문제는 배치였다. 1번 문제가 그닥 쉬워보이지 않아서 2번 문제를 잡았다.
• 숫자가 큰 것 부터 작은 것까지 답을 구하기라는 아이디어를 생각했고,
• 유파와 IOI Werewolf 식 트리 구성을 통해 풀 수 있다고 생각해 구현을 시작했다.

70분 2 AC

• 3번 문제를 읽었다.
• 가장 쉬운 서브테스크를 맞췄다.
• 비트 DP를 이용해 풀 것이라고 생각했고, 서브테스크 풀이를 금방 찾을 수 있었다.
• 풀 테스크 풀이도 조금 더 생각하니까 나왔다. 삼분탐색 또는 기울기 기준 이분탐색을 할 수 있는데, 후자를 택했다.
• 구현을 했는데 틀렸다.
• Cout의 Presicion 기본값이 6이라서 틀렸는데, 이걸 찾는 데 한참 걸렸다. 앞으로 실수를 쓸 때 유의해야겠다.

130 3 AC

• 3번 문제는 처음엔 가장 쉬운 15점 서브테스크조차 생각이 안났다.
• 짧은 길이에 대해 손으로 시도를 해보면서 유효한 전략이 있는지를 확인해봤다.
• 1111 / 0110/ 1001을 통해 15점 서브테스크를 풀 수 있음을 확인했다.
• 구현했다.

170분 1 15점

• 1111 / 0110 / 1001 을 반복적으로 질의해 탐색 범위를 2/3로 줄일 수 있음을 생각했다.
• 구현하는 도중, 알고보니 0000 / 1111 / 0110 / 1001을 이용하면 질의 4개에 탐색 범위를 1/2로 줄일 수 있음을 생각했다.
• 이 방법대로라면 대략 30*4 = 120 개정도의 쿼리를 써, 고득점을 얻을 수 있을 것이라고 생각했다.
• 분할정복 구현인데, 2개가 아니라 4개로 나누는 분할정복이라서 구현에 신경을 조금 썼다.
• 실수를 써서 분할 지점을 계산하고, 이를 내림해 정수 범위에서 분할했다.

220분 1 74점

• 피보나치 수열을 이용한 최적화를 생각해보았다. 질의 n개에 탐색 범위를 F_n / 2^n 개로 줄일 수 있으니, n에 따라 사용되는 쿼리 횟수를 계산하니, 문제에서 요구하는 만점인 100정도로 수렴하는 것을 확인했다.
• 이를 구현하려고 노력했다. 어차피 수가 작아서 좀 비효율적인 구현을 했는데,
• 알고보니까 메모리 제한이 작아서 터졌다
• 이를 고치려고 시도하다가 시간이 끝났다
• 이때쯤 자습이 끝나서 친구가 내 방에 들어와 좀 떠들어서 집중을 못한 부분도 있다.

---

후기

• 난이도는 백준 기준으로 (없음) / 플1 / 다5 였다. 전체적으로 쉬운 셋이였다.
• 2번을 다2인 Werewolf처럼 풀었으니, 좀 오버킬이였다. 어쨌든 풀었으니 된 거 아닐까..
• 마지막에 생각한 1번 최적화는 거의 만점 풀이일 것이라고 예상했으나, 나중에 짜본 결과 77점밖에 못 얻었다.
• 1번 정해는 논문이던데, 그래도 이해하는 건 그렇게 어렵지 않았다. 정해가 꽤나 인상적이였다.