cho.sh

문제

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

전체 결과문제 32797개
제목난이도유형정답자시간 제한메모리 제한채점
피아의 아틀리에: 신비한 생명의 연금술사n x n 이진 격자에 모든 2x2 부분합의 패리티가 주어진 값과 같아야 하고, 각 날짜에 활성화된 셀 고정 조건을 모두 만족하는 배치가 존재하는지 판정한다.어려움9유니온 파인드누적 합+2아직 제출이 없습니다2초512 MB채점 가능
부스터걷기는 체력을 소모하고 부스터는 축 방향으로만 이동할 수 있다는 규칙에서, 체력 한계 X로 체크포인트 A에서 B로 갈 수 있는지 각 질의마다 판정한다.어려움9그래프유니온 파인드+2아직 제출이 없습니다8초512 MB채점 가능
숏코딩비교식들을 &&로 이은 조건문이 주어질 때, 이와 동치이면서 가장 짧은 조건문을 출력한다.어려움9문자열구현+2아직 제출이 없습니다4초512 MB지문만 제공
공룡 발자국N개의 점이 주어질 때, 유일한 최남단 점을 발뒤꿈치로 하고 좌회전과 우회전이 번갈아 나타나며 발가락 선분이 다각형 안에 있고 골을 지나지 않는 조건을 만족하는 발자국 중 발가락이 가장 많은 것을 찾는다. 가장 남쪽 점에서 시작해 반시계 방향으로 정렬한 점들 가운데, 각도 순서를 유지하면서 좌회전과 우회전이 교대로 나타나는 최장 부분수열을 구하는 문제로 바꿀 수 있다. 부분수열의 길이가 홀수여야 발가락이 정수 개가 되고, 마지막 점에서 발뒤꿈치로 돌아올 때의 회전 방향과 골을 지나지 않는 조건도 확인해야 한다. 서브태스크에 따라 N이 커지므로, 회전 방향을 기준으로 나눈 두 개의 최장 증가 부분수열을 O(N log N)에 계산하고, 발가락 선분이 다각형을 벗어나거나 골을 지나지 않는지 기하학적으로 검사하는 과정이 필요하다. 좌표 범위는 -10^8 이상 10^8 이하이고, 모든 점은 서로 다르며 y좌표가 가장 작은 점이 유일하다. 정답이 여러 개면 아무거나 출력하고, 발자국이 존재하지 않으면 0을 출력한다.어려움9기하정렬+2아직 제출이 없습니다2초512 MB지문만 제공
국제 소 줄서기 사진 콘테스트0과 1로 이루어진 배열에서 인접한 두 원소를 바꾸는 연산이 최대 10만 번 주어질 때, 각 연산 직후 0과 1의 개수가 같은 가장 긴 연속 구간의 길이를 구한다.어려움9세그먼트 트리누적 합+2아직 제출이 없습니다2초512 MB채점 가능
팀 빌딩원소를 합치는 연산, P로 나눈 나머지를 기준으로 팀을 나누는 연산, 팀 크기 질의를 최대 10만 개의 명령에 대해 처리한다.어려움9유니온 파인드구현+1아직 제출이 없습니다1초512 MB채점 가능
뒤집기한 칸을 누르면 그 칸이 속한 단색 연결 성분 전체의 색이 뒤집힐 때, 주어진 격자 상태에 도달할 수 있는 초기 상태의 가짓수를 10⁹+7로 나눈 나머지로 구한다.어려움9그래프유니온 파인드+2아직 제출이 없습니다5초256 MB채점 가능
클라우드 컴퓨팅수락한 주문마다 최소 클록 속도를 만족하는 코어를 충분히 공급하도록 주문과 컴퓨터 구매 집합을 골라, 고객 지불액에서 구매 비용을 뺀 값을 최대로 만든다.어려움9동적 계획법그리디+2아직 제출이 없습니다2초512 MB채점 가능
Fibonacci representations각 접두사에 대해 대응하는 피보나치 수의 합을 구하고, 그 합을 서로 다른 피보나치 수의 합으로 나타내는 방법의 수를 10^9+7로 나눈 나머지를 출력한다.어려움9동적 계획법조합론+2아직 제출이 없습니다2초512 MB지문만 제공
Expression Mining주어진 산술식 문자열에서 문법(숫자, +, *, 괄호)에 맞게 해석되고 값이 n인 부분 문자열의 개수를 센다.어려움9분할 정복동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
Winter Festival각 간선에 비용 0, 1, 2 중 하나를 부여해 인접한 두 간선의 합이 3으로 나눈 나머지가 1이 되지 않고 모든 사이클의 비용 합이 홀수가 되도록 하며, 불가능하면 -1을 출력한다.어려움9그래프수학+1아직 제출이 없습니다5초512 MB지문만 제공
Buildingsn×n 색칠 정사각형 벽 m개를 정m각형 둘레에 배치해 만들 수 있는 집의 개수를 회전을 같게 보아 세고, 10^9+7로 나눈 나머지를 구한다.어려움9조합론수학+2아직 제출이 없습니다2초512 MB채점 가능
Ratatöskr나무 위에서 두 까마귀가 다람쥐를 잡으려 한다. 다람쥐는 매 턴 까마귀가 있는 노드를 지나지 않고 이동하며, 최소 몇 번의 신호로 반드시 잡을 수 있는지, 불가능하면 impossible을 출력한다.어려움9게임 이론그래프+2아직 제출이 없습니다2초512 MB지문만 제공
미생물 키우기구매 비용과 생산 비용이 주어질 때 미생물을 사고 각 종이 다른 종을 생산하게 해 종마다 x_i개를 만드는 최소 비용을 구한다.어려움9수학그리디+2아직 제출이 없습니다2초512 MB채점 가능
별자리2e5개 이하의 점 중에서, 어떤 점을 원점으로 잡아도 나머지 점이 모두 제1사분면이나 제3사분면에 있고 각 사분면에서 가장 가까운 점이 L 이내가 되도록 부분집합을 골라 밝기 합의 최댓값을 구한다.어려움9수학기하+2아직 제출이 없습니다1.5초512 MB채점 가능
#15164번_제보주어진 대문자 문자열에서 회문인 부분 문자열의 개수를 위치별로 모두 세어 출력합니다.어려움9문자열문자열 매칭+2아직 제출이 없습니다1초512 MB지문만 제공
Möbius Madness1부터 N까지의 d에 대해 mu(L·d)와 floor(N/d)^K의 곱을 모두 더한 값을 10^9+7로 나눈 나머지를 구한다. N이 최대 10^9, L이 최대 10^15라서 L을 소인수별로 쪼개고 floor(N/d)가 같은 구간을 묶어 계산해야 한다.어려움9정수론수학+2아직 제출이 없습니다2.5초512 MB지문만 제공
Histogram Sequence히스토그램에서 모든 연속한 막대 구간의 최대 직사각형 넓이를 모아 정렬했을 때, L번째부터 R번째까지의 값을 출력한다.어려움9스택이분 탐색+2아직 제출이 없습니다2초1024 MB지문만 제공
N과 MN, N^N, N^{N^N}, ... 거듭제곱 탑을 M으로 나눈 나머지가 나중에 고정된 값을 구합니다. N과 M은 10^9 이하입니다.어려움9수학정수론+1아직 제출이 없습니다1초1024 MB채점 가능
옥토끼나라그래프에서 감염 정점 K개와 임계값 T가 주어집니다. 한 정점과 인접 간선을 제거한 뒤 감염 정점이 T개 이상인 연결 성분의 모든 정점이 감염될 때, 정점마다 남는 비감염 정점 수를 구합니다.어려움9트리DFS+2아직 제출이 없습니다1초1024 MB채점 가능
정렬하기매번 한 번의 교환으로 갱신되는 순열마다, 에르맥이 버티는 가운데 아이잔이 수열을 정렬시키는 데 필요한 최소 라운드 수를 구하고, 영원히 정렬할 수 없으면 -1을 출력한다.어려움9조합론수학+2아직 제출이 없습니다1초1024 MB지문만 제공
LISA문자열 s1..sn과 구간 질의 [l,r]이 주어질 때, 구간 안의 두 문자열 sx의 비어 있지 않은 접두사와 sy의 비어 있지 않은 접미사를 이어 붙여 만들 수 있는 서로 다른 문자열의 개수를 센다.어려움9문자열트라이+2아직 제출이 없습니다3초512 MB지문만 제공
위성반원 행성 위에 위성이 추가·삭제될 때, 두 위성의 커버 영역이 행성 밖에서 겹치면서 다른 살아 있는 위성의 커버 영역에 들어가지 않는 지점이 있는지 판정한다.어려움9기하동적 계획법+2아직 제출이 없습니다4초512 MB채점 가능
블랙 체인n개(최대 10^18)의 고리로 된 사슬에서 몇 개의 고리를 열어야 남은 조각을 조합해 1g부터 ng까지의 모든 무게를 만들 수 있는지 구합니다.어려움9그리디조합론+2아직 제출이 없습니다0.1초512 MB채점 가능
침공이 일어난다면, 제발...도로로 이어진 n개 지점의 사람들을 용량이 제한된 최대 10개의 대피소로 보내는데, 모두가 도착하는 최대 시간을 최소로 만듭니다.어려움9이분 탐색BFS+2아직 제출이 없습니다3.5초512 MB채점 가능
배달 지연모든 교차점 쌍의 최단 거리를 구한 뒤 배달 순서 부분집합을 상태로 하는 동적 계획법으로, 주문 시간부터 배달까지의 최대 대기 시간을 최소로 만드는 배달 계획을 찾는다.어려움9최단 경로동적 계획법+2아직 제출이 없습니다5초512 MB채점 가능
에스컬레이터트리 위에서 서로 쌍으로 겹치지 않는 경로를 선택하고 경로마다 시작 값과 도착 값의 보수를 더해 최댓값을 구합니다.어려움9트리동적 계획법+2아직 제출이 없습니다3초512 MB채점 가능
Prime Tree - 2트리의 각 정점에 1부터 n까지의 번호를 다시 붙여, 두 끝점의 번호가 1보다 큰 공약수를 가지는 간선의 수를 최소로 만드는 출력 전용 문제이다.어려움9정수론트리+2아직 제출이 없습니다10초512 MB채점 가능
프라임 트리 - 4각 트리의 정점에 1부터 n까지의 서로 다른 정수를 붙여 공약수가 1보다 큰 간선의 수를 최소화합니다.어려움9그리디정수론+2아직 제출이 없습니다10초512 MB채점 가능
소수 트리 - 6트리 꼭짓점에 1부터 n까지의 서로 다른 수를 배정하여 공약수가 1보다 큰 두 끝점을 잇는 나쁜 간 개수를 최소화합니다.어려움9그래프그리디+2아직 제출이 없습니다10초512 MB채점 가능
Prime Tree - 7주어진 트리의 각 정점에 1부터 n까지의 번호를 다시 붙여, 두 끝점이 1보다 큰 공약수를 갖는 간선의 수가 최소가 되도록 만든 답안 파일을 제출한다.어려움9그리디정수론+2아직 제출이 없습니다10초512 MB채점 가능
Prime Tree - 9주어진 트리의 정점에 새 번호를 붙여, 두 끝점이 1보다 큰 공약수를 갖는 간선의 수를 최소로 만든다.어려움9그래프그리디+2아직 제출이 없습니다10초512 MB채점 가능
Prime Tree - 10주어진 트리의 정점에 1부터 n까지의 번호를 다시 붙여, 두 끝점의 번호가 1보다 큰 공약수를 가지는 간선의 수를 최소로 만드는 출력 전용 최적화 문제다.어려움9정수론그리디+2아직 제출이 없습니다10초512 MB채점 가능
게임선수의 수동 제거 순서를 정할 때 인접한 같은 숫자가 사슬처럼 합쳐지는 연쇄 소거를 최대화하여 자동으로 없어지는 공의 수를 출력합니다.어려움9동적 계획법스택+2아직 제출이 없습니다2초512 MB채점 가능
Shopping각 상품 가격에 정수 배수를 붙여 부호 있는 합이 n이 되게 하고, 그 배수를 100개 이하의 인수 곱으로 출력한다.어려움9정수론수학아직 제출이 없습니다2초512 MB지문만 제공
Superstition가중 무방향 그래프에서 총 이동 시간이 K 이하이면서 D로 나누어떨어지는 경로의 수를 1,000,000,007로 나눈 나머지를 구한다.어려움9그래프행렬+2아직 제출이 없습니다2초512 MB지문만 제공
Crypto1부터 N의 순열에서 길이가 K 이상인 연속 구간마다 가장 작은 K개 값을 곱한 결과가 서로 P개가 되는 순열 개수를 구합니다.어려움9조합론정수론+2아직 제출이 없습니다2초512 MB채점 가능
홀수 색칠색칠 결과가 각 행과 열의 검은 공 개수를 홀수로 만들도록 칠하는 방법 수를 세어서 998244353로 나눈 값을 구합니다.어려움9수학조합론+2아직 제출이 없습니다1초256 MB채점 가능
사전순으로 가장 작은 부호 수열일부 자리가 -1 또는 1로 고정된 길이 N의 부호 수열에서 각 구간 [Ai,Bi]의 합이 Ci 이상이 되도록 채우고, 사전순으로 가장 작은 수열을 출력하거나 불가능하면 Impossible을 출력한다.어려움9그리디누적 합+2아직 제출이 없습니다1초512 MB채점 가능
Fastest Speedrunn개의 레벨이 있고, 각 레벨은 아이템 j로 a[i][j]의 시간이 걸리며 j가 클수록 빠르고, 단축 아이템 x[i]를 쓰면 s[i]의 시간이 걸린다. 레벨을 임의 순서로 모두 깰 때 최소 총 시간을 구한다.어려움9동적 계획법그리디+2아직 제출이 없습니다5초512 MB지문만 제공
스키 경로 감시n개 정점의 DAG에서 각 정점의 나가는 경로는 최대 1개이고 도착 정점은 서로 다를 때 m개 등록 경로가 모두 지나는 정점의 최솟값을 구한다.어려움9그래프그리디+2아직 제출이 없습니다2초512 MB채점 가능
장식하는 세제곱러버n^3 길이의 원형 배열에 꾸미기 1부터 n을 배치해 길이 3 구간을 모두 서로 다르게 하며 지치기의 합을 최소화하고, 시작점에서 p번째 조각의 꾸미기를 출력합니다.어려움9조합론수학+2아직 제출이 없습니다1초512 MB채점 가능
Easyn이 10^18 이하로 주어질 때, 뫼비우스 함수와 이분 탐색으로 n번째 제곱ㄴㄴ수를 구한다.어려움9수학정수론+2아직 제출이 없습니다5초512 MB채점 가능
잊혀진 땅트리 정점들을 임의의 집합들로 나누는 모든 분할에 대해, 각 집합의 정점과 그 사이 경로에 나타나는 언어 집합으로 정해지는 난이도의 합을 구한다.어려움9동적 계획법트리+2아직 제출이 없습니다3초512 MB채점 가능
반쪽은 같지 않다s디나르를 n명의 왕비에게 나누되, 어떤 두 사람의 몫도 주어진 두 사람 공정 분배 규칙을 만족하고 전체 합이 s가 되게 해야 한다.어려움9수학그리디+1아직 제출이 없습니다3초512 MB채점 가능
Interval-Free Permutations연속된 정수 집합의 재배열이 되는 길이 2 이상 n-1 이하의 부분 구간이 없는 순열의 개수를 소수 p로 나눈 나머지를 구한다.어려움9조합론동적 계획법아직 제출이 없습니다2초512 MB지문만 제공
Minegraphed정점이 9개 이하인 방향 그래프가 주어질 때, 표시된 칸 사이의 도달 가능성이 그래프와 정확히 일치하는 3차원 블록 세계를 설계하는 문제다.어려움9그래프시뮬레이션+2아직 제출이 없습니다2초512 MB지문만 제공
실시간 내비게이션두 개의 평행한 경로와 N개의 다리로 이루어진 사다리 모양 그래프에서 최단경로 질의와 간선 갱신을 최대 30만 번 처리합니다.어려움9세그먼트 트리최단 경로+2아직 제출이 없습니다2.5초512 MB지문만 제공
카와이강의 다리간선이 추가되고 삭제되는 그래프에서 두 섬 사이 경로의 최대 위험도가 최소가 되는 값을 구하는 질의에 답한다. 위험도는 한 자리 수다.어려움9동적 계획법유니온 파인드+2아직 제출이 없습니다5초512 MB채점 가능
Incredible Hull볼록 위치에 놓인 점들을 이익이 큰 순서대로 주고, 재귀적 분할 규칙을 따라 통로 그래프를 만든 뒤 그 그래프의 최대 클리크를 찾는다.어려움9기하분할 정복+2아직 제출이 없습니다1초512 MB지문만 제공
의약품 수송 2최소 회전 반지름 R을 가진 차량이 후진 없이 두 방향이 정해진 리프트 사이를 이동할 때 최단 경로 길이를 구한다.어려움9기하최단 경로+2아직 제출이 없습니다0.5초256 MB지문만 제공
합동방정식1 이상 p(p-1) 이하의 순서쌍 (a, b) 중에서 a^b ≡ b^a (mod p)인 개수를 세어 10^9+7로 나눈 나머지를 구합니다.어려움9정수론수학+1아직 제출이 없습니다1초256 MB채점 가능
영과일 학회방'X' 기둥을 피하며 격자의 '.' 칸을 1x1과 1x2 타일로 덮을 때 필요한 타일 개수의 최솟값을 구합니다.어려움9그래프DFS+2아직 제출이 없습니다1초256 MB채점 가능
Cineman개 행과 m개 좌석이 주어질 때, 총 k 이하의 편안함을 더해 왼쪽부터 가장 편안한 좌석에 앉는 규칙으로 앉힐 수 있는 최대 관객 수를 구한다.어려움9그리디정렬+1아직 제출이 없습니다2초512 MB지문만 제공
Fair Chocolate-Cutting볼록 다각형을 넓이가 같은 두 부분으로 나누는 직선 자르기의 최소 길이와 최대 길이를 각각 구해 출력한다.어려움9기하이분 탐색+2아직 제출이 없습니다2초512 MB지문만 제공
Ranks이진 행렬이 주어질 때 각 원소를 뒤집었을 때 F2 위에서 계수가 감소하는지, 같은지, 증가하는지를 판별해 출력한다.어려움9수학행렬+2아직 제출이 없습니다3초512 MB지문만 제공
Sunčanje각 직사각형이 앞서 놓인 직사각형들의 합집합에 전혀 가려지지 않아 완전히 노출되는지 판정하는 문제입니다.어려움9세그먼트 트리기하+2아직 제출이 없습니다4초512 MB지문만 제공
Praktični가중 무방향 그래프가 주어질 때, 각 연산이 값 x와 간선 부분집합을 골라 XOR하는 상황에서 모든 단순 사이클의 XOR이 0이 되도록 하는 최소 연산 수와 그 연산들을 출력한다.어려움9그래프DFS+2아직 제출이 없습니다1초512 MB지문만 제공
Colored Tiles 1주어진 1x1, 1x2 타일을 H×W 판에 겹치지 않게 배치해 인접한 타일 색 경계의 점수 합을 최대로 만든다.어려움9동적 계획법백트래킹+2아직 제출이 없습니다1초512 MB지문만 제공
색 타일 2주어진 1×1과 1×2 타일을 H×W 판에 겹치지 않게 배치해 인접한 타일 사이 점수 합이 최대가 되도록 하고, 각 타일의 좌표를 출력한다.어려움9동적 계획법구현+2아직 제출이 없습니다1초512 MB채점 가능
Colored Tiles 3주어진 1x1, 1x2 색 타일을 H×W 판에 겹치지 않게 배치해 이웃한 두 색의 점수 A[j][k] 합이 최대가 되도록 만든다.어려움9동적 계획법구현+2아직 제출이 없습니다1초512 MB지문만 제공
Colored Tiles 4주어진 1x1과 1x2 타일을 H x W 판에 겹치지 않게 배치해 색 쌍마다 정해진 점수의 합이 최대가 되도록 만든다.어려움9동적 계획법구현+2아직 제출이 없습니다1초512 MB지문만 제공
Colored Tiles 5주어진 1x1, 1x2 타일을 HxW 판에 겹치지 않게 배치해 서로 맞닿은 변의 색 쌍 점수 합이 최대가 되도록 만든다.어려움9백트래킹동적 계획법+2아직 제출이 없습니다1초512 MB지문만 제공
Election Campaign트리와 가중치가 있는 M개의 경로가 주어질 때, 서로 정점을 겹치지 않는 경로 집합을 골라 얻을 수 있는 최대 득표를 구한다.어려움9동적 계획법트리+1아직 제출이 없습니다1초256 MB지문만 제공
JOIRIS열 높이가 주어진 보드에서 1xK 조각을 수직 또는 수평으로 놓아 가득 찬 행을 지우며, 10000번 이내에 모든 블록을 제거하는 방법을 찾거나 불가능하면 -1을 출력한다.어려움9그리디시뮬레이션+2아직 제출이 없습니다1초256 MB지문만 제공
Skyscraper서로 다른 N개 건물 높이의 순열 중 인접한 높이 차의 절댓값 합이 L 이하인 것의 개수를 1e9+7로 나눈 나머지를 구한다.어려움9동적 계획법조합론+2아직 제출이 없습니다2초512 MB지문만 제공
Amusement ParkJOI-kun이 각 명소의 게시판에 0 또는 1을 적어 X를 전달하고, IOI-chan은 시작 위치 P에서 이동하며 읽은 값으로 X를 알아내는 두 프로그램을 설계한다.어려움9그래프DFS+1아직 제출이 없습니다2초512 MB지문만 제공
Cats or Dogs트리에서 Q일에 걸쳐 고양이와 강아지를 추가하거나 제거하며, 매 갱신 후 고양이와 강아지가 만나지 못하도록 지워야 하는 간선의 최소 개수를 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다3초512 MB지문만 제공
Fox Observationx좌표와 y좌표가 모두 다른 두 격자점을 축에 평행한 직사각형의 마주 보는 꼭짓점으로 잡아 내부 여우 무게의 합을 넓이로 나눈 값을 최대로 하고, 기약분수로 출력한다.어려움9분할 정복누적 합+2아직 제출이 없습니다2초512 MB지문만 제공
마법 타일 제거x축 위에 놓인 사다리꼴 타일들이 주어질 때, 모든 쌍이 겹치는 타일 집합들로 나누는 최소 개수를 구한다.어려움9그리디기하+2아직 제출이 없습니다2초512 MB채점 가능
블랙 기업모든 간과 한 정점을 공유하는 두 간에서 두 끝점의 크기 관계가 기여도 순서와 일치하도록 양의 급여를 정하고 그 합을 최소화합니다.어려움9그래프위상 정렬+2아직 제출이 없습니다5초512 MB채점 가능
낮은 구간 합 행렬N행 M열 행렬(둘 다 10 이하)에서 최대 K개 원소의 부호를 바꿔 가로 또는 세로 연속 부분합이 모두 S 이하가 되도록 만들 수 있는지 판정한다.어려움9완전 탐색동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
마법 삼각형반시계 방향으로 주어진 최대 100000개의 삼각형에 대해 모든 삼각형의 공통 교집합 넓이를 구한다.어려움9기하분할 정복+2아직 제출이 없습니다2초512 MB채점 가능
Cellular Automaton길이 2^(2w+1)인 이진 규칙 문자열 p 중 s 이상이면서, (w,p) 셀 오토마타에서 1의 개수가 항상 보존되게 하는 사전순 최소 p를 구한다.어려움9수학조합론+2아직 제출이 없습니다1초512 MB지문만 제공
룩, 비숍, 킹, 나이트, 궁전 게임거대한 체스판 위의 체스말 N개를 각자의 이동 규칙에 따라 왼쪽 아래로 옮기고, 더 옮길 말이 없는 사람이 지는 게임에서 이기는 쪽을 구한다.어려움9게임 이론수학+1아직 제출이 없습니다0.5초512 MB지문만 제공
중복 없는 님 게임각 더미에서 같은 개수의 돌을 두 번 이상 제거할 수 없는 변형 님 게임에서, 두 사람이 최선으로 둘 때 승자를 판정한다.어려움9게임 이론동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
소수 제곱 게임두 사람이 번갈아 소수 p와 양의 정수 k를 골라 p^k가 수열의 어떤 수를 나누면 그 수를 모두 p^k로 나누고, 더 고를 p^k가 없는 사람이 진다.어려움9게임 이론정수론+2아직 제출이 없습니다1초512 MB지문만 제공
채석장 게임N개의 채석장 각각은 X부터 시작하는 M개의 연속한 돌무더기로 이루어지고, 한 수에서 한 무더기의 돌을 1개 이상 가져간다. 최적으로 둘 때 승자를 판정한다.어려움9게임 이론수학+2아직 제출이 없습니다2초512 MB채점 가능
mex각 질의 x마다 수열의 모든 원소를 x로 XOR한 뒤 mex(수열에 없는 가장 작은 음이 아닌 정수)를 출력한다.어려움9비트 연산트라이+2아직 제출이 없습니다1초512 MB채점 가능
mex와 쿼리자연수 집합에 구간 추가, 구간 제거, 구간 토글 질의를 최대 100000번 수행하고, 각 질의 뒤에 mex를 출력한다. 값의 범위는 1e18까지다.어려움9세그먼트 트리구간+1아직 제출이 없습니다2초512 MB채점 가능
Unique Cities각 도시에 특산품 종류가 배정된 트리에서, 모든 도시에 대해 그 도시로부터의 거리가 유일한 도시들이 가진 특산품 종류의 수를 구한다.어려움9트리DFS+2아직 제출이 없습니다2초512 MB지문만 제공
XOR 수열2^m개의 질의 값 각각에 대해 XOR이 최대가 되는 번호를 정한 배열이 주어질 때, 이를 만들어 내는 서로 다른 m비트 정수 n개의 순서 있는 배열의 개수를 10^9+7로 나눈 나머지로 센다.어려움9비트 연산분할 정복+2아직 제출이 없습니다2초512 MB채점 가능
무리오 카트숲의 각 트리를 X 길이의 간선으로 이어 붙이고 트리마다 내부 경로를 하나씩 골라 만든 단순 사이클 중 길이가 Y 이상인 것들의 길이 합을 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다3초512 MB채점 가능
잔디 깎기 장난격자 위의 꽃들 가운데 두 소가 모두 지나야 할 가장 긴 사슬을 고른 뒤, 두 단조 경로가 훑는 넓이의 최솟값을 구한다.어려움9동적 계획법정렬+2아직 제출이 없습니다2초512 MB채점 가능
메시지길이 n인 소문자 문자열 가운데 주어진 패턴 p를 부분 문자열로 포함하는 것의 개수를 m으로 나눈 나머지를 구한다. n은 10^12까지, p의 길이는 최대 50이다.어려움9동적 계획법문자열 매칭+2아직 제출이 없습니다5초512 MB채점 가능
달콤새콤사탕 나라 선수 중 누구에게 단맛과 신맛을 무작위로 바꾸는 물약을 먹일지 골라, 모든 무작위 순서와 경기 종류에서 사탕 나라가 얻는 기대 점수를 최대로 만든다.어려움9확률조합론+2아직 제출이 없습니다1초512 MB채점 가능
쿼리와 쿼리질의마다 수열의 두 원소를 교환하고, 각 교환 뒤에 M개의 왼쪽 주머니 인덱스와 M개의 오른쪽 주머니 인덱스를 짝지어 얻어지는 범위 최댓값 중 가장 큰 값을 최소화한 값을 출력한다.어려움9세그먼트 트리그리디+2아직 제출이 없습니다2초512 MB채점 가능
연결그래프의 모든 간선의 저항이 1Ω일 때, 간선으로 직접 이어진 모든 점 쌍 A, B 사이 합성저항 값의 총합을 구해 소수점 넷째 자리에서 반올림한 값을 출력하는 문제모든 간선의 저항이 1인 연결 그래프에서 각 간선 양 끝점 사이의 등가 저항을 모두 더한 값을 소수점 셋째 자리까지 반올림해 구한다.어려움9그래프행렬+2아직 제출이 없습니다1초512 MB채점 가능
Africa 2숨겨진 채점 데이터의 정확히 절반에서만 정답을 내면서 샘플은 통과하는 코드를 제출하는 문제로, 답을 계산하는 것이 아니라 채점 환경을 이용하는 발상이 필요하다.어려움9구현완전 탐색+2아직 제출이 없습니다1.357초1357 MB채점 가능
Karel the Robot프로시저와 if, until을 포함한 간단한 로봇 언어를 해석해, 각 프로그램 실행이 끝난 뒤 Karel의 최종 위치를 출력하거나 무한 반복이면 "inf"를 출력한다.어려움9시뮬레이션구현+2아직 제출이 없습니다10초512 MB지문만 제공
가희의 수열놀이 (Large)스택에 값을 넣고 빼는 연산을 처리하면서, 3번 질의마다 접미사 중 나머지 0부터 mod-1까지가 모두 한 번 이상 나타나는 가장 짧은 길이를 구하고 불가능하면 -1을 출력한다.어려움9스택투 포인터+2아직 제출이 없습니다1초256 MB채점 가능
Increasing Sequence각 i마다 다른 원소 j 하나를 제거했을 때 i를 포함하는 최장 증가 부분 수열의 길이가 줄어드는 j의 개수를 구한다.어려움9동적 계획법세그먼트 트리+2아직 제출이 없습니다3초1024 MB지문만 제공
Dijkstra Is Playing At My House서로 겹치지 않는 최대 250,000개의 축 평행 직사각형 장애물이 있는 평면에서 두 점 사이의 맨해튼 최단 경로 길이를 구한다. 장애물의 경계는 지날 수 있다.어려움9최단 경로그래프+2아직 제출이 없습니다3초1024 MB지문만 제공
계곡서로 다른 높이를 가진 N x N 격자가 주어질 때, 모든 셀이 경계의 인접 셀보다 낮은, 구멍 없는 변 인접 영역들의 크기 합을 구한다.어려움9유니온 파인드그래프+2아직 제출이 없습니다2초512 MB채점 가능
아름다운 만영로간선에 꽃 이름이 붙은 방향 트리에서, 간선 문자열이 주어진 문자열 P와 같은 경로의 수를 센다.어려움9트라이DFS+2아직 제출이 없습니다2초512 MB채점 가능
문제집 만들기N개 문제 사이의 선후 관계를 간선 삽입과 삭제로 유지하면서, x번부터 y번까지의 문제가 이루는 부분 그래프가 비순환인지 판정한다.어려움9그래프동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
불확정성이 넘쳐흘러구간 [i,j]마다 [1,Y]에서 독립적으로 균등하게 뽑은 j-i+1개 값의 최대공약수가 Y와 서로소일 확률을 구해 모든 구간에 대해 더한 뒤, 분모 Y^N에 대한 분자를 1e9+9로 나눈 나머지를 출력한다.어려움9정수론동적 계획법+2아직 제출이 없습니다1초256 MB채점 가능
Grid Query 2100000 곱하기 100000 크기의 0 행렬에서 직사각형 덧셈 갱신과 직사각형 합 쿼리를 처리하며, 각 질의는 직전 출력값으로 복호화해 온라인으로 받는다.어려움9세그먼트 트리누적 합+2아직 제출이 없습니다15초1024 MB지문만 제공
Calligrapher격자 위에 축에 나란한 N, O, I 도형을 각 글자의 연결 사각형 규칙에 맞게 배치해 덮인 칸 값의 합이 최대가 되도록 한다.어려움9동적 계획법누적 합+2아직 제출이 없습니다1초512 MB지문만 제공
Magic Chessboard고정된 위치를 기준으로 하는 직사각형 영역의 최대공약수를 구하는 질의와, 임의의 직사각형 영역에 같은 값을 더하는 갱신을 함께 처리한다. N 곱하기 M은 500000 이하이고 연산 수는 100000 이하이다. 문제에서 주어진 조건만으로 판단할 때 2차원 GCD 세그먼트 트리와 차분 배열을 결합해야 하는 매우 어려운 문제이다. 인터뷰 문제가 아니라 대회용 고난도 문제에 해당한다. 19930324 같은 특수한 숫자는 정답 횟수와 관련된 장치일 뿐 알고리즘에는 영향을 주지 않는다. 갱신이 값을 더하는 형태이므로 GCD의 차분 성질을 이용해야 한다. 각 행과 열에 대해 차분 배열을 관리하고 GCD 세그먼트 트리로 구간 GCD를 유지하는 방식이 필요하다. 쿼리 영역이 고정된 위치를 기준으로 확장되므로 그 점을 활용한 최적화가 가능하다. 난이도는 9로 평가한다.어려움9세그먼트 트리정수론+2아직 제출이 없습니다5초512 MB지문만 제공