KOI는 Korean Olympiad in Informatics의 약자로, 한국 정보 올림피아드를 말합니다. 이 대회는 1차 대회와 2차 대회로 이루어져 있고, 1차 대회는 이산 수학을 바탕으로 하는 수학 문제들로 이루어진 1교시와 알고리즘 문제들로 이루어진 2교시로 나누어 진행됩니다. 자세한 정보는 koi.or.kr에서 확인하실 수 있습니다. koi.or.kr에 2교시 문제들의 풀이는 공개되어 있지만 1교시 문제들의 풀이는 제공하지 않아서 풀이를 작성했습니다. 팀원 찾기: 엄밀한 증명 고민 중... 1교시 풀이 문제의 지문은 링크에서 확인하실 수 있습니다. 또한, biko.kr에서 문제를 채점받을 수 있습니다. 다음은 각 문제에 대해 개인적으로 부여한 난이도와 실제 배점입니다. 1. 그래프의 지름 2...

문제 링크 재밌는 트리 DP 문제였다. 편의상 각 사원 $i$의 실력을 $V_i$, 부모를 $P_i$라고 하자. Subtask: $V_i > 0$ (17점) 더보기 그냥 최대한 많이 포함하면 이득이다. 그런데, 한 팀의 팀장을 전체 트리의 루트로 잡아버리면 다른 팀이 만들어질 수 없다. 또한, 루트의 $k$대 독자 후손 노드도 잡아버리면 다른 팀이 만들어질 수 없다. 따라서 1번 노드에서부터 DFS를 돌리다가 처음으로 자식 노드가 2개 이상이 된다면 가장 큰 2개만 골라주면 된다. 필자의 코드이다. Subtask: $N\le 5\ 000,\ P_i=i-1$ (12점) 더보기 직선형 그래프에서 문제를 풀면 된다. Kadane 알고리즘과 꽤 비슷하다. 각 노드 $i$마다 $\sum_{i\le k\le j}V..