Notable Solved Problems 3호

2023/11/14~2023/3/1

NERC 2020 Online #G - Geometrical Combinatorics

• 파스칼의 삼각형 위에 삼각형을 그려서, 삼각형 안에 있는 숫자를 더한 값을 찾는 문제입니다.
• 입력을 45도 돌리면 제1사분면에만 삼각형이 딱 이쁘게 잘 들어가게 됩니다.
• $nCk$에 대해 모든 $k$에 대한 값을 찾으면 됩니다. 하키스틱으로 빠르게 답을 찾을 수 있습니다.
• 그러면 됩니다. 별 거 없는 문제입니다.

연세대학교 강원도대학생코딩경진대회 #E - 육각형 순회 (28285)

• 벌집 같은 육각형 형태의 지도에서 한 점이 주어질 때, 그 점을 시/종점으로 하는 해밀토니언 사이클을 찾는 문제입니다.
• 구성적으로, 임의 크기의 지도에서 사이클을 찾을 수 있습니다. 현재 점을 출발점으로 하는 경로를 적절히 출력해주는 것만 구현하면 됩니다.

UCPC 2020 #L - 피자 배틀

• 두 플레이어가 피자 조각을 골라 먹는데, 더 많이 먹도록 하는 전략을 찾는 게임 이론 문제입니다.
• n도 작고 각 피자 조각의 크기도 작아서, 제곱 곱하기 피자 조각의 크기 만큼의 dp를 짜도 됩니다. 이후는 적절히 하면 됩니다.

SciOI 2023 #A-3 - 균형 잡힌 등급

• 문제를 해석해 보면, 결국 수열을 3개로 쪼개서 부분 수열의 합의 차이를 최소화하는 문제임을 알 수 있습니다.
  • 이는, 등급 간 관계가 나뉘는 부분이 만들어지기 생각보다 힘들다는 것을 알아차리면 알 수 있습니다.
• 적절한 lower_bound를 사용하면 풀 수 있습니다. 사실 플4까지 갈 정도의 문제인가 싶습니다.

SciOI 2023 #B-1 - 라면 배달하기

• 트리에서 K개의 점을 방문하는 데 걸리는 시간의 최솟값의 합을 구하는 문제입니다.
• 많은 플레급 조합론 문제와 비슷하게, 더블카운팅 비슷한 것을 통해 풀 수 있습니다.
• (나름 직관적으로,) 각 점에 대해 생각하는 식으로 풀이했습니다.
• 너무 오래 전이라 정확히 어떤 느낌으로 풀었는지는 잘 모르겠습니다.

solved.ac Grand Arena #3 Div. 2 #E - 교차 집합 크기 합

• 집합 N개 중 임의의 k개의 교집합의 크기의 총합을 구하는 문제입니다.
• 집합의 원소로 출현하는 수가 많지 않기 때문에, 이들을 map으로 관리하면서 더블카운팅으로 풀어내는 조합론 문제입니다.

solved.ac Grand Arena #3 Div. 2 #F - TSM

• MST의 비용이 주어지면 간선에 가중치를 부여하는 문제입니다.
• 그래프의 아무 간선이나 잡고 가중치를 1 늘리면 MST의 비용은 그대로이거나1 늘어납니다.
• 즉, 간선의 순서를 적절하게 잡고 가중치를 순서대로 최솟값부터 최댓값까지 늘리면 MST의 비용은 최솟값부터 최댓값까지가 모두 1번 이상 선형적으로 나옵니다.
• 그렇다면 이분탐색을 쓸 수 있습니다. 쓰면 풀립니다.

제3회 초콜릿컵 #H - 삼각 초콜릿 포장 (Bitter)

• 벌집 구조의 삼각형을 작은 삼각형으로 채우는 문제입니다.
• N을 12로 나눈 나머지가 0, 2, 9, 11일 때만 채울 수 있음을 증명했다는 큰 힌트가 있습니다. 각각에 대한 해를 찾으면, 더 큰 것을 더 작은 것을 기반으로 구성적으로 만들어낼 수 있습니다.
• 2, 9에 대한 답은 주어져 있습니다. 11과 12에 대한 답은 9에 대한 답을 그리고 거기에 연장하는 식으로 구할 수 있습니다.
• 이를 하드코딩하고(몇백 개밖에 되지 않습니다), 더 큰 크기는 작은 크기로 만들어주면 됩니다.