cho.sh

문제

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

전체 결과문제 7376개
제목난이도유형정답자시간 제한메모리 제한채점
Oneness주어진 의사 난수 생성기로 아주 큰 수 n의 자릿수를 만든 뒤, 1부터 n까지 모든 정수 x에 대해 oneness(x)(x를 나누는 1로만 이루어진 1보다 큰 약수의 개수)의 합을 구한다.어려움9수학정수론+2아직 제출이 없습니다2초512 MB지문만 제공
Sketch각 길이의 비감소 부분수열이 가질 수 있는 가장 작은 마지막 값을 모은 스케치 일부가 주어질 때, 이를 만족하는 길이 n, 값 범위 1..m의 수열을 만들거나 불가능함을 판정한다.어려움9그리디동적 계획법+2아직 제출이 없습니다1초512 MB지문만 제공
hi각 정수 a를 정확히 C_a개 포함하는 모든 서로 다른 원형 수열에 대해, 같은 값이 연속한 구간 길이의 곱으로 정의된 점수의 합을 구한다.어려움9조합론동적 계획법+1아직 제출이 없습니다1초1024 MB지문만 제공
Repeating Subsequence Tests문자열 S가 주어질 때 의사 난수 생성기가 만들어 내는 여러 부분문자열 각각의 서로 다른 부분열 개수를 구해 마지막 값을 10^9+7로 나눈 나머지를 출력한다.어려움9동적 계획법문자열+2아직 제출이 없습니다2초512 MB지문만 제공
Connected Subgraph트리에 최대 10개의 간선을 추가한 그래프에서, 간선을 일부 제거한 뒤에도 그래프가 연결되는 경우의 수를 998244353으로 나눈 나머지를 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다1초256 MB지문만 제공
Prefix-free Queries각 질의마다 주어진 부분 문자열들의 부분집합 중 서로 접두사 관계가 없는 것의 개수를 세고, 같은 부분 문자열도 인덱스별로 따로 센 뒤 m으로 나눈 나머지를 구한다.어려움9트라이트리+2아직 제출이 없습니다2초256 MB지문만 제공
동전 던지기두 사람이 길이 20 이하의 H/T 문자열을 하나씩 고르고, 공정한 동전을 던져 둘 중 하나 또는 둘 다 처음 나타날 때까지 진행할 때 앨리스 승리, 밥 승리, 무승부 확률을 각각 구한다.어려움9확률동적 계획법+2아직 제출이 없습니다1초256 MB채점 가능
Statistics값의 합이 정확히 V이고 원소 수가 최소인 부분집합들 가운데 평균, 중앙값, 최빈값의 등장 횟수, 최댓값과 최솟값의 차의 최솟값을 각각 구한다.어려움9동적 계획법정렬+2아직 제출이 없습니다1.5초256 MB지문만 제공
Randomized Binary Search Tree무작위 키와 우선순위를 가진 N개의 원소를 트립에 삽입할 때, 최종 높이가 h가 될 확률을 각 h마다 구한다.어려움9확률동적 계획법+2아직 제출이 없습니다2.5초512 MB지문만 제공
201 패턴을 피하는 상승 수열길이 n인 ascent sequence 가운데 패턴 201을 피하는 것의 개수를 소수 p로 나눈 나머지를 구한다. n은 최대 500이다.어려움9동적 계획법조합론+2아직 제출이 없습니다2초512 MB채점 가능
Power of Power Partition Functionn, m, k가 주어질 때 m의 거듭제곱들의 분할 함수를 k번 합성곱한 값의 i=0부터 n까지의 합을 10^9+7로 나눈 나머지를 구한다.어려움9동적 계획법조합론+1아직 제출이 없습니다2초512 MB지문만 제공
최대 유량각각 n개 정점으로 이루어진 두 경로와 2n+1개의 연결 간선이 주어질 때, (0,0)에서 (1,n)까지의 최대 유량을 구한다.어려움9그래프최단 경로+2아직 제출이 없습니다2초512 MB채점 가능
Graph Coloring 2정점이 최대 18개인 그래프에서 공집합이 아닌 모든 부분집합의 색칠수를 구한 뒤 해시값을 출력한다.어려움9동적 계획법비트 연산+1아직 제출이 없습니다2초512 MB지문만 제공
Parentheses길이 n인 모든 괄호 문자열에 대해 올바른 문자열로 바꾸는 데 필요한 뒤집고 뒤집힌 괄호 바꾸기 연산의 최솟값을 구하고, 그 값의 가중합을 m으로 나눈 나머지를 계산한다.어려움9조합론동적 계획법+2아직 제출이 없습니다1초512 MB지문만 제공
Values on a Tree가중치 없는 트리에서 지름이 정확히 K인 비어 있지 않은 정점 부분집합의 개수를 K=0부터 n-1까지 998244353으로 나눈 나머지로 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다1초512 MB지문만 제공
Generator가중치가 주어진 무작위 숫자 스트림에서 n개의 서로 다른 길이 L 수열이 모두 한 번 이상 나타날 때까지의 기대 시간을 구해 1e9+7로 나눈 값을 출력한다.어려움9동적 계획법확률+2아직 제출이 없습니다3초256 MB지문만 제공
적은 시간, 많은 이익건설할 발전소의 부분집합을 고르는데, 상점은 필요한 발전소가 모두 지어졌을 때만 이익을 준다. 최대 건설 시간을 최소화한 뒤 그 시간 안에서 이익을 최대화한다.어려움9동적 계획법그래프+2아직 제출이 없습니다1초256 MB채점 가능
애완 트리트리의 각 간선 길이를 주어진 범위에서 정할 때 지름이 S 이상 E 이하가 되는 조합의 수를 세어 1e9+7로 나눈 나머지를 구한다.어려움9동적 계획법트리+2아직 제출이 없습니다8초1024 MB채점 가능
관광 사업가중치 트리에서 각 질의마다 서로소인 후보 도시 집합 A, B와 인구가 주어질 때, X는 A에서 Y는 B에서 골라 (C_X+C_Y)*dist(X,Y)를 최대로 만드는 값을 구한다.어려움9트리분할 정복+2아직 제출이 없습니다5초1024 MB지문만 제공
꿀벌반지름 N인 육각 벌집에서 꿀벌이 모을 수 있는 최대 에너지를 구한다. 다른 칸으로 날아가는 비용은 (벌집 거리 - 1) × F이고, 이미 지나간 경로를 다시 지나면 비용이 들지 않는다.어려움9그래프최단 경로+1아직 제출이 없습니다1초1024 MB지문만 제공
인간의 실수각 차례에 인접한 말 하나를 잡아 없애야 하는 격자 게임에서, 두 선수가 후보 수 집합의 크기를 각자의 오차 계수로 제한할 수 있을 때 최적 전략 아래에서 저스틴이 이길 확률을 구한다.어려움9게임 이론비트 연산+2아직 제출이 없습니다1초512 MB채점 가능
오답두 캐릭터를 쓰는 그리디 풀이의 결과가 실제 최솟값에서 최대한 멀어지도록 비용 행렬을 만들어, 그 비율을 최대화하는 입력을 구성한다.어려움9그리디동적 계획법+2아직 제출이 없습니다1초512 MB채점 가능
Robot모든 시작 기둥에 대해 왼쪽 로봇과 오른쪽 로봇의 이동 거리 차이가 2 이하가 되도록, 각 기둥 높이를 주어진 범위 안에서 정하는 경우의 수를 센다.어려움9동적 계획법조합론+1아직 제출이 없습니다1초512 MB지문만 제공
Aesthetic미적 순서로 번호가 매겨진 연결 가중 그래프에서 i < j인 두 간선을 골라 i번 간선의 길이에 Wj를 더했을 때, 1번에서 N번까지 최단 거리가 가질 수 있는 최댓값을 구한다.어려움9그래프최단 경로+2아직 제출이 없습니다2초1024 MB지문만 제공
Firefighting가중치가 있는 트리에서 모든 마을이 선택한 마을 중 하나로부터 거리 K 이내에 있도록 최소 개수의 마을을 소방서로 골라, 그 개수와 한 가지 배치를 출력한다.어려움9트리그리디+2아직 제출이 없습니다3초512 MB지문만 제공
Star Trek나무의 D개 평행 우주 사본에 포털을 배치할 때, 새로운 행성을 방문하는 게임에서 선공이 이기는 배치의 수를 구한다.어려움9트리게임 이론+2아직 제출이 없습니다1초32 MB지문만 제공
Race of robots1열의 모든 로봇이 (n, m)까지 같은 최소 시간으로 도달하도록, 주어진 정보와 모순되지 않는 n 곱하기 m 격자의 장벽 배치 가짓수를 998244353으로 나눈 나머지로 구한다.어려움9동적 계획법그래프+2아직 제출이 없습니다1초512 MB지문만 제공
Formula 42볼록한 바깥 경계 안에서 볼록한 안쪽 경계를 평행 이동해, 두 경계 사이를 한 바퀴 돌 수 있는 원형 자동차의 최대 반지름을 구한다.어려움9기하이분 탐색+1아직 제출이 없습니다1초512 MB지문만 제공
원자구간 덧셈 갱신이 주어지는 전하 수열에서, 질의 구간 안에 한정했을 때 인접한 두 전하의 차가 정확히 1인 최장 연속 구간의 길이를 구한다.어려움9세그먼트 트리동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
Circuit단일 전선 네트워크를 직렬 및 병렬로 합성해 만든 그래프가 주어질 때, 전선을 제거해 신장 트리를 만드는 경우의 수를 998244353으로 나눈 나머지를 구한다.어려움9그래프트리+2아직 제출이 없습니다1초512 MB지문만 제공
Economic One-way Roads각 간선의 방향마다 비용이 주어진 무방향 그래프에서 모든 간선의 방향을 정해 강하게 연결되도록 만들 때 최소 비용을 구하고, 불가능하면 -1을 출력한다.어려움9동적 계획법그래프+2아직 제출이 없습니다5초1024 MB지문만 제공
LCS 8길이 N인 대문자 문자열 T 중에서 주어진 문자열 S와의 최장 공통 부분 수열 길이가 N-K 이상인 것의 개수를 K가 3 이하일 때 10^9+7로 나눈 나머지로 구한다.어려움9동적 계획법조합론+2아직 제출이 없습니다3초1024 MB지문만 제공
트리와 쿼리 17루트 있는 트리에서 서브트리 증가와 경로 증가 쿼리를 처리한 뒤, 매번 가중 1-중앙값 정점을 출력한다.어려움9트리누적 합+2아직 제출이 없습니다2초1024 MB지문만 제공
Steel Slicing 2두 히스토그램으로 만든 히스토곤을 모든 조각이 직사각형이 되도록 자르는 데 필요한 최소 수평·수직 절단 횟수를 구한다.어려움9분할 정복동적 계획법+2아직 제출이 없습니다1초1024 MB지문만 제공
SemaforM개의 5세그먼트 디스플레이에서 K번째 이동마다 유효한 숫자가 되도록 세그먼트를 켜고 끄는 이동 순서의 수를 각 최종 숫자별로 10^9+7로 나눈 나머지를 구한다.어려움9동적 계획법행렬+2아직 제출이 없습니다4초512 MB지문만 제공
Meetings각 질의 구간에서 회의 장소를 정할 때, 참가자마다 자기 산과 회의 산 사이 최대 높이의 합이 최소가 되는 값을 구한다.어려움9세그먼트 트리분할 정복+2아직 제출이 없습니다4.5초768 MB지문만 제공
소가 연세로를 건너간 이유좌우 순열을 각각 회전시키는 모든 N^2가지 경우에 대해 가로지르는 쌍의 수를 구해 모두 더한 값을 1,000,000,009로 나눈 나머지를 출력한다.어려움9조합론수학+2아직 제출이 없습니다5초1024 MB지문만 제공
Мониторинг труб주어진 m개의 문자열 중 하나와 라벨 순서가 같은 방향 경로들로 루트 트리의 모든 간선을 덮는 최소 비용을 구한다.어려움9트라이그래프+2아직 제출이 없습니다1초512 MB지문만 제공
Телефонный номер하이픈으로 나뉜 전화번호 하나가 주어질 때, 러시아어로 읽었을 때 같은 소리가 나는 다른 모든 번호 묶음을 찾는다.어려움9문자열 매칭동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
쿼리와 수열각 위치에서 후보 값 하나를 골라 구간 최댓값 쿼리 결과의 합에서 선택 비용을 뺀 값을 최대화한다.어려움9동적 계획법분할 정복+2아직 제출이 없습니다2.5초1024 MB지문만 제공
정기 모임 2정점 1부터 i까지로 이루어진 각 모임에서, 모임을 X개의 장소로 나눌 때 가능한 최대 이동 거리의 최솟값을 X=1부터 K까지 더한 값을 모든 i에 대해 구한다. 두 정점 사이 거리는 경로 위 간선 가중치의 최댓값이다.어려움9트리그리디+2아직 제출이 없습니다3초1024 MB지문만 제공
Counting Stars별이 시간에 따라 추가되고, 세 별로 만든 삼각형의 변과 내부에 있는 별들의 아름다움 합을 각 질의마다 구한다.어려움9기하동적 계획법+2아직 제출이 없습니다6초1024 MB지문만 제공
트리와 쿼리 19흰색과 검정색 정점으로 이루어진 루트 트리에서 정점 하나의 색을 바꿀 때마다 모든 흰색 정점 쌍의 LCA 레벨 합을 구하고, 초기 상태의 값도 출력한다.어려움9트리동적 계획법+2아직 제출이 없습니다5초512 MB지문만 제공
Neural Networks모든 노드가 1층에서 N층까지 가는 경로 위에 놓이는 층별 방향 그래프의 개수를 998244353으로 나눈 나머지를 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다4초1024 MB지문만 제공
Raid순열이 주어질 때, 각 k에 대해 크기 k인 부분집합의 역전 순서쌍 최솟값과 그 값을 달성하는 부분집합의 수를 구한다.어려움9동적 계획법조합론+2아직 제출이 없습니다3초768 MB지문만 제공
Pop musicm 이하의 증가하는 정수 n개를 골라 각 수의 이진 표현에서 1의 개수에 가중치 a_i를 곱한 합을 최대로 만든다.어려움9동적 계획법그리디+2아직 제출이 없습니다5초256 MB지문만 제공
Floyd-WarshallFloyd-Warshall의 반복 순서를 y, z, x로 바꾼 잘못된 구현이 희소 방향 가중 그래프에서 거리를 틀리게 계산하는 순서쌍의 수를 구한다.어려움9그래프최단 경로+2아직 제출이 없습니다5초256 MB지문만 제공
Abstract Circular Cover원 위 n개 점에 대해 모든 원형 구간의 비용이 주어질 때, 각 k마다 원을 정확히 k개 구간으로 분할하는 최소 총비용을 구한다.어려움9동적 계획법분할 정복+2아직 제출이 없습니다20초512 MB지문만 제공
Keep It Cool1<=a<b<=n인 모든 쌍 (a,b)의 순열 중 사이 조건과 m개의 순서 제약을 만족하는 것의 개수를 998244353으로 나눈 나머지를 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다1초512 MB지문만 제공
Dynamic Convex Hull삽입과 삭제가 있는 함수 집합 f_i(x)=(x-a_i)^4+b_i에서 주어진 x에 대한 최솟값을 구한다.어려움9세그먼트 트리분할 정복+2아직 제출이 없습니다4초512 MB지문만 제공
Stirling Numbern이 1e18까지, 소수 p가 1e6까지 주어질 때 l부터 r까지의 제1종 스털링 수 합을 p로 나눈 나머지를 구한다.어려움9수학조합론+2아직 제출이 없습니다9초256 MB지문만 제공
Towns and Roads열리고 닫히는 간선을 가진 트리에서 로봇이 열린 간선만 따라 이동하며, 각 질의 후 로봇 위치에서 가장 먼 마을을 모두 오름차순으로 출력한다.어려움9트리DFS+2아직 제출이 없습니다2초512 MB지문만 제공
Spaceship단추 번호가 더 큰 단추를 누른 뒤에만 같은 단추를 다시 쓸 수 있다는 규칙 아래, (s, b_s)에서 (t, b_t)로 가는 방과 단추 누름의 순서 열의 개수를 1e9+7로 나눈 나머지로 구한다.어려움9동적 계획법행렬+2아직 제출이 없습니다1초512 MB지문만 제공
Wind of Change 2020같은 N개 정점 위의 두 가중치 트리가 주어질 때, 모든 쌍 x, y에 대해 depth1(x)+depth1(y)-depth1(LCA1(x,y))-depth2(LCA2(x,y))의 최댓값을 구한다.어려움9트리분할 정복+2아직 제출이 없습니다12초1024 MB지문만 제공
Stabbing Number격자에 그려진 히스토그램 다각형을 직사각형으로 분할할 때, 임의의 수평 또는 수직 선분이 지나는 직사각형 내부 개수의 최댓값을 최소로 만드는 값을 구한다.어려움9기하동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
Hit the Hay아기의 수면 상태를 연속시간 마르코프 연쇄로 모델링하고, 고정된 알람 시각 전까지 부모가 얻을 수 있는 최대 기대 수면 시간을 구한다.어려움9확률동적 계획법+2아직 제출이 없습니다5초512 MB지문만 제공
Paris Escape마크는 0번 방에서 n-1번 방까지 정해진 경로로 이동하고 경찰관들은 각자 무작위로 걷는다. 같은 방에 동시에 있을 때마다 충돌로 세며, 기대 충돌 횟수를 최소로 하는 경로를 찾는다.어려움9그래프확률+2아직 제출이 없습니다2초512 MB지문만 제공
Caching approximations곡선 근사 생성 비용과 실행 비용을 모두 고려해 N개 연산의 총 작업 시간을 최소화하는 스케줄을 찾습니다.어려움9동적 계획법수학+1아직 제출이 없습니다2초256 MB지문만 제공
Rikka with Storehouse완전 이진 트리 마지막 절반 노드의 높이가 고정되어 있을 때 나머지 노드의 높이를 정해 모든 간선 높이 차의 제곱합을 최소화하고, 갱신마다 답을 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
Rikka with Generals번호가 인접한 장군끼리 도로로 이어진 도시를 교환할 수 있을 때, 처음 배정에서 도달 가능한 배정의 가짓수를 998244353으로 나눈 나머지로 구한다.어려움9그래프조합론+2아직 제출이 없습니다2초512 MB지문만 제공
Civilizations단일 칸의 소유자가 바뀔 때마다 각 문명의 재산과 국경 길이를 갱신하고, 매번 새로 주어지는 계수 A, B, C에 대해 A*w + B*l + C*w*l의 최댓값을 출력한다.어려움9구현해시맵+2아직 제출이 없습니다15초512 MB지문만 제공
Polygonal Query점 삽입으로 동적 볼록 껍질을 유지하면서, 껍질 위 두 정점 사이의 시계 방향 호와 반시계 방향 호 중 정점 수가 더 많거나 같은 쪽을 답한다.어려움9기하동적 계획법+2아직 제출이 없습니다1초512 MB지문만 제공
Game on a Tree각 노드에 색 카드가 놓인 트리에서 m번의 라운드마다 경로 위 색을 모든 참가자의 덱에 토글하고 GCD 기반 점수를 합산한 뒤 노드 하나의 색을 바꾼다.어려움9트리수학+2아직 제출이 없습니다5초512 MB지문만 제공
Final Exam시험 n개의 총 복습 시간이 M분을 넘지 않도록 배분해, 각 시험 점수가 이차함수를 자른 f_i(x)로 주어질 때 총점의 최댓값을 구한다.어려움9수학그리디+2아직 제출이 없습니다12초256 MB지문만 제공
Minimum Spanning Tree간선 가중치 1부터 m의 순열 중에서 처음 n-1개 간선이 주어진 다중 그래프의 최소 신장 트리를 이루는 경우의 수를 센다.어려움9최소 신장 트리조합론+2아직 제출이 없습니다1초256 MB지문만 제공
Colorful Componentsn개 정점에 색이 주어질 때, 서로 다른 색을 잇는 간선을 지운 뒤 남는 각 단색 연결 성분의 크기가 k 이하가 되도록 하는 연결 그래프(트리)의 개수를 세어 10^9+7로 나눈 나머지를 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
Number of Colorful Matchings이분 그래프의 완전 매칭을 사용한 빨간 간선 수에 따라 분류하고, 각 개수를 2로 나눈 나머지로 구한다.어려움9조합론행렬+2아직 제출이 없습니다2초512 MB지문만 제공
Jogging각 회차가 집에서 출발해 [L,U] 길이로 돌아오면서 이전에 지나지 않은 거리를 하나 이상 포함해야 할 때, 가능한 최대 일수를 구한다.어려움9그래프그리디+2아직 제출이 없습니다3초512 MB지문만 제공
Anagramistica서로 다른 n개의 단어 중에서, 부분집합 안의 애너그램 쌍 개수가 정확히 k인 부분집합의 수를 1e9+7로 나눈 나머지로 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다1초512 MB지문만 제공
Fireworks폭죽 하나를 만드는 데 n분이 걸리고 완벽할 확률은 p/10000이며, 완성된 폭죽을 모두 점화하는 데 m분이 들 때, 완벽한 폭죽이 하나 이상 나올 때까지 걸리는 최소 기대 시간을 구한다.어려움9확률수학+2아직 제출이 없습니다2초512 MB지문만 제공
Ascending Matrix각 항이 1부터 K까지이고 오른쪽과 아래로 단조 증가하며 한 칸의 값이 V로 고정된 N×M 행렬의 개수를 998244353으로 나눈 나머지로 구한다.어려움9조합론동적 계획법+1아직 제출이 없습니다2초1024 MB지문만 제공
Bit Operation0과 1로 이루어진 배열에서 인접한 두 원소를 AND 또는 OR로 합치는 연산을 N-1번 수행해 최종 값이 1이 되는 경우의 수를 998244353으로 나눈 나머지를 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다2초1024 MB지문만 제공
Find the LCA부모 p_i가 i보다 작은 N개 정점의 모든 루트 트리에 대해, 정점 N-1과 N의 최소 공통 조상 x를 루트로 하는 부분 트리에 속한 A_v의 곱을 모두 더해 998244353으로 나눈 나머지를 구한다.어려움9조합론수학+2아직 제출이 없습니다7초1024 MB지문만 제공
Games주어진 크기들로 서로 구별되는 K개의 돌 더미를 만드는 N^K가지 방법 중, 한 번에 최대 6개 더미에서 돌을 제거할 수 있는 님 변형 게임에서 선공이 지게 되는 초기 배치의 수를 센다.어려움9게임 이론동적 계획법+2아직 제출이 없습니다4초1024 MB지문만 제공
Japanese Knowledge비감소 수열 A가 주어질 때, 0 <= x_i <= A_i를 만족하고 x_i = A_i인 위치가 정확히 k개인 비감소 수열 x의 개수를 각 k마다 998244353으로 나눈 나머지로 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다10초512 MB지문만 제공
Solitaire chess6x6 보드의 말 종류가 주어질 때, 각 다음 제거가 직전 말의 이동 규칙을 따라야 한다는 조건 아래 제거 순서를 정하고 연쇄 보너스를 포함한 최고 점수를 구한다.어려움9동적 계획법그래프+2아직 제출이 없습니다1초1024 MB지문만 제공
Kingdom Division가중치가 있는 트리를 P명의 영주에게 나눠 줄 때, 각 부분이 연결되어 있고 값의 합이 모두 같도록 분할하는 문제입니다.어려움9트리동적 계획법+2아직 제출이 없습니다2초1024 MB지문만 제공
Вышивка жемчугом구슬 자수 그래프가 주어지고, 각 질의 직사각형 영역 안에서 연결 요소 개수를 세는 문제다. 그래프는 구슬을 차례로 붙여 만든 트리 구조다.어려움9그래프트리+2아직 제출이 없습니다2초1024 MB지문만 제공
Perfect Round Dancen개의 단짝 쌍마다 두 옷 번호가 주어질 때, 같은 옷을 입은 이웃이 자기 단짝일 때만 허용되는 원형 배치를 만들 수 있는 최대 단짝 쌍의 수와 그 순서를 구한다.어려움9그래프동적 계획법+2아직 제출이 없습니다1초512 MB지문만 제공
Таблица첫 행이 주어질 때 각 칸을 위쪽 삼각형 영역의 합을 r로 나눈 값으로 채우고 마지막 행을 출력한다.어려움9동적 계획법조합론+2아직 제출이 없습니다2초512 MB지문만 제공
Несчастливые номера0부터 k까지의 숫자로 만든 n자리 번호 중, 자릿수를 둘로 나눠 합이 같게 만들 수 없는 번호의 개수를 센다.어려움9동적 계획법조합론+1아직 제출이 없습니다1초512 MB지문만 제공
Inversion Statisticsn과 k가 주어질 때 inversion이 정확히 k개인 1부터 n까지의 순열 개수를 소수 10^6+3으로 나눈 나머지를 구합니다. n은 2*10^10까지 커질 수 있습니다.어려움9조합론수학+1아직 제출이 없습니다1초1536 MB지문만 제공
Worst Reporter 4x_i >= x_{A_i} 제약과 초깃값 H_i, 변경 비용 C_i가 주어질 때 모든 제약을 만족하도록 등급을 바꾸는 최소 비용을 구한다.어려움9그래프동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
Routing Schemes주어진 방향 그래프의 모든 간선을 정확히 한 번씩 사용하면서 송신자에서 수신자로 가는 S개의 서로소 경로를 만드는 경우의 수를 1e9+7로 나눈 나머지를 구한다.어려움9그래프동적 계획법+2아직 제출이 없습니다1초512 MB지문만 제공
Permutation기하 삽입 과정에서 각 단계마다 정확히 세 개의 선분이 추가되는 N개 점의 순열 개수를 센다.어려움9기하조합론+2아직 제출이 없습니다1초512 MB지문만 제공
Permutation Recovery숨겨진 순열의 각 접두사에서 증가 부분수열의 개수를 세어 준 배열이 주어질 때 원래 순열을 복원한다. N은 70000까지 커진다.어려움9동적 계획법조합론+2아직 제출이 없습니다1초512 MB지문만 제공
Double Move두 사람이 번갈아 n+1번 동안 돌 두 개씩을 선언하고, 무작위 시나리오가 각 선언에서 하나씩을 정할 때, 최적으로 플레이할 경우 각 플레이어가 이기는 시나리오 수를 구한다.어려움9게임 이론동적 계획법+2아직 제출이 없습니다5초512 MB지문만 제공
Dungeons Game각 던전에서 이기면 s[i]를 더하고 w[i]로, 지면 p[i]를 더하고 l[i]로 이동하는 게임 그래프가 주어질 때, 시작 던전과 힘이 주어지는 질의마다 게임이 끝날 때의 최종 힘을 구한다.어려움9그래프이분 탐색+2아직 제출이 없습니다4초2048 MB지문만 제공
Нанороботыw개의 나노로봇이 n×m 격자의 왼쪽 위 칸에서 시작하고 각 칸마다 동시에 수용할 수 있는 로봇 수가 정해져 있으며, 로봇은 분할만 가능하고 다시 합쳐지지 않을 때, 모든 로봇을 오른쪽 아래 칸으로 옮기는 데 필요한 서버 명령의 최솟값을 구한다.어려움9동적 계획법그래프+2아직 제출이 없습니다2초256 MB지문만 제공
Трисолианцы각 좌표의 합이 n인 k차원 나이 벡터에서 끝나는, 서로 다른 순증가 나이 벡터 사슬의 최대 개수를 소수 7340033으로 나눈 나머지를 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다2초256 MB지문만 제공
Truck각 간선에 통행료가 있는 가중치 트리에서 통행료 변경 갱신과, G개의 금과 통행료를 함께 옮길 때 드는 최소 연료를 경로마다 구해 1e9+7로 나눈 나머지를 출력한다.어려움9트리동적 계획법+2아직 제출이 없습니다1초512 MB지문만 제공
Tiles3×N 격자의 흰 칸에 겹치지 않게 도미노를 놓는 경우의 수를 구간마다 세고, 칸 색을 한 칸씩 뒤집는 갱신을 처리한다.어려움9동적 계획법세그먼트 트리+2아직 제출이 없습니다4초1024 MB지문만 제공
Impenetrable Wall문과 관측탑 일부를 꼭짓점으로 하여 집을 엄격히 내부에 포함하고, 탑 꼭짓점의 내각이 180도 미만이며, 집에서 벽 전체가 보이는 다각형의 개수를 센다.어려움9기하조합론+2아직 제출이 없습니다1초1024 MB지문만 제공
두 최단 경로음이 아닌 가중치를 가진 방향 그래프에서 각 정점 i마다 1번 정점에서 i로 가는 간선이 겹치지 않는 두 경로의 최소 비용 합을 구한다.어려움9그래프최단 경로+2아직 제출이 없습니다5초1024 MB지문만 제공
XOR 5N x N 흑백 이미지가 주어질 때, 흰 화면을 목표 이미지로 만드는 XOR 사각형 연산의 최소 횟수를 구하고 그 연산들의 매개변수를 출력한다.어려움9행렬그리디+2아직 제출이 없습니다1초512 MB지문만 제공
UCPC 만들기각 정점에 U, C, P가 적힌 트리에서 두 정점 사이 경로의 문자를 재배열해 UCPC의 반복 문자열을 만들 수 있는 순서쌍의 개수를 센다.어려움9트리DFS+2아직 제출이 없습니다3초1024 MB지문만 제공
Aggressive Traveller제한 국가에 입국할 때마다 여권 검사를 받으며, 같은 나라 도장이 두 번 찍히거나 도장 수가 제한을 넘으면 입국이 거부될 때 S에서 T까지 이동하며 얻을 수 있는 도장 수의 최댓값을 구한다.어려움9그래프최단 경로+2아직 제출이 없습니다2초512 MB지문만 제공
不思議なボタン방 1에서 시작해 방 d_j의 탈출 버튼을 누르며 코인을 정확히 e_j개 모으는 버튼 누름 순서의 가짓수를 구한다. 워프는 항상 번호가 큰 방으로 향하고 코인 1~3개를 준다.어려움9동적 계획법조합론+2아직 제출이 없습니다8초512 MB지문만 제공
土地相続H×W 격자를 겹치지 않는 최대 N개의 직사각형으로 나눠 형제들에게 분배할 때, 가장 낮은 직사각형 합을 최대로 만드는 값을 구한다.어려움9이분 탐색동적 계획법+2아직 제출이 없습니다10초512 MB지문만 제공
Stamp Rally간선마다 스탬프가 붙은 방향 다중 그래프에서 s에서 t로 가는 어떤 보행이 정해진 산술 BNF 문법에 맞는 문자열을 만드는지 판정한다.어려움9그래프동적 계획법+2아직 제출이 없습니다8초512 MB지문만 제공