PS 이야기

문제: 공식 홈페이지 채점: Yandex 1. nowruz 이 문제는 빈 칸과 장애물로 이루어진 직사각형 모양의 격자칸에서 빈 칸에 새로운 장애물을 적절히 넣어, 격자판의 빈 칸들을 트리 모양으로 만든다. 이 때, 만들어지는 트리에 포함된 리프 정점 수를 최대화하는 문제다. IOI 2010 Maze 문제와 비슷한 감이 있는 문제다. 문제 세팅 자체도 2차원 격자판이라는 것도 비슷하지만, 최적해가 아니라 최적근접해를 구하는 output only 문제라는 사실이 비슷하다. 이런 류의 문제는 TopCoder Marathon Match 줄여서 MM에 주로 나오는 것으로 알고 있다. 예전에 maze 문제를 해결할 때, 공부에 도움이 됐던 일루님의 글을 소개하고, 이 문제에 맞는 자세한 풀이는 추후 시간이 나면 추..

0. 문제 패키지 1. paint 길이가 $n$인 문자열이 있고 각 문자는 'X'혹은 '_'이다. 연속한 'X'끼리 묶어 블록이라 부르고, 총 $k$개의 블록이 있다. 문자열의 전체가 주어지지 않고 일부만 주어진다. 그리고 블록의 개수 $k$와 왼쪽부터 순서대로 블록들의 크기가 길이 $k$인 정수배열로 주어진다. 이 때 가능한 문자열이 여러 개가 있을 수 있는데, 가능한 모든 문자열에 대해서 항상 'X'가 놓이는 위치, 그리고 항상 '_'가 놓이는 위치를 구하는 문제다. 모든 위치에 대해서 '_'를 놓을 수 있는지, 'X'를 놓을 수 있는지를 나눠서 계산하면 된다. 아래와 같은 세 개의 DP 배열을 계산해놓으면 편하다.D[i][j] = 1번 블록부터 i번 블록을 1번째 문자부터 j번째 문자까지의 부분 문..

0. 문제 패키지 1. molecules $n$개의 자연수로 이루어진 집합 $S$가 있다. 한 집합 안에 같은 수가 여러 개 있을 수 있다. 이 때, 속한 원소의 합이 $l$이상 $u$이하가 되는 부분집합을 찾는 문제다. 이 문제에서 중요한 조건은 $u-l \geq \max(S) - \min(S)$이다. 부분집합의 크기 $k$를 정했을 때, 부분집합 원소 합의 최소값을 $s_k$, 부분집합 원소 합의 최대값을 $e_k$라고 하자. $[s_k, e_k]$와 $[l, u]$가 겹치는 것과 속한 원소의 합이 $l$이상 $u$이하가 되는 크기가 $k$인 부분집합이 존재하는 것은 필요충분조건이다. 왜냐하면 $u-l \geq \max(S) - \min(S)$이기 때문이다. 이에 대한 증명은 어렵지 않다. 위와 같은..

인접한 도시 사이를 이동하는데 걸리는 시간 1, 한 도시에 있는 관광지를 모두 둘러보는 시간 1이 걸리고 시작점이 주어졌을 때, 가장 관광지를 많이 방문하는 문제다. 물론 같은 관광지를 여러 번 방문해서는 안된다. 답이 될 수 있는 이동 경로는 아래 두 가지 중 하나이다. 1) 시작점에서 왼쪽으로 0칸 이상 가다가 어느 순간 오른쪽으로 이동하여, 시작점 보다 오른쪽으로 간다. 2) 시작점에서 오른쪽으로 0칸 이상 가다가 어느 순간 왼쪽으로 이동하여, 시작점 보다 왼쪽으로 간다. 즉, 쉽게 말하자면 방향을 한 번만 바꾼다는 것이다. 두 번 이상 방향을 바꾸어 왔다갔다 하는 것은 이동하는 시간만 늘리므로 항상 안좋다는 것을 알 수 있다. 2번 경우는 전체를 좌우로 뒤집었을 때 1번 경우와 같아지므로, 1번 ..

0. 표지 1. horses 문제: 말을 한 번 팔 때, 모두 팔아버리는 것이 좋음을 알 수 있다. $i$번 해에 말을 파는게 제일 좋기 위한 필요조건은 $i 1$인 $i$들 중 30개 보다 앞에 있는 날에 말을 파는 것은 안좋다는 것을 알 수 있다. 결국 답으로 가능한 구간이 최대 30개 생기는 꼴인데 매 쿼리마다 각 구간 별로 최대 $Y[i]$를 인덱스트리나 세그먼트 트리로 구해놓은 다음에 말을 팔고 남은 최대 이익을 계산하면 된다. 그러면 하나의 쿼리를 $30 \lg N$ 에 조금 비례한 회수의 연산으로 해결할 수 있다. #include using namespace std; #define MAXN 500005 #define TS 1048576 #define pb push_back #define sz..

0. 표지 1. boxes 문제: 최적의 이동 방법이 있다고 하자. 이 이동 방법에서는 절대 반시계방향으로 이동한 경로와 시계방향으로 이동한 경로가 교차하는 일은 없다. 이 때 경로라 함은 선물을 주러 이동하는 경로만을 얘기하며 선물을 다시 가지러 0번 지점으로 이동한 경로는 제외하고 말했다. 그렇기 때문에 문제에서 원형의 일부를 끊어 선형으로 바꾸어 생각할 수 있다. 선형으로 바꾼 경우, 0번 지점을 기준으로 음수 좌표와 양수 좌표를 나누어 생각할 수 있다. 결국 선형인 경우에 대해 욕심쟁이 기법으로 답을 전부 구해놓은 뒤, 모든 지점에 대해 끊어 선형으로 바꾼 뒤 답을 계산하면 된다. 선형일 때 주의해야할 점은 K개의 지점에 선물을 나누어주고 다시 0번 지점으로 돌아가는 경로는 원형에서 이루어지는게 ..

카자흐스탄 알마티에서 열리는 IOI 2015가 오늘 개막했다. 이전 IOI와 다르게 이번 IOI는 한국대표단에 조교로 소속되어 학생들과 같이 현장에 왔다. 출국 전 3주 동안 합숙 훈련을 마친 학생들에게 좋은 성적을 기대해본다. 원래 연습 세션 문제는 풀이를 적지 않지만, 문제가 상당히 괜찮아보여 처음으로 적어보려한다. 관련 자료들은 여기에서 다운받을 수 있다. 1. search 문제: 정렬되어 있는 배열이 입력으로 들어오므로 이분 검색을 통해 위치를 구하면 되는 아주 쉬운 문제다. 배열의 크기가 최대 100번이므로 7번의 질문으로 위치를 구할 수 있다. #include "graderlib.h" int find(int sub, int N, int X) { int s = 0, e = N-1, t; whil..

이 문제에서 독특한 성질의 그래프가 주어진다. 답으로 어떤 노드 집합을 구해야하는데, 이 노드 집합에 있는 각 노드는 서로 연결되어 있지 않으며, 각 노드별로 주어진 특성값의 합이 최대가 되어야한다. 아직 이 문제의 정해를 찾지 못 했다. 우선 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 등)도 공개가 안되어 ..