cho.sh

문제

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

전체 결과문제 7376개
제목난이도유형정답자시간 제한메모리 제한채점
Lucky Draws 2K가 1부터 m까지일 때, 고른 K개의 점 중 하나 이상을 포함하는 구간 [A,B]의 최대 개수를 구한다.어려움9그리디정렬+2아직 제출이 없습니다5초1024 MB지문만 제공
Do It Yourself?루트가 있는 트리에서 각 직원의 업무를 자신이나 조상에게 배정해 f_i 곱하기 업무 수의 제곱의 합을 최소화한다.어려움9동적 계획법그리디+2아직 제출이 없습니다10초1024 MB지문만 제공
조화 함수정수 계수 다항식 f와 g가 주어지고, 현재 f와 조화를 이루는 실수 계수 다항식 h로 f를 바꾸는 시행을 유한 번 해서 g에 도달할 수 있는지 판별한다.어려움9수학조합론+1아직 제출이 없습니다1초1024 MB지문만 제공
마비노기 가방 정리하기크기 2x2 이하의 물건과 직사각형 가방이 추가되거나 제거될 때마다, 가방 하나에 겹치지 않게 담을 수 있는 물건 가치 합의 최댓값을 구한다.어려움9동적 계획법세그먼트 트리+1아직 제출이 없습니다4초1024 MB지문만 제공
트리의 개수트리의 모든 부분 트리 T'에 대해 내구성 j 이하인 정점을 지운 뒤 남는 조각 수를 모든 j에 걸쳐 더한 값을 구한다.어려움9트리DFS+2아직 제출이 없습니다2초1024 MB지문만 제공
줌배열에 구간 덧셈, 절반을 복사하는 전역 연산, 지금까지의 모든 연산을 다시 실행하는 재생 연산이 주어질 때 구간 합을 998244353으로 나눈 나머지를 구한다.어려움9세그먼트 트리동적 계획법+2아직 제출이 없습니다3초1024 MB지문만 제공
카드 색칠 2첫 행의 일부만 주어진 N x N 격자를 규칙에 맞게 칠하는 모든 경우에 대해 흰색 연결 영역 수의 합을 998244353으로 나눈 나머지를 구한다.어려움9조합론수학+2아직 제출이 없습니다1초1024 MB지문만 제공
Minimum Longest Trip라벨이 붙은 비순환 방향 그래프에서 각 마을마다 가장 긴 경로를 찾고, 같은 길이면 라벨 수열이 사전순으로 가장 작은 것을 골라 길이와 라벨 합을 출력한다.어려움9그래프동적 계획법+2아직 제출이 없습니다2초1024 MB지문만 제공
닌자 파티같은 정점 집합 위의 두 트리가 주어질 때, 두 트리에서 파티 장소가 같아지는 공집합이 아닌 부원 집합 S의 개수를 10^9+7로 나눈 나머지를 구한다.어려움9트리조합론+2아직 제출이 없습니다5초1024 MB지문만 제공
Tube Master III각 교차점에 사용되는 관이 0개 또는 2개가 되고 각 칸에 정확히 count[i][j]개의 꺾임점이 인접하도록 관을 선택해 총비용을 최소화한다.어려움9동적 계획법그래프+2아직 제출이 없습니다1초1024 MB지문만 제공
Prof. Pang's sequence각 질의 구간에서 서로 다른 값의 개수가 홀수인 부분 배열의 개수를 세며, n과 m은 5*10^5까지 주어진다.어려움9누적 합동적 계획법+2아직 제출이 없습니다3초1024 MB지문만 제공
Wiring Engineering각 질의마다 내부에서 교차하지 않는 건물-탑 연결을 골라 고정 설치 비용을 치르고 이익이 최대가 되게 한다.어려움9동적 계획법구간+1아직 제출이 없습니다8초1024 MB지문만 제공
LIS Counting길이 NM인 순열 가운데 최장 증가 부분수열의 길이가 N이고 최장 감소 부분수열의 길이가 M인 것에 대해, 각 위치와 값이 등장하는 순열의 개수를 소수 P로 나눈 나머지를 구한다.어려움9조합론동적 계획법+1아직 제출이 없습니다2초1024 MB지문만 제공
Werewolves색이 칠해진 트리에서 특정 색이 절반을 초과해 차지하는 연결 부분 그래프의 개수를 998244353으로 나눈 나머지를 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다2초1024 MB지문만 제공
Many LCSK가 주어질 때, 서로 다른 최장 공통 부분 수열의 개수가 정확히 K인 두 이진 문자열을 길이 8848 이하로 만든다.어려움9동적 계획법조합론+1아직 제출이 없습니다4초1024 MB지문만 제공
Paimon Segment Tree구간 덧셈 갱신이 끝난 뒤, 부분 배열과 시간 구간에 걸친 값의 제곱 합을 여러 질의에 대해 구한다.어려움9세그먼트 트리누적 합+2아직 제출이 없습니다2초1024 MB지문만 제공
Paimon's Tree검은 정점 집합을 하나씩 늘려가며 간선에 a_1..a_n을 순서대로 부여할 때, 가중 트리의 지름 최댓값을 구한다.어려움9동적 계획법트리+1아직 제출이 없습니다4초1024 MB지문만 제공
마카롱카마파란색 코크를 재배치해 각 마카롱의 크기를 두 코크 중 큰 값으로 정하고, 얻어지는 N자리 수가 팰린드롬이 되도록 하면서 최댓값을 구한다.어려움9그리디동적 계획법+1아직 제출이 없습니다1초1024 MB지문만 제공
Two PathsDAG와 두 정점 쌍이 주어질 때, 각 쌍을 잇는 간선 비공유 단순 경로 중 총 길이가 최소인 쌍을 찾는다.어려움9그래프최단 경로+2아직 제출이 없습니다5초1024 MB지문만 제공
Random Spanning Tree정점이 8개 이하인 연결 그래프의 각 변 길이가 [0,1]에서 균등분포일 때 최소 신장 트리 무게의 기댓값을 분수로 구한다.어려움9조합론확률+2아직 제출이 없습니다1초1024 MB지문만 제공
Tri-color Spanning Tree빨강, 초록, 파랑으로 색칠된 무방향 그래프에서 초록 간선을 g개 이하, 파랑 간선을 b개 이하로 사용하는 신장 트리의 개수를 10^9+7로 나눈 나머지를 구한다.어려움9행렬조합론+2아직 제출이 없습니다2초1024 MB지문만 제공
아몬드 초콜릿각 변의 길이가 주어진 120도 육각형에서 여섯 꼭짓점의 마름모가 이미 놓여 있을 때, 나머지를 단위 마름모로 채우는 경우의 수를 구합니다.어려움9조합론동적 계획법아직 제출이 없습니다2초1024 MB지문만 제공
정렬된 프랙탈 수열길이 N이고 각 값이 1 이상 N 이하인 비내림차순 수열 A 가운데 모든 i에서 a_{a_i}=a_i를 만족하고 K개 위치의 값이 고정된 것의 개수를 M으로 나눈 나머지를 구한다.어려움9조합론수학+2아직 제출이 없습니다1초1024 MB지문만 제공
Merging Cells인접한 두 세포를 무작위로 합칠 때 각 라벨이 최종 세포가 될 확률을 1e9+7로 나눈 값으로 구한다.어려움9확률동적 계획법+2아직 제출이 없습니다2초1024 MB지문만 제공
점프 게임발판 수 N이 10^12까지이고 A[i]가 Q개의 구간 증가 연산으로 정해질 때, 한 번에 K칸 점프하거나 한 칸 걷는 이동으로 N-1을 넘어설 때 얻는 점수의 최댓값을 구한다.어려움9동적 계획법그리디+2아직 제출이 없습니다3초1024 MB지문만 제공
庭園 2 (Garden 2)격자에 마름모를 놓고 각 링의 색을 자유롭게 정할 때, 격자의 색과 일치하는 칸 수의 최댓값을 구한다.어려움9누적 합동적 계획법+2아직 제출이 없습니다4초1024 MB지문만 제공
Road Service 2격자 도로망에서 동서 방향 도로 한 줄을 통째로 복구하는 데 드는 비용이 1 또는 2일 때, 각 질의마다 주어진 교차점들을 서로 연결하는 최소 복구 기간을 구한다.어려움9그래프유니온 파인드+2아직 제출이 없습니다3초1024 MB지문만 제공
가지밭길장애물을 피해 (0,0)에서 (R,C)까지 가는 단조 경로 두 개가 모든 가지를 같은 쪽에 두면 같은 경로로 보고, 서로 다른 경로의 수를 10^9+7로 나눈 나머지를 구한다.어려움9조합론동적 계획법+1아직 제출이 없습니다1초1024 MB지문만 제공
Colourful Tree가중 트리에 리프를 추가하고 정점의 색을 바꾸는 연산을 처리하면서, 매번 서로 다른 색인 두 정점 사이 거리의 최댓값을 구한다.어려움9트리분할 정복+2아직 제출이 없습니다6초1024 MB지문만 제공
Splatanie ciągówA와 B의 모든 연속 부분배열 쌍에 대해 두 배열을 섞어 만들 수 있는 최소 안정성을 구하고, 그 값별로 쌍의 개수를 센다.어려움9동적 계획법조합론+2아직 제출이 없습니다9초1024 MB지문만 제공
Monetyk개부터 n개까지 각 길이 d마다 주어진 접두사를 이어 붙여 만든 m개 동전 더미들의 나열이 최적 플레이에서 후수 승리가 되는 경우의 수를 센다.어려움9게임 이론조합론+2아직 제출이 없습니다25초1024 MB지문만 제공
Hyper Tree Problem가중치 트리에서 각 간선의 가중치를 주어진 값과 비트 AND로 갱신하고, 특정 정점에서 다른 모든 정점까지 경로 OR 가중치의 합을 구하는 질의를 처리한다.어려움9트리비트 연산+2아직 제출이 없습니다4초1024 MB지문만 제공
Fish 3각 질의 구간마다 두 종류의 먹이를 넣어 목표 지능값을 정확히 만들 수 있는지 판정하고, 가능하면 A 먹이의 최소 개수를 구한다.어려움9그리디구현+2아직 제출이 없습니다2초1024 MB지문만 제공
JOI Tour주스, 오믈렛, 아이스크림 음식점이 있는 마을 세 곳을 골라 두 최단 경로가 같은 도로를 지나지 않는 경우의 수를 구하고, 음식점 종류가 바뀔 때마다 그 값을 다시 계산한다.어려움9트리DFS+2아직 제출이 없습니다3초1024 MB지문만 제공
Escape Route 2매일 운항하는 인접 도시 간 항공편을 이용해 도시 L에서 R까지 가는 최소 소요 시간을 각 질의마다 구한다.어려움9동적 계획법세그먼트 트리+2아직 제출이 없습니다2초1024 MB지문만 제공
Insects, Mathematics, Accuracy, and Efficiency원 안에 있는 N개의 점이 주어질 때, 원 안의 한 점을 하나 더 골라 볼록 껍질의 넓이를 최대로 만들어야 한다.어려움9기하완전 탐색+1아직 제출이 없습니다0.5초1024 MB지문만 제공
무당벌레방문한 칸 집합 S와 각 열의 최초 방문 행 F가 같은 탈출 방법을 하나로 세어, 탈출 행별 가짓수를 1e9+7로 나눈 나머지로 구한다.어려움9동적 계획법조합론+2아직 제출이 없습니다2초512 MB지문만 제공
Discount Event가중치가 있는 트리에서 각 질의마다 두 도시 사이 경로의 모든 간선 비용을 0으로 만들고, 그때 임의의 두 도시 사이 거리의 최댓값을 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다4초1024 MB지문만 제공
One, Two, Three1, 2, 3으로 이루어진 수열과 각 원소의 아름다움이 주어질 때, 합이 4 또는 8인 연속 구간을 반복해서 제거하여 남은 원소 합의 최솟값과 그때의 아름다움 합 최댓값을 구한다.어려움9그리디동적 계획법+1아직 제출이 없습니다1초1024 MB지문만 제공
Compression이진 문자열에서 인접한 두 개의 같은 부분 문자열 중 하나를 반복해서 지우며, 최종 문자열이 가장 짧아지도록 제거 순서를 정한다.어려움9문자열동적 계획법+2아직 제출이 없습니다1초1024 MB지문만 제공
Alea Iacta Est주사위 6개 이하와 길이 d인 단어 사전이 주어질 때, 단어를 만들기까지 필요한 기대 굴림 횟수를 최소로 하는 최적 전략을 구한다.어려움9동적 계획법확률+2아직 제출이 없습니다10초1024 MB지문만 제공
House Deconstruction원 위에 사람과 그보다 많은 집이 있을 때, 일부 집을 부순 뒤 각 사람을 서로 다른 남은 집까지 원을 따라 최소 총 이동 거리로 배정한다. 이 비용을 모든 삭제 집합에 대해 최소화하고, 그 최솟값을 이루는 집합의 개수를 센다.어려움9동적 계획법그리디+2아직 제출이 없습니다1초2048 MB지문만 제공
이진 트리이전 트리 두 개를 합쳐 T_i를 만들고, 각 트리에서 연속한 리프 구간 [a,b]를 덮는 최소 서브트리 개수 f(a,b)의 모든 구간 합을 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다1초1024 MB지문만 제공
기숙사 택배물 배달무게 제한 없이 여러 택배를 들 수 있는 예성이가 N+1번 보관실에서 출발해 M개의 택배를 각 방에 배달하고 돌아올 때 걸리는 최소 시간을 구한다.어려움9그리디정렬+2아직 제출이 없습니다1초1024 MB지문만 제공
리스트 가상화직사각형 항목이 빈틈없이 쌓인 목록에서 삽입과 삭제를 처리하면서, 주어진 구간의 내부와 겹치는 항목 수를 구한다.어려움9트리이분 탐색+2아직 제출이 없습니다6초1024 MB지문만 제공
복사 붙여넣기파일 [0] 하나에서 시작해 복사 붙여넣기를 K번 한 뒤, 수열 A가 사전순으로 몇 번째인지 998244353으로 나눈 나머지를 구한다.어려움9트리조합론+2아직 제출이 없습니다3초1024 MB지문만 제공
Go 2격자 변에 성냥을 놓아 닫힌 영역이 생기면 그 넓이만큼 점수를 얻는다. 각 수가 몇 점이었는지 순서대로 출력한다.어려움9기하그래프+2아직 제출이 없습니다3초1024 MB지문만 제공
COVID tests각 검체가 양성일 확률이 P로 독립인 상황에서 모든 양성 검체를 가려내는 데 필요한 검사 횟수의 최솟값을 기댓값 기준으로 구한다.어려움9확률동적 계획법+2아직 제출이 없습니다미설정1024 MB지문만 제공
두 개의 트리를 이용하는 놀이특별한 노드가 표시된 두 트리가 주어질 때, 각 트리에서 노드를 하나씩 골라 연결했을 때 생기는 트리에서 두 트리의 특별한 노드를 정확히 하나씩 포함하는 단순 경로 개수의 가중합을 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
4색 정리바깥평면 그래프를 4색으로 칠하되 주어진 색 순서쌍이 간선의 양 끝에 나타나지 않도록 하고, 불가능하면 -1을 출력한다.어려움9그래프동적 계획법+2아직 제출이 없습니다4초1024 MB지문만 제공
\prod_{i=1}^N(R_i-L_i+1)개의 트리각 정점의 비용 계수 c_i를 주어진 범위에서 모두 고를 때, 서브트리 합 하한과 정점별 상한을 만족하는 a_i의 가중합 최솟값을 구해 그 값들을 모두 더한다.어려움9동적 계획법트리+2아직 제출이 없습니다2초1024 MB지문만 제공
스레드N개의 스레드가 각각 x=x+1 명령을 두 단계로 나누어 실행될 때, 모든 실행 순서 중에서 최종 x 값별로 경우의 수를 세어 998244353으로 나눈 나머지를 구한다.어려움9조합론수학+2아직 제출이 없습니다3초1024 MB지문만 제공
트리를 쓰는 트리 문제루트가 아닌 각 정점마다 부모로 가는 간선을 끊고 부분 트리를 다른 정점에 다시 붙일 때 얻을 수 있는 트리 지름의 최댓값을 구한다.어려움9트리DFS+2아직 제출이 없습니다2초1024 MB지문만 제공
지문이 트리로 가득 찬 트리 문제서로 겹치지 않는 구간들을 고르되 주어진 필수 구간들을 반드시 포함해야 할 때, 각 쿼리마다 고를 수 있는 구간 개수의 최댓값을 구한다.어려움9동적 계획법그리디+2아직 제출이 없습니다2초1024 MB지문만 제공
Split the SSHS 4트리의 각 정점에 리프 하나를 매달았을 때, 정점 하나를 터트리면 그 정점과 이웃들이 함께 제거되는 규칙으로 트리 전체를 지우는 최소 횟수를 각 정점마다 구한다.어려움9트리동적 계획법+1아직 제출이 없습니다2초1024 MB지문만 제공
닌자 택배트리 위에서 두 물류 허브 x, y를 골라 x를 거쳐 y로 가는 Q개 요청의 총 수송 비용을 최소화한다.어려움9트리동적 계획법+2아직 제출이 없습니다1초1024 MB지문만 제공
물탱크 알바(Hard)이진 트리에서 물탱크 하나를 골라 m의 물을 부을 때 꽉 채울 수 있는 물탱크 수의 최댓값을 구한다.어려움9트리DFS+2아직 제출이 없습니다3초1024 MB지문만 제공
나무에서 나뭇가지가 다 사라지면?루트 있는 트리에서 루트까지의 경로를 골라 그 정점으로 님 게임을 한 뒤 트리를 서브트리로 쪼개는 게임을 두 사람이 번갈아 하며 승자를 판정한다.어려움9게임 이론트리+2아직 제출이 없습니다1초1024 MB지문만 제공
MATKOR 문자열 만들기점 갱신이 있는 문자열에서 부분 문자열마다 MATKOR로 만드는 방법의 수와 연산 횟수의 분산을 구한다.어려움9세그먼트 트리동적 계획법+2아직 제출이 없습니다3초1024 MB지문만 제공
\mathbb{E}\left(\operatorname{LCS}\right)K가 나올 때까지 무작위로 수를 뽑아 만든 증가 수열 M개의 LCS 길이 기댓값을 K=1부터 N까지 모두 구해 출력한다.어려움9확률조합론+2아직 제출이 없습니다1초1024 MB지문만 제공
트리와 경로 뒤집기 쿼리방향 트리가 주어지고, 각 쿼리는 u와 v 사이의 무방향 경로에 있는 모든 간선 방향을 뒤집은 뒤 도달 가능한 순서쌍 (a,b)의 개수를 묻는다.어려움9트리동적 계획법+2아직 제출이 없습니다6초1024 MB지문만 제공
Tree각 질의 (L,R)마다 모든 부분트리 합이 [L,R]에 들어가도록 정수 계수를 배정하고, 계수 절댓값의 가중합을 최소로 만든다.어려움9트리동적 계획법+2아직 제출이 없습니다2초1024 MB지문만 제공
Telephone Plans동적으로 변하는 숲에서 간선을 넣고 빼며, 최근 시간 구간 동안 한 번이라도 연결된 집의 쌍 수를 센다.어려움9그래프유니온 파인드+2아직 제출이 없습니다4초1024 MB지문만 제공
Automata Embedding길이 n인 문자열 가운데 KMP 실패 링크 오토마타를 평면에 교차 없이 그릴 수 있는 것의 개수를 C가지 문자로 세어 998244353으로 나눈 나머지를 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다1초1024 MB지문만 제공
White-Black-Tree두 색으로 칠해진 트리에서 인접한 두 정점의 색을 맞바꿀 수 있다. 유한 번의 교환을 마친 뒤, 교환 횟수와 흰 정점 및 검은 정점을 각각 잇는 최소 부분그래프의 간선 수 합을 더한 값을 최소화한다.어려움9트리DFS+2아직 제출이 없습니다2초1024 MB지문만 제공
GAME배열의 한 원소가 갱신되는 상황에서 이동 거리 제한 D가 고정된 게임을 10^100턴 진행할 때, 주어진 시작 위치에서 선수가 이기는지 각 질의마다 판정한다.어려움9게임 이론동적 계획법+2아직 제출이 없습니다1.5초1024 MB지문만 제공
AQUARELLE칠해진 구간과 셀마다 정해진 색 집합이 주어질 때, 구간을 넓혀 가며 새 셀마다 이전에 쓰이지 않은 색을 하나 이상 추가해 모든 셀을 칠할 수 있는지 판정한다.어려움9동적 계획법그리디+2아직 제출이 없습니다0.4초1024 MB지문만 제공
동적 사이클 계산 쿼리정해진 규칙에 따라 간선을 넣고 빼면서, 두 간선이 포함되는 간선 단순 사이클의 집합이 정확히 같은지 판정하는 문제입니다.어려움9그래프유니온 파인드+2아직 제출이 없습니다6초1024 MB지문만 제공
HijerarhijaN개의 정점과 N-1개의 간선을 가진 유향 그래프에서 간선을 하나씩 뒤집을 때마다 한 정점이 모든 정점에 도달하는 루트 트리인지 판별한다.어려움9그래프동적 계획법+2아직 제출이 없습니다1초1024 MB지문만 제공
Cross Countryn개의 선분 검문소를 1번부터 n번까지 순서대로 통과하면서 시작점에서 도착점까지 가는 최단 경로의 길이를 구한다.어려움9기하동적 계획법+2아직 제출이 없습니다10초1024 MB지문만 제공
Jabber Network오래된 케이블을 하나씩 제거한 뒤 통신 스트레스가 최소가 되도록 새 케이블로 트리를 다시 연결하고, 동률이면 끝점 번호가 가장 작은 쌍을 골라 각 단계의 연결 쌍을 출력한다.어려움9트리그리디+2아직 제출이 없습니다2초1024 MB지문만 제공
표식각 흰 정사각형에 W개의 도형이 들어 있고 검은 정사각형이 적어도 하나 있으며 검은 정사각형 총합이 B일 때, 홀수 길이와 짝수 길이 표식의 수를 비교한다.어려움9조합론수학+2아직 제출이 없습니다1초512 MB지문만 제공
Fences Make Good Neighbors볼록 n각형을 최소 총 길이로 삼각분할하되, 두 형제의 토지가 정확히 두 개의 울타리로 분리되도록 해야 한다.어려움9동적 계획법기하+1아직 제출이 없습니다4초2048 MB지문만 제공
Complexity Measure순서열 X[i..n]에서 노드의 이진 검색 트리 부모가 시작 위치 i가 변할 때 바뀌는 횟수의 합을 계산합니다.어려움9동적 계획법트리+2아직 제출이 없습니다3초1024 MB지문만 제공
Stablo노드 x를 y 아래로 옮긴 뒤, y의 서브트리에 속한 모든 노드에서 y까지의 가중 거리 합을 구한다.어려움9트리DFS+2아직 제출이 없습니다2초2048 MB지문만 제공
Tree Generators각각 무작위로 트리를 만드는 두 괄호 표현식이 주어질 때, 두 표현식 모두에서 만들어질 수 있는 트리의 수를 998244353으로 나눈 나머지로 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다2초2048 MB지문만 제공
Greatest of the Greatest Common Divisors수열과 q개의 구간 질의가 주어질 때, 각 구간 안에서 서로 다른 두 원소의 최대공약수 가운데 가장 큰 값을 구한다.어려움9정수론세그먼트 트리+2아직 제출이 없습니다1초2048 MB지문만 제공
Peculiar Protocol은행권 열에서 합이 d*k+r인 연속 구간을 반복해서 떼어내며, 뗀 횟수가 아니라 k의 총합을 최대로 만든다.어려움9동적 계획법구간+2아직 제출이 없습니다2초2048 MB지문만 제공
19m19p19s12345675z정수 k가 주어질 때 서로 다른 모든 마작패 문자열을 ASCII 사전순으로 나열했을 때 k번째 문자열을 구하고, 개수를 넘으면 -1을 출력한다.어려움9조합론동적 계획법+2아직 제출이 없습니다2초1024 MB지문만 제공
Interstellar Intervals같은 길이의 빨강·파랑 구간 쌍을 겹치지 않게 배치해 N개 점을 칠할 때, R/B/X 제약을 만족하는 색칠의 수를 센다.어려움9동적 계획법조합론+2아직 제출이 없습니다2초2048 MB지문만 제공
2D Conveyor BeltN×N 격자에 Q개의 방향 칸이 차례로 고정될 때, 남은 칸을 모두 채웠을 때 영원히 빠져나가지 못하게 만들 수 있는 칸 수의 최솟값을 매번 구한다.어려움9그래프DFS+2아직 제출이 없습니다2초2048 MB지문만 제공
Expected Beauty각 원소를 주어진 구간에서 균등하게 뽑을 때, 인접한 같은 값을 지워 얻는 점수의 최댓값을 제곱한 값의 기댓값을 구한다.어려움9동적 계획법조합론+2아직 제출이 없습니다1초2048 MB지문만 제공
Count DFS Tree모든 잎이 깊이 K에 있는 n개 노드 트리에서 DFS 반환 수열의 서로 다른 가짓수를 구하고, M개 질의의 값을 곱해 출력한다.어려움9조합론동적 계획법+1아직 제출이 없습니다1초2048 MB지문만 제공
Narrower Passageway각 열이 1/2 확률로 안개에 덮이고, 안개가 없는 최대 연속 구간마다 정의된 강도의 합의 기댓값을 998244353으로 나눈 나머지를 구한다.어려움9확률동적 계획법+2아직 제출이 없습니다1초2048 MB지문만 제공
Inversion Insight1부터 N까지의 모든 순열을 반전 수 오름차순으로, 같으면 사전순으로 정렬했을 때 K번째 순열을 구해 출력한다.어려움9조합론동적 계획법+2아직 제출이 없습니다0.5초2048 MB지문만 제공
Sweets루트가 있는 트리에서 각 시장의 학습 수치가 갱신될 때마다, 루트에서 임의의 노드까지 가는 경로에서 성공할 수 있는 시장 수의 최댓값을 구한다.어려움9트리세그먼트 트리+2아직 제출이 없습니다3초2048 MB지문만 제공
Gladni Gargamel각 단계에서 흰 칸에 발을 디디면 모든 흰 칸 중 하나로 순간이동하는 격자에서, 최적의 이동으로 오른쪽 아래 칸에 도착할 때까지 걸리는 기대 걸음 수를 구한다.어려움9확률동적 계획법+2아직 제출이 없습니다1초2048 MB지문만 제공
Dale ‘n’ Chip각 구간에서 선택한 다람쥐가 오른쪽 이웃과 정확히 한 번 이기고 한 번 지도록 원을 이루게 하는 최대 인원수를 구한다.어려움9조합론누적 합+2아직 제출이 없습니다2초2048 MB지문만 제공
Difficult PasswordL자 이상 R자 이하이며 숫자와 영문자를 모두 포함하고, 같은 문자가 A번 연속하거나 B번 연속 오름차순/내림차순이 되는 일이 없는 비밀번호의 개수를 구한다.어려움9동적 계획법조합론+2아직 제출이 없습니다3초2048 MB지문만 제공
Edges and Divisors길이 1, 2, ...의 경로를 골라 i번째 경로의 간선 가중치 합이 i+1의 배수가 되게 하면서 가중 평균 경로 길이를 최대화한다.어려움9그래프동적 계획법+2아직 제출이 없습니다1초2048 MB지문만 제공
Hard to Compare각 테스트케이스의 n과 k에 대해 x가 1부터 k-1까지 변할 때 f(n,k,x)의 가장 큰 값 9개의 합을 1e9+7로 나눈 나머지를 구한다.어려움9조합론수학+1아직 제출이 없습니다4초9 MB지문만 제공
Counting Is Not Fun (Easy Version)좋은 쌍 n개를 갖는 미지의 균형 괄호열에서 각 단서가 주어진 뒤 조건을 만족하는 괄호열의 개수를 구합니다.어려움9동적 계획법조합론+2아직 제출이 없습니다3초2048 MB지문만 제공
Counting Is Not Fun (Hard Version)균형 잡힌 괄호열의 좋은 쌍이 하나씩 주어질 때마다 그때까지의 단서를 만족하는 균형 괄호열의 개수를 998244353으로 나눈 나머지로 구한다.어려움9조합론트리+2아직 제출이 없습니다3초2048 MB지문만 제공
입자 가속기Q번의 입자 생성 시도(성공 시 입자 정지, 실패 시 방 폐쇄)가 주어질 때, 매 시도 후 진행 가능한 충돌 실험의 최대 횟수를 구한다.어려움9트리DFS+2아직 제출이 없습니다5초2048 MB지문만 제공
다리 보수 공사다리들은 (1,1)에서 (N,N)으로 가는 단조 격자 경로를 이루며, 두 다리가 마을을 공유하지 않도록 최대 개수의 다리를 고르고 그러한 최대 집합의 수를 1e9+7로 나눈 나머지로 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다2초2048 MB지문만 제공
Series Sumn=k부터 무한대로 가는 C(n,k)^p / 2^n의 합을 998244353으로 나눈 나머지를 구한다. p*k <= 10^6이다.어려움9수학조합론+2아직 제출이 없습니다2초2048 MB지문만 제공
Growing Sequences각 원소가 1 이상 c 이하이고 이전 원소의 두 배 이상인 길이 n 배열의 개수를 998244353으로 나눈 나머지를 구한다.어려움9동적 계획법수학+1아직 제출이 없습니다1초2048 MB지문만 제공
Hierarchies of Judgesn개의 정점으로 이루어진 뿌리 있는 트리에서 각 정점을 신뢰/불신뢰로 표시하고, 각 정점이 자신과 자식 중 절반 이상 신뢰일 때 공정하다고 한다. 신뢰 자식은 순서를 무시하고 불신뢰 자식은 순서를 구분할 때 공정한 트리의 수를 세는 문제이다.어려움9조합론트리+2아직 제출이 없습니다6초2048 MB지문만 제공
Interval Addition수열이 주어질 때, 연속한 구간에 실수를 더하는 연산만으로 모든 원소를 0으로 만드는 최소 연산 횟수를 구한다.어려움9동적 계획법그리디+2아직 제출이 없습니다4초2048 MB지문만 제공
Lines각 i에 대해 F_i(t) = i*t + M_i이고 M_i는 x+y+z=i인 a_x+b_y+c_z의 최댓값일 때, 다른 모든 함수를 항상 앞서는 t가 존재하지 않는 i를 모두 찾는다.어려움9동적 계획법기하+2아직 제출이 없습니다1초2048 MB지문만 제공