문제

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

전체 결과문제 1545개

제목	난이도	유형	정답자	시간 제한	메모리 제한	채점
달나라에 사는 토끼와 우주에서 떨어지는 떡각 정점에서 나가는 간선이 하나뿐인 그래프에서 떡이 떨어질 때마다 토끼들이 최단 경로로 이동한 뒤, 토끼마다 점프한 총 횟수를 구한다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
Longest Shortest Paths서로 겹치지 않는 축에 평행한 직사각형들과 두 수직 선분 S, T가 주어질 때, 모든 점 쌍에 대한 최단 장애물 회피 경로 길이의 최댓값을 구한다.	어려움9	기하최단 경로+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Dungeon Crawler가중치 트리에서 각 질의 (출발, 열쇠, 함정)마다 열쇠를 먼저 얻고 함정 방에 들어가기 전에 모든 방을 방문하는 최소 시간을 구한다.	어려움9	트리DFS+2	아직 제출이 없습니다	5초	1024 MB	지문만 제공
Guardians of the Gallery단순 다각형 내부에서 경비원이 원형 조각의 절반 이상을 볼 수 있는 지점까지 이동하는 최단 경로 길이를 구한다.	어려움9	기하최단 경로+1	아직 제출이 없습니다	5초	1024 MB	지문만 제공
Grapevine가중치를 바꿀 수 있는 트리에서 노드의 포도를 켜고 끄며, 각 질의마다 가장 가까운 포도까지의 거리를 구한다.	어려움9	트리세그먼트 트리+2	아직 제출이 없습니다	3초	1024 MB	지문만 제공
Bog of Eternal Stench가중치가 있고 0 아래로 내려가지 않는 스텐치를 다루며, 노드 1에서 n까지 갈 때 사이클과 재방문을 허용하는 방향 그래프에서 최소 최종 스텐치를 구한다. 최종 스텐치는 음수가 될 수 없다. 가중치와 노드 수는 최대 2,000이다. 음수 간선이 있으므로 벨만-포드류 완화를 사용한다. 답은 0 이상이다. 목적지에 도달하는 것은 보장된다. 목적지에 도달한 후에도 추가 이동이 가능하다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	3초	1024 MB	지문만 제공
Dijkstra's Nightmare (Hard)주어진 p마다 참조용 다익스트라 변형이 정확히 p개의 정점을 처리한 뒤 종료하는, 정점 60개 이하의 방향 가중 그래프를 만든다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	60초	1024 MB	지문만 제공
Emacs++괄호 문자열의 각 위치마다 왼쪽·오른쪽 이동 비용과 짝 괄호로 순간이동하는 비용이 주어질 때, 여러 질의의 두 위치 사이 최단 시간을 각각 구해 모두 더한다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	60초	1024 MB	지문만 제공
Shortest Path QueryDAG의 검은 간선과 흰 간선에 각각 a와 b의 가중치를 주고, 정점 1에서 정점 x까지의 최단 거리를 각 질의마다 구한다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
황혼가중치가 있는 방향 그래프와 서로 겹치지 않는 K개의 금지된 단순 경로가 주어질 때, 각 도시까지 금지 경로를 연속 구간으로 포함하지 않는 최단 경로의 시간을 모두 구한다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	4초	1024 MB	지문만 제공
Путешествие по островам서로 겹치지 않는 n개의 볼록 다각형(섬)이 주어질 때, 섬 a에서 b로 이동하는 데 필요한 최소 비행 거리를 구한다. 섬 위에서는 걸어서 자유롭게 이동할 수 있다.	어려움9	기하그래프+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Zany and Zealous yclock고정된 서울 지하철 1호선부터 9호선 노선도에서 환승이 금지된 역 집합이 주어질 때 두 역 사이 최소 이동 시간과 경로를 각 쿼리마다 구한다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	1.5초	1024 MB	지문만 제공
지름길 건설길이가 양 끝 마을에 직접 연결된 도로 중 최솟값 이하이고 각 마을에서 가장 가까운 중심 마을까지의 거리를 바꾸지 않는 지름길의 최대 개수를 구한다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	3초	1024 MB	지문만 제공
Sleeping Chameleons1번 카멜레온에서 시작해, 깨어난 카멜레온은 1초에 대각선 포함 한 칸씩 이동하거나 다른 색 카멜레온에게 같은 행 또는 열로 즉시 혀를 뻗을 수 있을 때, N번 카멜레온을 깨우는 최소 시간을 구한다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
제우스Treewidth가 2 이하인 가중 연결 그래프가 주어질 때 모든 정점 쌍의 최단 경로 길이 합을 구한다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	12초	1024 MB	지문만 제공
Quadratic Integer Program각 변수를 자기 구간의 값으로 정하되 짝별 절대값 차 제한을 지키며 여러 질의에서 가중치를 받는 값별 개수의 최댓값을 구합니다.	어려움9	동적 계획법최단 경로+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Trade도시들이 완전 이진 트리와 추가 간선으로 이루어질 때 모든 순서쌍의 최단 거리 합을 998244353으로 나눈 나머지를 구한다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	1.5초	1024 MB	지문만 제공
Two avenues무방향 연결 그래프에서 두 간선을 유료 도로로 지정해 k개의 출발-도착 쌍에 대한 최단 경로 비용 합이 최대가 되도록 하는 문제.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	6초	1024 MB	지문만 제공
Air Reform베를라플로트의 각 간선에 대해, 원래 그래프의 minimax 거리로 가중치가 정해진 여객 그래프에서 두 끝점 사이의 minimax 거리를 구한다.	어려움9	그래프최소 신장 트리+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
외판원 순회 로봇외판원과 그가 들고 다니거나 내려놓을 수 있는 로봇이 방향 그래프의 모든 도시를 함께 방문해야 하며, 두 이동 속도가 다를 때 순회를 마치는 최소 시간을 구한다.	어려움9	동적 계획법비트 연산+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
활자 그래프이전에 만든 활자 그래프를 붙여서 정의되는 그래프에서 1번 정점에서 2번 정점으로 가는 최단 경로를 구한다. 붙인 그래프는 가중치가 있는 간선처럼 동작한다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	1.5초	1024 MB	지문만 제공
City Brain무향 그래프의 간선 속도를 k달러로 높여 두 사람의 최단 경로 이동 시간 합을 최소로 만든다.	어려움9	최단 경로그리디+2	아직 제출이 없습니다	4초	1024 MB	지문만 제공
혼합 정수 이차 계획법각 간선의 비용이 ax^2 + bx인 그래프에서 1번 정점에서 n번 정점까지 최대 유량을 보내면서 최소 비용을 구한다. a가 0이 아닌 간선은 최대 100개다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	3초	1024 MB	지문만 제공
Two PathsDAG와 두 정점 쌍이 주어질 때, 각 쌍을 잇는 간선 비공유 단순 경로 중 총 길이가 최소인 쌍을 찾는다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	5초	1024 MB	지문만 제공
바이러스가중 트리에서 각 사람이 반지름 D[j]의 영역을 오가며, 공유 지점의 최소 전파 시간을 매개로 0번 사람부터 감염 시각을 계산한다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	4초	1024 MB	지문만 제공
Board Game각 목표 칸마다 플레이어 1의 말이 그 칸에 도달할 때까지 K명이 움직인 총 이동 횟수의 최솟값을 구한다. 0인 칸에 서면 한 번 더 움직여야 한다.	어려움9	그래프BFS+2	아직 제출이 없습니다	4초	1024 MB	지문만 제공
돈 복사돈과 물건 사이의 교환 거래 목록이 주어질 때, 돈을 무한히 늘릴 수 있게 되는 최소 초기 자금을 구하고 그런 자금이 없으면 INF를 출력한다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Blocking the Way타일 조각이 왼쪽 위에서 오른쪽 아래로 이동하지 못하도록 막는 데 필요한 최소 비용을 구한다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	8초	1024 MB	지문만 제공
가중치 복사 버그각 간선을 지날 때마다 모든 간선의 가중치가 지나간 간선의 가중치만큼 증가하는 0/1 그래프에서 s에서 e까지의 최소 경로 길이를 구해 이진수로 출력한다.	어려움9	최단 경로BFS+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Treasure Hunt각 정점에 값이 있는 가중 무방향 그래프에서 모든 시작 정점마다 (도착 정점의 값 - 경로 비용)의 최댓값을 구한다.	어려움9	최단 경로그래프+2	아직 제출이 없습니다	4초	1024 MB	지문만 제공
Cross Countryn개의 선분 검문소를 1번부터 n번까지 순서대로 통과하면서 시작점에서 도착점까지 가는 최단 경로의 길이를 구한다.	어려움9	기하동적 계획법+2	아직 제출이 없습니다	10초	1024 MB	지문만 제공
Pigpartite Giraffe돼지와 기린이 이루는 이분 그래프에서 새 동물은 두 부모의 이웃 집합 대칭차에 연결되며, 각 출생 후 모든 쌍의 최단 거리 합을 출력한다.	어려움9	그래프비트 연산+2	아직 제출이 없습니다	5초	1024 MB	지문만 제공
Grand Glory Race가중 트리에서 각 질의 (잎 S, 결승 T)마다 S에서 출발한 주자가 다른 모든 잎 주자보다 먼저 도달하는 마을 수를 구한다.	어려움9	트리최단 경로+2	아직 제출이 없습니다	1초	2048 MB	지문만 제공
Photo Op출발 시각마다 (X,0)에서 (0,Y)까지, 그 시각까지 나타난 선분들을 피하는 최단 경로의 길이를 구한다.	어려움9	기하최단 경로+2	아직 제출이 없습니다	2초	2048 MB	지문만 제공
도로 공사각 도로의 길이를 [L_i, R_i] 범위의 정수로 정해, 1번에서 i번까지 최단 거리가 정확히 D_i가 되는 경우의 수를 센다.	어려움9	최단 경로그리디+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Pinball블록 벽과 비스듬한 거울이 있는 격자에서 공을 밀어 보내며, 원하는 시각에 거울을 부수어 공이 격자 밖으로 나가게 하는 최소 파괴 횟수를 구한다.	어려움9	시뮬레이션그래프+2	아직 제출이 없습니다	5초	2048 MB	지문만 제공
Home Sweet Home가중치 0 이상 K 이하의 간선 (u,v) 중 기존에 없고, 추가해도 어떤 정점에서 1번까지의 최단거리도 줄어들지 않는 쌍의 개수를 센다.	어려움9	최단 경로그래프+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
e-코너 시스템 테스트 (Hard)격자에서 (1,1)에서 (N,N)까지 최단 경로를 찾되 방향이 바뀌는 횟수를 최대로 하여, 총 거리와 피봇턴 횟수를 출력한다.	어려움9	최단 경로동적 계획법+2	아직 제출이 없습니다	1초	512 MB	지문만 제공
Bitaro’s Travel 2격자 위 산 높이와 점프 길이 L이 주어질 때, 두 칸 사이를 최소 몇 번의 하이 점프로 이동할 수 있는지 구하고 불가능하면 -1을 출력한다.	어려움9	그래프BFS+2	아직 제출이 없습니다	4초	2048 MB	지문만 제공
Most Scenic Cycle강하게 연결된 다중 그래프에서 각 간선에 가중치가 주어질 때 최대 가중치를 갖는 단순 사이클을 구한다.	어려움9	그래프동적 계획법+2	아직 제출이 없습니다	7초	2048 MB	지문만 제공
Lava Moat꼭짓점 높이가 모두 다르고 삼각형마다 선형 보간으로 높이가 정해진 삼각분할 직사각형에서, 서쪽 경계와 동쪽 경계를 잇는 가장 짧은 등고선 경로의 길이를 구하거나 불가능을 판정한다.	어려움9	기하그래프+2	아직 제출이 없습니다	4초	2048 MB	지문만 제공
Hold the Star각 캐릭터의 시작 방과 이동 비용이 주어질 때, 별의 시작 방마다 캐릭터 m이 별을 들도록 만드는 최소 비용을 구한다.	어려움9	최단 경로동적 계획법+2	아직 제출이 없습니다	2초	2048 MB	지문만 제공
초콜릿 먹기방향을 바꿀 때마다 도착 칸의 B를 곱한 개수만큼 초콜릿을 먹게 될 때, 시작점에서 도착점까지 총 당도가 최소인 경로를 찾는다.	어려움9	최단 경로그리디+2	아직 제출이 없습니다	3초	1024 MB	지문만 제공
Clique Festival서로 다른 가중치를 가진 k개의 클리크 간선 추가가 주어질 때, 모든 정점 쌍의 최단 경로 거리 합을 구한다.	어려움10	그래프최단 경로+2	아직 제출이 없습니다	2초	512 MB	지문만 제공
A Very Long Hiken x n 고도 행렬이 평면을 주기적으로 채울 때, 한 걸음 비용이 1에 고도 차를 더한 값일 때 1e20초 안에 도달할 수 있는 서로 다른 격자점의 수를 센다.	어려움10	그래프최단 경로+2	아직 제출이 없습니다	6초	2048 MB	지문만 제공