cho.sh

문제

문제를 고르고 내장 에디터에서 풀이를 작성해 보시기 바랍니다. 채점기가 실제 테스트 케이스로 코드를 바로 검증하고, 아카이브의 문제들도 자유롭게 둘러볼 수 있습니다.

전체 결과문제 32797개
제목난이도유형정답자시간 제한메모리 제한채점
색종이와 쿼리축에 평행한 직사각형 N개와 질의 직사각형 M개가 주어질 때, 각 질의 영역 안에서 한 점을 덮는 입력 직사각형 수의 최댓값을 구한다.어려움9세그먼트 트리분할 정복+2아직 제출이 없습니다1초512 MB채점 가능
내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)N = 2^k - 1개의 가중치 노드를 힙 순서로 번호 매긴 완전 이진 트리에서, 변이 노드를 지나지 않는 축에 평행한 직사각형 안에 들어가는 노드 가중치 합의 최댓값을 구한다.어려움9분할 정복동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
트리 깊이순열의 각 구간에서 최솟값을 루트로 삼아 만든 이진 탐색 트리에서, 반전이 정확히 K개인 모든 순열에 대해 각 노드 i의 깊이 합을 구해 소수 M으로 나눈 나머지를 출력한다.어려움9동적 계획법조합론+2아직 제출이 없습니다2초512 MB채점 가능
Jaki Jovsi길이가 최대 백만인 소문자 문자열이 주어질 때, l이 증가하고 r이 감소하는 팰린드롬 부분 문자열들의 중첩 수열의 개수를 998244353으로 나눈 나머지를 구한다.어려움9문자열동적 계획법+2아직 제출이 없습니다1초512 MB지문만 제공
체스판 이동N×M 체스판에서 홀수 행은 같은 색 인접 칸으로만, 짝수 행은 색 제약 없이 인접 칸으로 이동할 수 있을 때 1행에서 N행에 도착하는 경로의 수를 10^9+7로 나눈 나머지를 구한다.어려움9동적 계획법행렬+2아직 제출이 없습니다2초512 MB채점 가능
Gnalcats일곱 가지 염기 변환으로 이루어진 두 유전자가 충분히 긴 모든 단백질에서 같은 결과를 내거나 둘 다 실패하는지 판정한다.어려움9문자열스택+2아직 제출이 없습니다0.3초512 MB채점 가능
Falling Portals세계 i는 속도 i로 아래로 떨어지고, 높이가 같아지면 소가 다른 세계로 이동한다. i에서 Q_i로 가는 최단 시간을 기약분수로 구하거나 불가능하면 -1을 출력한다.어려움9기하그래프+2아직 제출이 없습니다2초512 MB지문만 제공
Klasika가중치 간선을 가진 루트 트리에 노드가 하나씩 추가될 때, 주어진 노드에서 특정 노드의 부분트리 안 임의 노드까지 경로 xor의 최댓값을 매 질의마다 구한다.어려움9트라이트리+2아직 제출이 없습니다5초512 MB지문만 제공
Lets Burn and Rob ManhootanBob이 격자 도로를 따라 왼쪽 위에서 오른쪽 아래로 갔다가 되돌아오는 닫힌 경로를 지날 때, 불탄 도로에 둘러싸인 블록 가치의 합에서 통행 비용을 뺀 최댓값을 구한다.어려움9동적 계획법그래프+2아직 제출이 없습니다2초512 MB지문만 제공
순례자의 기억과 감명받은 신격자 위 (1,1)에서 (N,N)으로 가는 단조 경로들이 만드는 서로 다른 0/1 문자열마다 등장 횟수 X에 대해 X^2+1을 더한 합을 구한다.어려움9동적 계획법조합론+1아직 제출이 없습니다8초1024 MB지문만 제공
완벽한 순례정수 격자점 N개로 닫힌 다각형을 만들되 서로 다른 변의 길이가 N-K 이하이고 인접하지 않은 변이 교차하지 않도록 하는 점들을 찾아 출력한다.어려움9기하수학+2아직 제출이 없습니다1초1024 MB지문만 제공
속독 강좌등차수열을 n으로 나눈 나머지가 p보다 작은지로 정의되는 0과 1의 수열 c에서 주어진 m비트 단어 w가 나타나는 위치의 개수를 센다.어려움9정수론문자열 매칭+2아직 제출이 없습니다2초512 MB채점 가능
Car washesn개의 세차장 각각에 가격을 정해, 각 고객이 예산 안에서 자신의 구간에서 가장 싼 세차장을 이용하도록 만들 때 총수입을 최대로 하는 가격을 구한다.어려움9동적 계획법구간+2아직 제출이 없습니다5초512 MB지문만 제공
Highway modernization마을 n개를 잇는 트리에서 간선 하나를 지우고 새 간선 하나를 추가해 연결성을 유지하면서 지름을 최소화하는 경우와 최대화하는 경우의 간선 선택을 각각 출력한다.어려움9트리그리디+2아직 제출이 없습니다3초512 MB지문만 제공
Trips간선 가중치가 1에서 3인 방향 그래프에서 같은 마을이나 도로를 여러 번 지나도 되는 경로를 길이 순으로 나열할 때, k번째로 짧은 경로의 길이를 구하고 그러한 경로가 k개 미만이면 -1을 출력한다.어려움9그래프동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
트리와 쿼리 14트리와 여러 쿼리가 주어지며, 각 쿼리는 중심 정점과 반지름으로 이루어진 k개 조건을 나열하고, 그중 k-1개 이상을 만족하는 정점의 수를 센다.어려움9트리BFS+2아직 제출이 없습니다5초1024 MB지문만 제공
N!!!...! mod PN, K와 소수 P가 주어질 때 a_0 = N, a_{n+1} = (a_n)!으로 정의된 수열의 a_K를 P로 나눈 나머지를 구한다. N, K, P는 최대 5×10^8이다.어려움9정수론수학+1아직 제출이 없습니다1초1024 MB지문만 제공
착한 말 나쁜 말N×N 격자의 각 세균이 직교 이웃으로 한 칸 이동하는 데 a, 좋은 칸에서 체비쇼프 거리 D 이내로 뛰는 데 b의 에너지가 들 때, 각 회의 칸마다 모든 세균이 모이는 최소 총에너지를 구한다.어려움9최단 경로그래프+2아직 제출이 없습니다2.5초1024 MB채점 가능
트리와 K번째 지름쿼리마다 두 정점의 번호를 맞바꾼 뒤, 트리의 모든 지름을 인코딩한 수 가운데 K번째로 작은 값을 구한다.어려움9트리수학+2아직 제출이 없습니다3초1024 MB지문만 제공
은광N×N 격자에 대해 행 또는 열을 반전하는 연산이 주어질 때마다, K×K 정사각형 안에 포함되는 은광 개수의 최댓값과 그 최댓값을 이루는 정사각형의 수를 구한다.어려움9구현누적 합+2아직 제출이 없습니다1초1024 MB지문만 제공
XOR과 집합과 트리와 쿼리집합을 XOR과 2배 연산으로 닫은 최소 집합을 정의하고, 트리 경로 위 값들의 닫힘에서 가장 작은 원소를 각 쿼리마다 출력한다.어려움9수학비트 연산+2아직 제출이 없습니다2초1024 MB지문만 제공
순찰 경로정점이 15개 이하인 연결 가중 무향 다중 그래프에서 모든 간선을 적어도 한 번 지나는 최소 길이의 닫힌 보행을 구한다.어려움9그래프동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
텐키 (Tenkey)0 키에서 시작해 커서 이동과 키 입력만으로 M으로 나눈 나머지가 R인 양의 정수를 입력할 때 필요한 최소 조작 횟수를 구한다.어려움9그래프BFS+2아직 제출이 없습니다2초512 MB채점 가능
우체국 5길이 L인 순환로 위 V개 마을 중 P곳에 우체국을 세워 각 마을에서 가장 가까운 우체국까지 거리의 합을 최소로 만들고, 최솟값과 우체국 위치를 출력한다.어려움9동적 계획법분할 정복+2아직 제출이 없습니다10초1024 MB지문만 제공
그래프 세기정점 2n개를 가진 무향 그래프 중 완전 매칭이 없지만 어떤 없는 변을 하나 추가하면 완전 매칭이 생기는 그래프의 동형류 개수를 998244353으로 나눈 나머지로 구한다.어려움9조합론그래프+2아직 제출이 없습니다5초512 MB채점 가능
Interesting Graph그래프의 임의의 7개 정점 중 두 정점이 바깥의 단절점을 지나야만 연결되도록 보장될 때, 1부터 n가지 색 각각으로 하는 적절한 색칠의 수를 구한다.어려움9그래프동적 계획법+2아직 제출이 없습니다5초512 MB지문만 제공
지식문자열 s에서 aa, bbb, ababab 블록을 넣거나 지우는 연산으로 길이가 x인 문자열을 만들 수 있는 경우의 수를 구해 998244353으로 나눈 나머지를 출력한다.어려움9문자열조합론+2아직 제출이 없습니다1초512 MB채점 가능
Airplane Cliques트리와 거리 한계 x가 주어질 때, 모든 두 정점 사이의 거리가 x 이하인 k개 정점 부분집합의 개수를 각 k마다 998244353으로 나눈 나머지로 구한다.어려움9트리분할 정복+2아직 제출이 없습니다2초512 MB지문만 제공
Disjoint LIS최장 증가 부분수열을 서로 원소를 공유하지 않는 두 개의 증가 부분수열로 나타낼 수 있는 n개 원소 순열의 개수를 998244353으로 나눈 나머지를 구한다.어려움9동적 계획법조합론+2아직 제출이 없습니다2초512 MB지문만 제공
One Goal정점 n개인 트리에서 모든 k-튜플에 대해 그 튜플의 1-중앙값 중 번호가 가장 작은 정점의 번호 합을 998244353으로 나눈 나머지를 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
Bitwise Xor고른 원소 두 개의 xor가 모두 x 이상인 비어 있지 않은 부분수열의 개수를 998244353으로 나눈 나머지로 구한다.어려움9비트 연산트라이+2아직 제출이 없습니다2초512 MB채점 가능
Counting Cactus주어진 작은 그래프(n은 13 이하)에서 부분 그래프의 변 집합 가운데 연결되어 있고 모든 변이 많아야 하나의 단순 사이클에 속하는 것의 개수를 998244353으로 나눈 나머지를 구한다.어려움9동적 계획법그래프+2아직 제출이 없습니다2초512 MB지문만 제공
Easy Win간선이 하나씩 추가될 때마다, 고른 간선들 중 어떤 비어 있지 않은 서로소 사이클 합집합도 돌 개수의 xor이 0이 되지 않도록 하는 부분집합의 최대 가중치 합을 구한다.어려움9게임 이론유니온 파인드+2아직 제출이 없습니다1.5초512 MB채점 가능
Grammarly문자열 s의 서로 다른 비어 있지 않은 부분 문자열을 정점으로 하고, a의 길이가 하나 짧은 부분 문자열 b로 향하는 간선을 둔 그래프에서 s에서 시작하는 단순 경로의 개수를 998244353으로 나눈 나머지를 구한다.어려움9문자열정렬+2아직 제출이 없습니다2초512 MB지문만 제공
Interactive Vertex트리에서 숨겨진 특별 정점을 찾아야 한다. 각 질의는 정점 x와 정점 집합을 주면 x가 집합의 모든 정점보다 특별 정점에 가깝거나 같은지 알려준다. 질의 횟수는 4*ceil(log2 n) 이하로 제한된다.어려움9트리분할 정복+2아직 제출이 없습니다2초512 MB지문만 제공
Jiry Matchings가중치가 있는 트리에서 각 k=1부터 n-1까지 정확히 k개의 간선을 고르는 매칭의 최대 총 가중치를 구하고, 불가능하면 "?"를 출력한다.어려움9트리동적 계획법+2아직 제출이 없습니다6초512 MB지문만 제공
K-pop Strings길이 n인 문자열 가운데 길이가 n-k 이상인 연속 반복(tandem repeat)이 하나도 없는 문자열의 개수를 35종 문자로 세어 998244353으로 나눈 나머지를 구한다. n은 100 이하, k는 16 이하이다.어려움9동적 계획법문자열+2아직 제출이 없습니다7초512 MB지문만 제공
Four Elements정수 구간 n개의 합집합에서 원소 4개의 합이 s인 부분집합의 개수를 998244353으로 나눈 나머지로 구한다.어려움9조합론수학+2아직 제출이 없습니다2초512 MB지문만 제공
Six Words정점 i의 퍼텐셜이 i이고 간선 i의 가중치가 i인 연결 그래프가 주어질 때, 선그래프의 선그래프에서 최소 신장 트리의 총 가중치를 구한다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다2초512 MB채점 가능
Seven Nevers순열에서 연속한 k개 원소를 지웠을 때 남은 수열의 최장 증가 부분 수열 길이를 모든 시작 위치마다 구한다.어려움9동적 계획법세그먼트 트리+2아직 제출이 없습니다2초512 MB채점 가능
Nine Judgesk개 문제에 대한 n명의 선호 순위가 주어질 때, 다수결 교환으로 이루어지는 마르코프 연쇄가 양의 확률로 무한히 자주 방문하는 p개짜리 문제 집합을 하나 출력한다.어려움9게임 이론조합론+2아직 제출이 없습니다2초512 MB지문만 제공
Eleven Problems문제 수 n이 11 이하일 때, 두 훈련 캠프의 득표 분포가 주어지면 두 원 그래프의 조각 순서를 정해 같은 문제 조각이 겹치는 면적 비율을 최대로 만든다.어려움9완전 탐색기하+2아직 제출이 없습니다2초512 MB지문만 제공
Um_nik의 알고리즘정점 2e6, 간선 2e6 규모의 이분 그래프가 주어질 때, 최대 매칭 크기의 0.95배 이상인 매칭을 찾아 출력하는 문제로, 상수 최적화가 필수적이다.어려움9그래프그리디+2아직 제출이 없습니다4초512 MB채점 가능
문자열 알고리즘모든 k에 대해 s를 길이 k의 블록으로 자르고 남는 부분을 버린 뒤, 해밍 거리가 1 이하인 블록 쌍의 개수를 구한다.어려움9문자열해시맵+2아직 제출이 없습니다20초512 MB채점 가능
FFT 알고리즘m과 k가 주어질 때, m에 대한 원시 2^k승근을 하나 찾거나 존재하지 않으면 -1을 출력한다.어려움9정수론수학+2아직 제출이 없습니다1.5초512 MB채점 가능
Closest Pair Algorithm평면을 무작위 각도로 회전한 뒤 가장 가까운 두 점을 찾는 알고리즘이 거리 함수를 호출하는 횟수의 기댓값을 계산한다.어려움9기하확률+2아직 제출이 없습니다10초512 MB지문만 제공
Interactive Algorithm길이 400 이하의 숨겨진 순열을 최대 25000번의 질의로 알아낸다. 각 질의는 제시한 순열과 숨겨진 순열이 공유하는 인접 무순서 쌍의 개수를 돌려준다.어려움9완전 탐색그래프+2아직 제출이 없습니다5초512 MB지문만 제공
괄호 오일러 투어무방향 그래프에서 각 정점에 괄호가 붙어 있을 때, 방문 순서대로 읽은 괄호열이 올바른 괄호열이 되는 오일러 투어를 찾아 출력하거나 불가능함을 판정한다.어려움9그래프DFS+2아직 제출이 없습니다2초512 MB채점 가능
Find a Tree색수 k인 그래프와 정점 k개짜리 트리가 주어질 때, 트리를 부분그래프로 포함하는 서로 다른 그래프 정점 k개를 찾거나 불가능함을 판별한다.어려움9그래프그리디+2아직 제출이 없습니다4초512 MB지문만 제공
하나의 실근|p|, |q| ≤ m인 정수 쌍 (p, q) 중에서 x^n + px + q가 실근을 정확히 하나 갖는 경우의 수를 센다.어려움9수학정수론+2아직 제출이 없습니다2초512 MB채점 가능
Unfair Card Deck가중 추출 과정에서 얻은 100000개의 카드 뽑기 순서를 보고, 모든 쌍의 비율이 실제 비율과 가깝도록 각 카드 종류의 가중치를 복원한다.어려움9확률수학+2아직 제출이 없습니다2초512 MB지문만 제공
Pick Your Own Nim앨리스가 고른 n개의 더미에 대해, Bob은 m개의 상자에서 각각 더미 하나씩 골라 어떤 비어 있지 않은 부분집합을 잡아도 xor이 0이 되지 않도록 만들어야 한다.어려움9수학비트 연산+2아직 제출이 없습니다2초512 MB지문만 제공
Battle Royale선분 안 고정된 위치에 있는 n명의 플레이어가 매초 줄어드는 안전 구역 밖에서 각각 ai초 버틸 수 있을 때, 구역이 한 점으로 줄어들면 마지막까지 살아남을 확률을 각 플레이어마다 구한다.어려움9수학확률+2아직 제출이 없습니다2초512 MB지문만 제공
The Good, the Bad and the Ugly수직선 위에서 움직이는 세 종류의 플레이어를 판별한다. 매 라운드 + 또는 -를 외치고 위치가 0인지만 들으며 30m 라운드 안에 정체를 밝힌다.어려움9수학정수론+2아직 제출이 없습니다2초512 MB지문만 제공
또 다른 동전 무게 재기 퍼즐저울을 m번 사용하고 각 봉지에 k개의 동전이 있을 때, 무거운 가짜 봉지를 유일하게 가려낼 수 있는 봉지 수의 최댓값을 998244353으로 나눈 나머지로 구한다.어려움9조합론수학+2아직 제출이 없습니다1초512 MB채점 가능
All Kill각 문제의 풀이 아이디어가 균등분포로 임의의 분에 도착할 때, 모든 문제를 연속된 구간으로 끝까지 코딩할 확률을 t^n배 하여 998244353으로 나눈 나머지를 구한다.어려움9확률조합론+2아직 제출이 없습니다1초512 MB지문만 제공
편집 거리 세기주어진 문자열 s와 레벤슈타인 거리가 정확히 d인 'A'부터 'Z'까지의 서로 다른 문자열 개수를 998244353으로 나눈 나머지를 구한다.어려움9동적 계획법문자열+2아직 제출이 없습니다10초512 MB채점 가능
Rooted Subtrees두 루트 r과 p가 주어질 때, r을 루트로 하는 트리의 서브트리와 p를 루트로 하는 트리의 서브트리의 교집합으로 만들 수 있는 서로 다른 공집합이 아닌 집합의 개수를 구한다.어려움9트리DFS+2아직 제출이 없습니다11초512 MB채점 가능
Tomb Raider회전 가능한 두 면 gargoyle이 있는 n×m 거울 미로에서, 모든 gargoyle 면이 빛으로 다른 gargoyle 면과 연결되도록 회전 횟수의 최솟값을 구한다.어려움9그래프DFS+2아직 제출이 없습니다3초512 MB지문만 제공
Associativity Degreen과 여러 k가 주어질 때, 결합 법칙이 성립하는 삼중항의 개수가 정확히 k인 이항 연산을 구성하거나 불가능함을 판정한다.어려움9수학조합론+2아직 제출이 없습니다6초512 MB지문만 제공
Medium Hadron ColliderN-1번의 일관된 게이트 작동 뒤 1번부터 128번 구간의 빔 전하를 알아내야 한다. 129번부터 512번 구간에서 최대 10번 측정할 수 있고, 검출기는 7자리를 넘으면 값을 감싼다.어려움9수학정수론+2아직 제출이 없습니다4초512 MB지문만 제공
기저 변환계수 a_i가 주는 선형 점화식을 만족하는 모든 수열이 함께 만족하는, 지정된 지연 b_i를 갖는 유일한 점화식의 계수를 구한다.어려움9수학구현+2아직 제출이 없습니다2초512 MB채점 가능
Incomparable Pairs문자열 s의 부분 문자열 쌍 중에서 어느 쪽도 다른 쪽을 포함하지 않는 쌍의 개수를 센다.어려움9문자열정렬+2아직 제출이 없습니다3초512 MB지문만 제공
QuoridorASCII 아트로 주어진 육각형 Quoridor 보드에서 플레이어 A가 놓을 수 있는 모든 벽 위치를 세되, 어떤 플레이어든 반대편에 도달하지 못하게 막는 배치는 제외한다.어려움9기하그래프+2아직 제출이 없습니다2초512 MB지문만 제공
Nightmare평면 아래에 있는 다면체 형태의 포트홀들과 직사각형 자동차가 주어질 때, 자동차가 k개를 초과하는 포트홀을 만나기 전까지 이동하는 거리를 구한다.어려움9기하시뮬레이션+2아직 제출이 없습니다1초512 MB지문만 제공
Employees수용 인원이 k인 홀과 한 명만 작업하는 방에서 이루어지는 과정을 두 가지 방식으로 평가한 점수를 모든 순열에 대해 합산하고, 직원별로 두 점수를 곱해 10^9+7로 나눈 값을 구한다.어려움9조합론수학+2아직 제출이 없습니다2초512 MB지문만 제공
모듈로 마방진각 행, 각 열, 두 대각선의 합이 모두 같은 상수와 합동이 되는 Z_m 위의 n x n 행렬의 개수를 n과 m이 10^9까지일 때 센다.어려움9수학조합론+2아직 제출이 없습니다1초512 MB채점 가능
Count the Sequences0 ≤ x_i ≤ b^i - c이고 합이 n보다 작은 정수 수열 x_1, ..., x_m의 개수를 998244353으로 나눈 나머지로 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다1초512 MB지문만 제공
네가 원하는 대로 불러주어진 n마다 x^n - 1을 정수 계수에서 사이클로토믹 다항식들의 곱으로 인수분해하고, 정해진 계수 순서와 부호 및 지수 표기 규칙에 맞춰 출력한다.어려움9정수론수학+2아직 제출이 없습니다2초512 MB채점 가능
Innocence길이 N인 배열의 각 원소가 [L, R] 범위에 있고 전체 XOR이 K가 되는 경우의 수를 여러 K에 대해 1e9+7로 나눈 나머지로 구한다.어려움9수학동적 계획법+2아직 제출이 없습니다1초512 MB지문만 제공
만화경마름모 육십면체의 60개 면을 n가지 색으로 칠하되 각 색 i를 최소 c_i번 사용하고, 회전 대칭으로 같은 색칠은 동일하게 볼 때 경우의 수를 p로 나눈 나머지를 구한다.어려움9조합론수학+2아직 제출이 없습니다2초512 MB채점 가능
Lost In The Echon개의 서로 다른 변수에 사칙연산과 괄호를 써서 만들 수 있는 유리식의 개수를, 유리함수로서 같은 것을 하나로 세어 1e9+7로 나눈 나머지를 구한다.어려움9조합론수학+2아직 제출이 없습니다8초512 MB지문만 제공
Alien Invasion꼭짓점이 순서대로 번호가 매겨진 미지의 다각형에서 일부 꼭짓점을 골라 그 볼록 껍질의 넓이를 되돌려받으며 다각형 전체의 넓이를 알아내는 인터랙티브 문제이다.어려움9기하이분 탐색+2아직 제출이 없습니다3초512 MB지문만 제공
Data Structure Problem2^p 크기 배열에서 점 갱신과 구간 합 질의를 처리하면서, 주어진 k와의 비트 AND, OR, XOR로 인덱스를 재배열하는 전역 변환까지 수행한다.어려움9세그먼트 트리비트 연산+2아직 제출이 없습니다8초512 MB지문만 제공
기댓값 비용n개 정점의 레이블 트리를 균일하게 무작위로 고를 때, 한 정점에서 다른 모든 정점까지 거리 합의 최솟값에 대한 기댓값을 소수 모듈로로 구한다.어려움9조합론트리+2아직 제출이 없습니다3초512 MB채점 가능
Fractional XOR Maximization두 실수의 비트 XOR을 스케일된 정수 내림의 극한으로 정의할 때, 두 유리수 구간에서 각각 원소를 골라 얻을 수 있는 XOR 값의 최소 상계를 구한다.어려움9비트 연산수학+2아직 제출이 없습니다2초512 MB지문만 제공
Jimp Numbers등차수열을 이루는 양의 정수 (a, b, c)에 대해 a^2 + b^2 + k = c^2을 만족하는 삼중항이 정확히 하나 존재하는 k의 개수를 n 이하에서 센다.어려움9정수론수학+2아직 제출이 없습니다2초512 MB지문만 제공
긴 게임순열을 담은 막대를 번갈아 자르되, 자른 뒤에도 역전 쌍을 가진 막대가 하나 이상 남아야 한다. 최적으로 둘 때 승자를 가린다.어려움9게임 이론그리디+2아직 제출이 없습니다1초512 MB채점 가능
Salty Fish도둑이 각 카메라의 감시 범위에서 사과를 훔칠 때, 잠글 카메라를 골라 비용을 지불하고 남는 이익이 최대가 되도록 하는 문제입니다.어려움9트리그리디+2아직 제출이 없습니다3초512 MB지문만 제공
Faraway최대 10개의 조건 각각에 대해 (|xi - xe| + |yi - ye|) mod ki = ti를 만족하는 격자점 (xe, ye)가 [0, m]^2 안에 몇 개인지 세는 문제다. ki는 5 이하이고 m은 1e9까지 커질 수 있다.어려움9수학정수론+2아직 제출이 없습니다1초512 MB채점 가능
TDLm과 k가 주어질 때, n보다 큰 수 중 n과 서로소인 m번째 정수에서 n을 뺀 값을 n과 XOR한 결과가 k가 되는 가장 작은 n을 찾는다.어려움9정수론비트 연산+2아직 제출이 없습니다1초512 MB채점 가능
Road Manager원형 격자에서 연속한 열 구간을 지운 뒤 남는 그래프의 최소 신장 트리 가중치를 각 질의마다 구한다. 간선 가중치는 주어진 난수 생성기로 만든다.어려움9최소 신장 트리그래프+2아직 제출이 없습니다4초512 MB지문만 제공
Monster Hunter1번을 루트로 하는 트리에서 각 정점에 소모 HP와 회복 HP가 주어질 때, 모든 몬스터를 처치하는 동안 HP가 음수가 되지 않도록 하는 최소 초기 HP를 구한다.어려움9그리디DFS+2아직 제출이 없습니다4초512 MB채점 가능
Minimum Spanning Trees각 정점 쌍이 독립적으로 간선이 없거나 1부터 k까지의 가중치를 확률적으로 가질 때, 그래프가 연결되어 있고 최소 신장 트리의 가중치가 주어진 s가 될 확률을 모든 s에 대해 구한다.어려움9조합론그래프+2아직 제출이 없습니다4초512 MB지문만 제공
Line Graphs단순 무방향 그래프 G와 1 이상 4 이하의 k가 주어질 때, k번 반복한 선 그래프 L^k(G)의 최대 클리크 크기와 최대 클리크의 개수를 10억 7로 나눈 나머지를 구한다.어려움9그래프조합론+2아직 제출이 없습니다5초512 MB지문만 제공
Play Games with Rounddog각 부분 문자열 질의마다 그 문자열로 끝나는 부분 문자열을 골라 등장 횟수 p에 대해 W[p]개의 돌 더미로 만들 때, Nim에서 이기면서 만들 수 있는 돌의 최대 총합을 구한다.어려움9문자열게임 이론+2아직 제출이 없습니다5초512 MB지문만 제공
Dense Subgraph차수가 5 이하인 트리에서, L 안에서 밀도가 최대인 연결 부분그래프의 밀도가 x 이하가 되는 부분집합 L의 개수를 세어 1e9+7로 나눈 나머지를 구한다.어려움9동적 계획법트리+2아직 제출이 없습니다3초512 MB지문만 제공
Closest Pair of Segments서로 만나지 않는 n개의 선분이 주어질 때, 서로 다른 두 선분 위의 점 사이 거리의 최솟값을 구한다.어려움9기하분할 정복+2아직 제출이 없습니다12초512 MB지문만 제공
Rounddog를 행복하게 만들기원소가 모두 서로 다르고 최댓값에서 길이를 뺀 값이 k 이하인 부분 배열의 개수를 센다. 배열 길이는 최대 300,000이고 원소는 1 이상 n 이하다.어려움9분할 정복투 포인터+2아직 제출이 없습니다2초512 MB채점 가능
Yet Another Convolutionk가 1부터 n까지일 때 gcd(i, j) = k인 모든 쌍에 대해 |a_i - b_j|의 최댓값을 구해 출력한다.어려움9정수론수학+2아직 제출이 없습니다4초512 MB지문만 제공
소수 전개무한곱 (9/10)(99/100)(999/1000)...의 값을 소수로 나타냈을 때 n번째 자리 숫자를 n이 10^18까지인 각 질의마다 구한다.어려움9수학정수론+2아직 제출이 없습니다1초512 MB채점 가능
Defying Gravity극좌표로 주어진 위성들에 대해, 전체 중력이 항상 위치 벡터와 나란해지는 원점 출발 직선 방향을 모두 구한다.어려움9기하수학+2아직 제출이 없습니다2초512 MB지문만 제공
From Modular to Rationalp, q가 각각 10^9 이하인 숨은 유리수 p/q를 알아내야 한다. 10^9보다 큰 소수 m을 골라 p·q^(-1) mod m을 묻는 질의를 10번까지 할 수 있다.어려움9정수론수학+2아직 제출이 없습니다20초256 MB지문만 제공
Tree Automorphisms정점 n개짜리 트리가 주어질 때, 합성으로 트리의 모든 자기동형사상을 만들어 내는 n개 미만의 순열 집합을 출력한다.어려움9트리DFS+2아직 제출이 없습니다1초512 MB지문만 제공
Bulbasaur층마다 k개의 구멍이 있는 방향 그래프에서 모든 층 쌍에 대해 서로 정점과 간선을 겹치지 않게 보낼 수 있는 최대 덩굴 수의 합을 구한다.어려움9그래프동적 계획법+2아직 제출이 없습니다6초512 MB지문만 제공
Eevee여러 순열을 교차 병합해 같은 돌이 k개 연속으로 나오지 않게 만드는 경우의 수를 모든 연속한 스택 구간에 대해 합해 1e9+7로 나눈 나머지를 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다5초512 MB지문만 제공
Lati@sn x n 행렬의 모든 순열 대각선으로 시작 멀티셋을 만든 유한 게임에서 최적 플레이 시 승자를 판정한다.어려움9게임 이론조합론+2아직 제출이 없습니다2초512 MB채점 가능
Goldberg Machine각 노드가 이웃을 순환하며 구슬을 보내는 트리에서, 일부 노드의 활성 간선을 바꾸는 갱신과 x걸음 뒤 구슬의 위치를 묻는 질의를 처리한다.어려움9트리이분 탐색+1아직 제출이 없습니다5초512 MB지문만 제공
Lowest Unique과반수 이상의 플레이어를 조종해, 고정 전략을 쓰는 상대를 상대로 각 라운드에서 가장 낮은 고유 정수를 낸 플레이어가 이기는 게임에서 90% 이상의 라운드를 이겨야 한다.어려움9게임 이론그리디+1아직 제출이 없습니다2초512 MB지문만 제공
선형 합동 생성기선형 합동 생성기와 두 인덱스 구간이 주어질 때, 첫 구간의 i와 둘째 구간의 j에 대한 X_i mod (X_j+1)의 합을 구한다.어려움9수학정수론+2아직 제출이 없습니다2초512 MB채점 가능