PS 이야기

이 문제에서 독특한 성질의 그래프가 주어진다. 답으로 어떤 노드 집합을 구해야하는데, 이 노드 집합에 있는 각 노드는 서로 연결되어 있지 않으며, 각 노드별로 주어진 특성값의 합이 최대가 되어야한다. 아직 이 문제의 정해를 찾지 못 했다. 우선 69점 받는 방법을 설명하겠다. 부분 문제1) 노드가 많아야 10개이므로 각 노드에 대해서 집합에 포함되는지 포함되지 않는지 구하는 경우의 수는 노드의 개수가 $n$개라 할 때, $2^n$개이다. $2^n$가지에 대해 모두 가능한 집합인지 확인하고, 최대값을 갱신하면 된다. 부분 문제2) 입력으로 주어지는 그래프에 간선이 존재하지 않는다. 따라서, 모든 노드의 값을 더해주면 된다. 부분 문제3) 입력으로 주어지는 그래프는 완전그래프다. 따라서, 노드의 값들 중 최..

이 문제는 여러 개의 부분 문제(서브태스크)가 하나의 문제를 이루어, 이 문제를 해결하기 위해서 3개의 코드를 짜야한다. 문제의 난이도는 매우 쉬운 편이며, 3개의 방법에 대해서 꼼꼼히 생각해야 되기 때문에 귀찮은 문제라고 생각한다. 1) 곤돌라 수열 확인 우선 곤돌라 수열에서 같은 수가 여러 개 있는 경우 이는 자명히 불가능한 곤돌라 수열이다. 그렇지 않은 경우, 주어진 곤돌라 수열에 있는 1 이상 $n$ 이하의 수에 신경써야한다. 곤돌라 수열에 1 이상 $n$ 이하의 수가 없다면, 이는 항상 가능한 곤돌라 수열이다. 만약 1 이상 $n$ 이하의 수가 하나라도 있다면, 초기 1의 위치를 짐작할 수 있으며, 다른 1 이상 $n$ 이하의 수가 그 1의 위치에 대해 상대적으로 올바른 위치에 있는지 확인하면 ..

오늘 오후 3시 IOI 2014 Contest Day 2가 끝나 모든 학생의 성적이 정해졌다. 대회 중간까지 우리나라 금메달이 한 명일 것 처럼 보였으나, 경기과고 2년 윤지학 군이 끝나기 30분 전에 holiday 문제를 해결하여 금메달 권에 들어왔다. 윤지학 군의 Day 2 성적은 6등으로 굉장히 우수했다. 이번 대회 총 6문제를 종합하여 보면 푼 사람 수를 기준으로 난이도를 따지면 gondola > wall > game > rail > friend > holiday 순이 된다. 개인적으로 wall 보다 game이 쉽다고 생각하며, friend 보다 holiday가 풀만하다고 생각된다. 예년과 다르게 채점 데이터 공개도 늦어지고, 온라인 저지도 없고, 문제 set (grader 등)도 공개가 안되어 ..