PS 이야기

문제 및 채점: oj.uz 번호가 0부터 $N-1$까지 매겨진 버섯 $N$ 개가 있다. 버섯은 두 종류로 구분할 수 있는데 눈으로 구분하기 힘들다. 기계를 사용하여 임의의 버섯들을 선택하여 순서를 정해 일렬로 기계에 넣을 수 있다. 기계에 넣으면 인접한 버섯 중에 종류가 다른 경우가 몇 개인지 확인하여 알려준다. 기계를 잘 사용하여 버섯 0과 같은 종류의 버섯 수가 몇 개인지 구하는 문제다. 10점 풀이 1 이상 $N-1$ 이하인 $i$에 대해 기계에 $[0, i]$ 순서로 버섯을 넣어 버섯 $i$가 버섯 0과 같은 종류인지 확인할 수 있다. 이때, 기계 사용을 최대 $19999$번 하게 된다. 더보기 #include #include "mushrooms.h" using namespace std; int ..

문제 및 채점: oj.uz $K$ 개 종류의 비스킷이 있고, 각 종류는 번호가 1부터 $K$까지 매겨져 있다. $i$번 종류의 비스킷의 맛 점수는 $2^{i-1}$이며, $i$번 종류의 비스킷은 $a[i]$ 개 있다. 비스킷 일부를 선택하여 비스킷 바구니 $x$ 개에 나눠 담을 건데, 각 비스킷 바구니에 담긴 비스킷 맛 점수의 합을 동일하게 해야 한다. 이렇게 나눌 때 만들 수 있는 바구니에 담긴 비스킷 맛 점수의 합의 수를 구하는 문제다. 다음과 같은 DP 배열을 정의하자. $$D[i] = \text{1번부터 }i\text{번 비스킷까지 사용했을 때 만들 수 있는 합의 수}$$ 초기값은 $D[0] = 1$이 된다. $i$ 번 비스킷까지 사용하여 만들 수 있는 합 중 가장 큰 수를 $b$라고 하자. 그러..

문제 및 채점: oj.uz $N$ 개의 정점으로 이루어진 트리가 주어진다. 각 정점에 $0$ 이상 $K$ 이하의 수를 서로 다르게 적는다. 수 $i$가 적힌 정점을 정점 $i$라고 하자. 정점 $s$에 인접한 정점에 적힌 수들이 배열 $c$로 주어질 때, 정점 $s$에서 정점 $t$로 가기 위해 어느 인접한 정점으로 이동하면 되는지 구하는 질문이 주어진다. 문제는 정점에 수를 적는 함수와, 주어지는 질문을 해결하는 함수 두 개를 작성하는 것이다. 단, 정점에 적는 수 이외에 전역 변수와 같이 외부 메모리를 참조하여 질문을 해결할 수 없다. 서브태스크 1, 2, 3, 4 이 서브태스크에 대한 풀이는 따로 서술하지 않겠다. 서브태스크 1, 2, 3은 주어지는 트리의 모양이 일자, 완전 이진 트리 등 정해진 ..

문제 및 채점: oj.uz 서로 다른 크기를 가지고 있는 식물 $N$ 개가 원으로 배치되어 있다. 편의상 $1$번 식물을 기준으로 시계 방향으로 차례대로 $N$ 번까지 번호가 매겨져 있다. $i$ 번 식물을 포함하여 시계 방향으로 연속하게 $K$ 개의 식물 중에서 $i$ 번 식물보다 키가 큰 식물의 수를 $R[i]$에 기록했다. 배열 $R$이 주어지고, 식물 번호 $i$와 $j$ 쌍들이 주어졌을 때, 배열 $R$의 내용으로 $i$번 식물과 $j$번 식물의 크기를 비교할 수 있는지, 비교 가능하다면 어떤 식물의 크기가 큰지 확인하는 문제다. 이 문제에서 각 쿼리는 실시간(online)으로 해결해야 된다. 풀이를 $N = 7$, $K = 3$, $R = [0, 1, 1, 2, 0, 0, 1]$인 경우를 예시..

문제 및 채점: oj.uz 티켓은 $N$ 개의 색 중 한 가지 색을 띄며, 각 색마다 $M$ 개의 티켓이 있다. 티켓에는 수가 적혀있는데, 티켓에 적힌 수는 서로 다를 수 있다. $K$ 번의 라운드를 진행할거고 각 라운드마다 $N$ 개의 서로 다른 색의 티켓을 뽑고, 어떤 수 $b$를 임의로 정해 $b$와 $N$ 개의 티켓에 적힌 수와 차이값을 구해 모두 더한 값을 $S$라 하자. 이때, $S$의 값이 최소가 되도록 수 $b$를 정한다. 한 라운드에 쓰인 티켓은 소멸되기 때문에 한 티켓은 최대 한 라운드에서만 사용 가능하다. 각 라운드마다 티켓을 적절히 골라 모든 라운드의 $S$ 값들을 다 더한 값을 최대화하는 문제다. 편의상 $N$은 짝수다. 우선, 각 라운드에서 $S$ 값을 계산할 때 문제에서 정의한..

문제 및 채점: oj.uz 정점이 $N$ 개인 양방향 그래프가 있다. 이 그래프에서 정점 $i$와 정점 $j$ 사이의 단순 경로의 수는 $p[i][j]$이다. $p[i][i] = 1$이며, $0 \leq p[i][j] \leq 3$이다. $p$ 배열의 내용만 주어졌을 때, 원래 그래프를 복원하는 것이 가능한지 확인하고, 가능하다면 그래프를 복원하는 문제다. 서브태스크 1 (11 점) $p[i][j] = 1$이다. 트리에서 각 정점 사이에 경로는 항상 한 개만 존재한다는 사실을 생각해보자. 즉, 모든 트리에 대해 $p[i][j] = 1$이기 때문에, 아무 트리로 그래프를 복원하면 된다. 아래는 만들 수 있는 단순한 트리 중 하나다. 서브태스크 2 (10 점) $p[i][j] = 0\ \mathrm{or}\..

문제: 공식 홈페이지채점: Yandex 1. doll 0번 정점을 시작점이라고 부르고 0번 정점은 나가는 간선이 정확히 1개다. 1번부터 M번까지 번호가 매겨진 나가는 간선이 정확히 1개인 트리거 정점 M개가 존재한다. 그리고 스위치라고 불리는 정점들은 번호가 음수로, 개수가 S개일 때, -1번부터 -S번까지 번호가 매겨진다. 스위치 정점은 나가는 간선이 정확히 2개이며 스위치 상태가 'X'일 때는 'X'로 표시된 간선으로 나가게 되며, 스위치 상태가 'Y'일 때는 'Y'로 표시된 간선으로 나가게 된다. 정점을 나가면서 동시에 스위치 정점의 상태가 뒤집힌다. 초기 0번 정점에서 이동을 시작하며, 이동을 하다가 다시 처음 0번 정점으로 돌아오는 순간 모든 스위치 정점의 상태는 'X'여야하며 트리거 정점은 ..

문제: 공식 홈페이지 채점: Yandex 1. combo 길이가 N인 'A', 'B', 'X', 'Y'로만 이루어진 문자열 S가 있다. 문자열 S의 첫 글자로 나타나는 알파뱃은 오직 한 번만 등장한다. press(p)라는 함수를 문제에서 제공하는데, press(p)에서 p는 길이가 4N 이하인 문자열이며, p의 부분문자열 중 문자열 S의 prefix 중 하나와 동일하며 가장 긴 문자열의 길이를 반환한다. 문제는 적은 횟수의 press(p) 함수 호출을 통해 문자열 S의 내용을 정확하게 알아내는 것이다. 여담으로, p의 부분문자열 중 문자열 S의 prefix 중 하나와 동일하며 가장 긴 문자열의 길이란, 즉, 문자열 S를 패턴이라고 생각하고 p를 전체 문자열이라고 생각했을 때, KMP 알고리즘의 실패 함수..

전체 결과: IOI Statistics, IOI 2017 official scoreboard대한민국 결과: IOI Statistics역대 대한민국 결과: IOI Statistics 2017년 국제정보올림피아드에서 우리나라는 금1, 은2라는 성적을 거둬 종합 10위에 그쳤다. 2017년도 문제들은 예년이 비해 좀 어렵게 느껴진다. 그리고 한 동안 안나왔던 Output Only 문제가 Day 1에 출제되었다. Nowruz 문제는 2차원 격자판의 빈 칸에 적절히 장애물을 설치해서 빈 칸들이 서로 트리를 이루게했을 때, 리프 정점의 개수를 많게하면 점수를 더 받는 문제다. 김동현 군을 제외한 우리나라 대표학생들은 Output Only 문제에서 상당히 적은 점수를 받았다. 불행인지 다행인지 nowruz에서 조금 ..

문제: 공식 홈페이지채점: Yandex 1. prize 1부터 v까지의 수가 적힌 크기가 N인 배열이 있다. 수 1의 갯수는 항상 1개고, 1보다 큰 t에 대해 수 t의 갯수는 수 t-1의 갯수의 제곱보다 많다. ask(i)를 호출하면, i보다 왼쪽에 있으면서 작은 수, i보다 오른쪽에 있으면서 큰 수를 알려준다. 이 때, 적은 횟수로 ask(i)를 호출하여 하나 뿐인 수 1의 위치를 찾는 문제다. 우선 배열에서 가장 많이 등장하는 수, 즉, 가장 큰 수는 등장 빈도가 과반이다. 가장 큰 수가 아닌 수의 최대 갯수는 조건에 따라 472개(1개, 4개, 21개, 446개, ...)다. 첫 번째로 가장 큰 수의 개수를 구하기 위해 최대 473번의 질문을 하여, 가장 큰 수의 위치 중 하나를 찾을 수 있다. ..