별도로 명시되지 않은 경우 실행 시간은 모두 $O(n)$이며, 구체적인 수치가 주어진 경우에는 TL이 1초입니다.
문제는 떠오르거나 고안한 순서대로, 즉 상당히 무작위적인 순서로 나열되어 있습니다.
#앵무새
어떤 정보 64바이트를 전달해야 합니다. 이를 위해 특별히 훈련된 앵무새 320마리가 있으며, 각 앵무새는 0부터 255까지의 수 하나를 기억할 수 있습니다. 모든 앵무새는 언젠가는 목적지에 도착하여 자신의 바이트를 알려 주지만, 풀어 준 순서와 다른 순서로 도착할 수도 있습니다. 앵무새들은 겉모습으로는 서로 구별할 수 없습니다.
#최솟값과 최댓값
무게가 서로 다른 돌 68개가 주어집니다. 100번의 무게 비교로 가장 가벼운 돌과 가장 무거운 돌을 찾아야 합니다.
#순열
64개의 원소로 이루어진 순열이 있습니다. 주어진 위치 집합에 어떤 원소들이 있는지 질문할 수 있습니다(원소 목록은 임의의 순서로 알려 줍니다). 6번의 질의로 순열을 복원하십시오.
#볼록 껍질
다음 두 종류의 쿼리에 답해야 합니다:
- 볼록 껍질에 점을 추가합니다.
- 점이 볼록 껍질 내부에 있는지 확인합니다.
두 연산 모두 온라인으로 $O(\log n)$에 수행됩니다.
#등비수열
임의의 모듈러에 대해 $\frac{1-a^n}{1-a}$를 $O(\log n)$에 계산하는 방법을 찾으십시오.
#포켓몬
토너먼트에는 1024종의 포켓몬이 참가합니다. 포켓몬 전문가인 여러분은 누가 누구를 이길 수 있는지 알고 있습니다. 다시 말해, 여러분은 정점 1024개와 간선 $1023 \times 1022 : 2$개로 이루어진 토너먼트 그래프를 완전히 알고 있으며, 이 그래프에서는 모든 두 정점이 정확히 하나의 방향 간선으로 연결되어 있고 이 간선이 가능한 대결의 승자를 결정합니다. $a \to b$와 $b \to c$로부터 $a \to c$가 따라 나오지는 않는다는 점에 유의하십시오.
여러분에게는 몬스터볼이 10개 있습니다. 1024가지 종류의 포켓몬 각각에 대해 그 포켓몬을 이기는 포켓몬이 여러분의 팀에 존재하도록 10마리의 포켓몬으로 팀을 구성하십시오. 같은 포켓몬끼리 대결하면 여러분의 포켓몬이 이긴다고 가정하십시오.
#정렬
정렬할 수 있습니까
- 돌 5개를 8번 저울질해서?
- 7번의 무게 비교로 돌 5개를 정렬할 수 있습니까?
- 돌 20개를 60번의 무게 측정으로?
#원 안의 점들
원점을 중심으로 하는 단위 원 안에 균등하게 분포된 $n$개의 점이 주어집니다. 이 점들을 원점으로부터의 거리 순으로 평균 $O(n)$에 정렬하는 알고리즘을 제안하십시오.
#이진 탐색
인터랙터 측에서 어떤 구간에 균등하게 분포된 $n$개의 무작위 수로 이루어진 배열을 생성한 다음 정렬했습니다. 한 번의 쿼리로 배열의 인덱스를 지정하여 그 위치에 있는 수를 알아낼 수 있습니다. 평균적으로 $O(\log \log n)$번의 연산으로 주어진 배열에 수 $x$가 있는지 판별해야 합니다.
#무작위 이진 탐색
가운데 원소 대신 임의의 원소를 고르는 다음과 같은 이진 탐색이 주어져 있습니다:
int lower_bound(int x) {
int l = 0, r = n - 1;
while (l < r) {
int m = l + rand() % (r - l);
if (t[m] >= x)
r = m;
else
l = m + 1;
}
return l;
}
모든 키와 쿼리는 무작위입니다. $n \to \infty$일 때, 무작위 이진 탐색은 일반 이진 탐색에 비해 평균적으로 몇 배 더 많은 반복을 수행합니까?
#닫힌 꺾은선
두 개의 닫힌 단순 꺾은선(자기 자신과 교차하지 않는 닫힌 꺾은선)이 주어집니다. 평행 이동, 회전, 닮음 변환을 이용하여 두 꺾은선을 서로 겹치도록 옮길 수 있는지 판별하십시오.
#비감소 배열
$n$개의 정수로 이루어진 배열이 주어집니다. “한 원소에 다른 임의의 원소를 더한다"는 연산을 $2n$번 사용하여 이 배열을 비내림차순으로 만들어야 합니다.
#짝수 길이 사이클
무향 그래프가 주어집니다. 이 그래프에 길이가 짝수인 단순 사이클이 있는지 판별하십시오.
#$k$번째 순서 통계량
$n$개의 정수로 이루어진 배열이 주어집니다. 이 배열에서 $k$번째로 작은 원소를 $O(n)$에 찾으십시오.
#지배 원소
$n$개의 원소로 이루어진 배열이 주어집니다. 구간 $[l, r]$에 지배적인 원소, 즉 그 구간에서 적어도 $\frac{r-l}{2}$번 등장하는 원소가 있는지 묻는 $m$개의 질의에 답해야 합니다. 실행 시간은 $O((n+m) \log n)$입니다.
#트리 파괴
루트가 있는 트리가 주어집니다. 매 반복마다 (남아 있는 모든 정점 중에서 같은 확률로) 정점 하나를 선택하고, 그 정점에 해당하는 서브트리 전체를 삭제합니다. 이 과정이 평균적으로 몇 번의 시행 동안 계속되는지, 즉 트리의 루트가 삭제되는 반복 번호의 기댓값을 구하십시오.
#구간에서 $k$번째 원소
$n$개의 정수로 이루어진 배열이 주어집니다. 임의의 구간에서 $k$번째 순서 통계량을 구하는 쿼리 $m$개에 답해야 합니다. 실행 시간은 $O((n+m) \log n)$입니다.
#구간 내 서로 다른 수
$n$개의 정수로 이루어진 배열이 주어집니다. 임의의 구간에 있는 서로 다른 원소의 개수를 묻는 $m$개의 질의에 답해야 합니다. 시간 복잡도는 $O(m\sqrt{n})$입니다.
#체육
어느 대학에서는 체육 과목의 이수 여부가 출석 횟수로 결정되므로, 학기 말까지 수업일이 며칠 남았는지 아는 것이 중요합니다(특히 수업을 많이 빠졌을 때 그렇습니다). 학기는 $m$일 동안 이어집니다. 학과 사무실은 다음 두 가지 유형의 명령 $n$개를 차례로 내립니다:
- $l$일부터 $r$일까지의 모든 날을 휴일로 지정합니다 (체육 출석을 채울 수 없습니다)
- $l$일부터 $r$일까지의 모든 날을 수업일로 지정합니다 (체육 수업은 취소해도 됩니다)
이때 명령은 이전 명령들의 효력을 부분적으로 취소할 수 있습니다.
각 명령이 내려진 후마다 학기 중 수업일의 총 개수를 계산해야 합니다. 시간 복잡도는 $O(n \log n)$입니다.
#영합
$n$개의 정수로 이루어진 중복집합이 주어집니다. 원소의 합이 $n$으로 나누어떨어지는 공집합이 아닌 부분집합을 아무것이나 하나 찾으십시오.
#메타 문제
이 문제에서는 임의의 문자열이 주어지며, 이 문자열로부터 출제자만 아는 방식으로 yes/no 답이 생성됩니다. 문제에는 테스트가 100개 있습니다. 여러분에게는 20번의 시도 기회가 있습니다. 피드백으로는 각 테스트에 대한 판정 결과를 확인할 수 있습니다. 판정 결과는 OK(답이 일치함)와 WA, 단 두 가지뿐입니다. 0으로 나누기, 테라바이트 단위의 메모리 할당 등의 시도 역시 WA로 처리됩니다. 이 문제를 「풀어」 보십시오.
#메타 문제 2
문제 조건은 「메타 문제」와 같지만, 통과한 테스트의 개수만 알려 줍니다.
테스트 100개, 시도 70회.
#메타 문제 3
조건은 «메타 문제»와 같지만, 처음으로 통과하지 못한 테스트의 번호만 알려 줍니다.
테스트 10개, 시도 100번입니다.
#실
평평한 판자에 반지름이 $r$인 못 $n$개를 박았는데, 이때 평면 위의 대응하는 점들이 볼록 다각형의 꼭짓점을 이루도록 박았습니다. 이 못들에 실을 팽팽하게 감았는데, 이때 실은 못들을 원을 따라 «휘감습니다». 실의 길이, 즉 둥글게 감긴 부분을 고려한 이 다각형의 둘레를 구하십시오.
#만두
친구들이 거대한 직사각형 반죽 덩어리로 만두피를 만들기로 했습니다. 이를 위해 컵, 머그잔, 냄비 등 온갖 둥근 모양의 물건이 동원되었습니다… 그 결과 반죽은 반지름과 중심이 임의인, 서로 교차할 수도 있는 원 $n$개로 나뉘었습니다. 만두피가 몇 개 만들어졌는지, 즉 반죽이 몇 조각으로 나뉘었는지 세어 보고자 합니다. 시간 복잡도는 $O(n^2 \log n)$입니다.
#0에서 1까지
다음과 같은 코드가 주어집니다:
x = 0
while x < 1:
x += random()
x의 기댓값을 구해야 합니다.
(파이썬의 random은 0에서 1 사이의 임의의 실수를 반환합니다.)
#넓이
단위 정사각형 하나와 원 100개가 주어집니다. 이 원들이 덮는 정사각형의 넓이를 1% 미만의 오차로 계산해야 합니다.
#원
반지름이 $R$인 원이 있으며, 이 원을 외부 원이라고 부릅시다. 그 안에 반지름이 $r < R$인 원이 놓여 있으며, 이 원은 외부 원과 접합니다. 이어서 다음 규칙에 따라 무한히 많은 원을 그립니다. $k$번째 원은 다음 조건을 만족해야 합니다
- 바깥 원과 접해야 하며,
- 이전 (($k-1$)번째) 원과 접하고,
- 그러면서 최대 반지름을 가져야 합니다.
$k$번째 그러한 원의 반지름을 구하십시오($O(1)$에 계산되는 공식을 유도하십시오).
#블러프
카탸와 세료자가 게임을 하고 있습니다. 카탸는 카드 $n$장을, 세료자는 $m$장을 가지고 있습니다. 추가 카드 한 장이 테이블 위에 뒷면이 위로 오도록 놓여 있습니다. 이 카드를 특별한 카드라고 부릅시다. 플레이어들의 목표는 이 카드를 알아맞히는 것입니다. $n+m+1$장의 카드는 모두 서로 다르며, 처음에 플레이어들은 자신의 카드만 알고 있습니다. 플레이어들은 번갈아 가며 차례를 진행하며, 카탸가 먼저 시작합니다. 플레이어는 자신의 차례에 다음 중 하나를 할 수 있습니다.
- 특별한 카드를 맞히려고 시도합니다. 맞히면 그 플레이어가 이기고, 그렇지 않으면 집니다. 어느 경우든 게임은 그것으로 끝납니다.
- 덱에 있는 카드 중 아무 카드나 하나 지목합니다. 상대에게 그 카드가 있다면, 상대는 반드시 그 카드를 공개하고 게임에서 제외해야 합니다. 반면 상대에게 그런 카드가 없다면, 상대는 그 사실을 알립니다.
두 플레이어가 모두 최적으로 플레이할 때 카탸가 이길 확률은 얼마입니까? 시간 복잡도는 $O(nm)$입니다.
#도달 가능성
중복 간선이 없는 방향 그래프가 주어집니다. 모든 정점 쌍 $u$와 $v$에 대해 $u$에서 $v$로 도달할 수 있는지 판별하십시오. 정점의 개수는 2000개 미만입니다.
#화폐 수집가
탐욕스러운 동전 수집가가 $n$명 있는데, 이들은 자신이 두 개 이상 가지고 있는 동전을 내주는 대가로 자신에게 전혀 없는 동전을 받을 때에만 교환에 응합니다. 동전의 종류는 모두 $k$가지입니다. 각 수집가와 수집가 세료자가 가진 각 종류의 동전 개수가 알려져 있습니다. 세료자는 탐욕스러운 수집가들과 교환하여 자신이 가진 서로 다른 동전의 수를 최대화하려고 합니다. 탐욕스러운 수집가들끼리는 서로 교환하지 않는다고 가정하십시오.
임의의 다항 시간 알고리즘을 고안하십시오.
#공주
어느 왕국에 공주가 살고 있었습니다. 공주는 너무나 아름다워서 왕국의 모든 젊은이가 그녀와 결혼하고 싶어 했습니다. 공주는 까다로웠기 때문에 나라에서 가장 잘생긴 젊은이와만 결혼하기로 굳게 결심했습니다.
그녀는 가장 잘생긴 청년 $n$명의 목록을 만들고, 매일 그들을 무작위 순서로 한 명씩 불러들입니다. 청년이 한 명씩 찾아올 때마다, 그녀는 그와 결혼할지 말지를 결정합니다. 그와 결혼하더라도, 그녀는 그가 정말로 가장 잘생긴 사람인지 확인하기 위해 나머지 청년들도 모두 만나 봅니다. 만약 그렇다면, 두 사람은 오래오래 행복하게 삽니다. 그렇지 않다면(가장 잘생긴 청년이 아닌 사람과 결혼했거나, 아예 결혼하지 않았다면) 공주는 스스로 목숨을 끊습니다.
공주는 기억력이 매우 좋아서 새로 온 청년의 아름다움을 이전의 모든 청년과 비교할 수 있으며, 또한 안목이 섬세하여 어떤 두 청년도 그녀에게는 똑같이 아름답지 않습니다.
공주가 가장 잘생긴 청년과 결혼할 확률을 최대화하는 전략을 세울 수 있도록 공주를 도와주십시오.
시간 복잡도는 $O(n^2)$입니다.
#나선
$(2n+1) \times (2n+1)$ 나선을 다음과 같은 형태의 행렬로 정의합시다:
$$ \begin{matrix} 21 & 22 & 23 & 24 & 25 \\ 20 & 7 & 8 & 9 & 10 \\ 19 & 6 & 1 & 2 & 11 \\ 18 & 5 & 4 & 3 & 12 \\ 17 & 16 & 15 & 14 & 13 \\ \end{matrix} $$여러분이 할 일은 임의의 직사각형 영역에 있는 수들의 합을 구하는 $q$개의 쿼리에 대한 답을 ($10^9+7$로 나눈 나머지로) 계산하는 것입니다.
$q \leq 100$, $n \leq 10^9$.
#폴란드 미로
$n$명의 관광객으로 이루어진 무리가 무한한 미로 안을 거닐고 있습니다. 미로는 시에르핀스키 삼각형 모양입니다. 칸 $(x, y)$는 x & y == 0인 경우에만 비어 있습니다.
관광객들은 미로를 헤매는 데 지쳐서, 모든 관광객으로부터의 거리의 합이 가장 작은 어떤 빈 칸에서 만나고자 합니다. 관광객들은 한 번의 이동으로 빈 칸을 따라 위, 아래, 왼쪽, 오른쪽으로 움직일 수 있습니다.
$n \leq 10^5$이고, 관광객들의 초기 좌표는 최대 $10^9$입니다.
#님 부분집합
0부터 $2^{32}-1$까지의 수 $n$개로 이루어진 집합 $A$가 있습니다. 이 집합의 부분집합 $B \subseteq A$ 중에서, 해당 크기의 더미들로 하는 님이 패배 상태가 되는 부분집합 $C \subseteq B$를 고를 수 없으면서 합이 최대인 것을 선택해야 합니다. 시간 복잡도는 $O(n \log n)$입니다.
#차수 균형
무향 그래프가 주어집니다. 진출 차수와 진입 차수가 같은 정점의 수가 최대가 되도록 각 간선에 방향을 지정해야 합니다.
#두 경로
방향 그래프가 주어집니다. $s$에서 $t$로 가는, 간선을 공유하지 않는 두 경로를 찾으십시오.
#술 취한 사람
취객이 수직선 위의 점 0에 서 있습니다. 그는 매초 확률 $p$로 오른쪽(좌표가 증가하는 방향)으로, 확률 $1-p$로 왼쪽으로 한 칸씩 이동합니다. 그가 언젠가 음수 좌표의 점에 도달할 확률은 얼마입니까?
#XOR 배낭 문제
$0$부터 $(2^{30}-1)$까지의 정수 $10^5$개로 이루어진 배열이 주어집니다. 이 배열의 서로 다른 부분 수열 중 xor-합이 주어진 수 $x$와 같은 것의 개수를 구하십시오.
#이반 수사닌
폴란드군은 마을 $s$에서 마을 $t$까지 가려고 합니다. 이 군대는 두 명의 헤트만, 카밀과 마테우시가 지휘합니다.
- 카밀은 낮에 군대를 지휘하며 도로를 따라 군대를 이끕니다.
- 마테우시는 밤에 군대를 지휘하며 비밀 오솔길을 따라 기동합니다.
각 헤트만은 행군하기 전에 이반 수사닌에게 길을 묻습니다. 이반은 폴란드군의 진격을 늦추고자 합니다.
도로 지도는 카밀이 알고 있습니다. 마찬가지로, 비밀 오솔길 지도는 마테우시가 알고 있습니다. 그러므로 이반은 그들을 그렇게 쉽게 속일 수 없습니다. 이반은 매번 해당 지도상에서 정착지 $t$와 군대 사이의 최단 거리가 엄격하게 감소하도록 이동 경로를 선택해야 합니다.
여러분은 도로와 오솔길의 지도를 그 길이와 함께 알고 있습니다. 이반이 군대를 $s$에서 $t$로 가능한 한 오래(가능하다면 무한히) 이끌 수 있도록 도우십시오.
#잼
빈 잼 병 $n$개가 한 줄로 놓여 있습니다. $i$번째 병의 용량은 $v_i$그램입니다.
칼손은 이 병들을 $m$단계에 걸쳐 잼으로 채웁니다. 각 단계에서 그는 수 $l$, $r$, $x$, $y$를 고른 다음, $l$번부터 $r$번까지의 병 위를 날아가며 다음 연산을 수행합니다. $l$번 병에는 잼 $x$그램을, $(l + 1)$번 병에는 잼 $(x + y)$그램을, $(l + 2)$번 병에는 $(x + 2y)$그램을 넣고, 이런 식으로 $r$번째 병까지 진행하며 그 병에는 잼 $x + y(r - l)$그램을 넣습니다.
꼬마는 각 병마다 그 병이 가득 차게 되는 가장 작은 연산 번호를 알아내고 싶어 합니다.
$n, m \leq 10^5$
#미로
세료자가 $n \times m$ 크기의 미로에서 길을 잃었습니다. 각 칸은 비어 있거나 벽입니다. 가장자리의 모든 칸은 벽입니다. 여러분은 미로의 출구가 어디에 있는지는 알지만, 세료자가 어디에 있는지는 알지 못합니다. 세료자의 시작 위치와 관계없이, 따라 움직이고 나면 출구가 있는 칸에 도착하게 되는 방향(위, 아래, 왼쪽, 오른쪽)의 수열을 만들어 주십시오. 벽 쪽으로 가라고 지시하면 아무 일도 일어나지 않습니다.
아무 다항 시간 알고리즘이나 고안하십시오.
#원숭이
라틴 알파벳 문자 $10^5$개로 이루어진 문자열이 주어집니다. 원숭이가 키보드의 키(26개 문자 중 하나)를 무작위로 누르다가, 이 문자열을 전부 입력하면, 즉 원래 문자열이 입력된 문자열의 부분 문자열이 되면 멈춥니다. 이렇게 되기까지 누른 키 개수의 기댓값은 얼마입니까?
#최솟값의 기댓값
구간 $[l_i, r_i]$에서 균등하게 분포하는 확률 변수 $n$개가 주어집니다. 각 변수마다 고유한 구간이 있습니다. 이 확률 변수들의 최솟값의 기댓값을 구하십시오.
임의의 정확한 다항 시간 알고리즘을 고안하십시오.
#노이즈가 있는 XOR
어떤 수 $x$가 정해져 있습니다. 다음과 같은 형식의 쿼리를 할 수 있습니다: 수 $y$를 제시하면 $x$, $y$, $m$의 XOR 합에서 1인 비트의 개수를 답으로 받습니다. 여기서 $m$은 무작위로 생성된 마스크로, 각 비트가 1일 확률은 $p = \frac15$입니다. 즉, $x \oplus y$의 각 비트가 확률 $y$로 반전되며, 1인 비트의 개수가 반환됩니다. 명확히 하자면 다음과 같습니다:
x = # ...
def mask(p=0.2):
r = 0
for i in range(32):
if random.random() < p:
r += 2**i
return r
def query(y):
return bin(x ^ y ^ mask()).count('1')
여러분의 과제는 10000번 이하의 시도로 수를 맞히는 것입니다.
#외판원
평면 위에 $3 \cdot 10^5$개의 점이 주어집니다. 이 중에서 500개의 점으로 이루어진 임의의 부분집합을 고르고, 그 부분집합에 대해 외판원 문제를 푸십시오. 즉, 이 점들을 모두 지나는 길이가 최소인 순환 경로를 찾으십시오.
#애너그램
문자열 $s$에서 문자열 $t$의 애너그램(문자의 순열)인 첫 번째 부분 문자열을 $O(n)$에 찾으십시오.
#함수형 그래프
각 정점에서 정확히 하나의 간선이 나가는 $n < 10^5$개의 정점으로 이루어진 방향 그래프가 주어집니다. “정점 $v_i$에서 시작하여 $k_i < 10^{18}$번 이동하면 어느 정점에 도달하는가"라는 $q < 10^5$개의 쿼리에 $O(q + n)$ 시간 안에 답해야 합니다.
#비동기 모자 게임
세료자와 그의 친구 $(n - 1)$명은 «모자» 게임을 하기로 했습니다. 이 게임에서 한 플레이어는 제한된 시간 안에 최대한 많은 단어를 설명하여 파트너가 그 단어들을 맞히도록 해야 합니다.
모든 플레이어는 다른 모든 플레이어와 한 번씩 짝을 이루어야 합니다. 보통 게임은 다음과 같이 진행됩니다:
- 1번 플레이어가 1분 동안 2번 플레이어에게 단어를 설명하고,
- 2번째 플레이어가 3번째 플레이어에게 단어를 설명하고,
- …,
- $n$번째 플레이어는 1번째 플레이어에게 단어를 설명하고,
- 1번째 플레이어는 3번째 플레이어에게 단어를 설명하고,
- 2번 플레이어는 4번 플레이어에게 단어를 설명하고…
…이런 식으로 $(n-1)$번째 플레이어가 $(n-2)$번째 플레이어에게 단어 설명을 마칠 때까지 계속됩니다.
친구가 많이 모이면 게임이 꽤 오랜 시간이 걸릴 수 있습니다. 세료자는 참가자 쌍들이 동시에, 그리고 어떤 순서로든 서로 소통할 수 있도록 허용한다면 게임이 최소 얼마 동안 지속될 수 있는지 궁금합니다.
주어진 $n \le 500$에 대해 최소 시간 $k$와 그에 해당하는 일정을 구하십시오.
#랜덤 커피
당신이 일하는 회사에는 알 수 없는 수의 사람이 고용되어 있으며, 그 수는 1명부터 무한대까지 같은 확률로 가능합니다. 외로움을 덜기 위해 모든 직원은 «random coffee»에 참여합니다. 매주 당신은 회사에서 무작위로 정해진 한 사람과 만나 커피를 마시며 무엇이든 이야기를 나눕니다.
당신은 random coffee에 $n$번 참여하여 $k$명의 서로 다른 사람과 이야기를 나누었습니다(그중 일부와는 두 번 이상 만났습니다). 회사에서 일하는 사람 수로 가장 가능성이 높은 값은 얼마입니까?
#마피아
「마피아」 게임은 13명이 하며, 그중 10명은 시민이고 3명은 마피아입니다. 모든 역할은 표준 트럼프 카드 덱을 사용하여 나누어 줍니다. 미리 빨간 카드 10장과 검은 카드 3장을 골라 섞어 두고, 검은 카드를 뽑은 사람이 마피아가 됩니다. 모든 카드는 서로 다르며 모두에게 알려져 있습니다. 게임은 낮 투표로 시작합니다.
시민은 어떻게 해야 확실하게 이길 수 있습니까?