cho.sh

문제

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

전체 결과문제 7376개
제목난이도유형정답자시간 제한메모리 제한채점
Long Distance Coach장거리 버스 여행에서 각 급수 지점마다 물을 얼마나 채울지 정해, 기사가 물 부족으로 멈추지 않으면서 물값과 승객 환불액의 합을 최소로 만든다.어려움9동적 계획법그리디+2아직 제출이 없습니다2초256 MB지문만 제공
Solitaire3×N 보드의 빈 칸을 채우는 순서의 수를 구한다. 어떤 칸은 위아래 칸이 모두 채워졌거나 좌우 칸이 모두 채워졌을 때만 놓을 수 있다. 경우의 수를 1e9+7로 나눈 나머지를 출력한다.어려움9동적 계획법조합론+2아직 제출이 없습니다4초512 MB지문만 제공
Building 3서로 다른 높이 순열에서 나올 수 있는 길이 N 수열 A 중, 한 원소를 지우면 주어진 수열 B가 되는 것의 개수를 구한다.어려움9동적 계획법조합론+2아직 제출이 없습니다1초512 MB지문만 제공
도로 정비N개 도시와 Q개의 계획 중 일부만 시행된 상황에서, 시행되지 않은 각 계획이 그 시점의 그래프에서 최단 경로 위의 미포장 도로를 몇 개 포장하게 되는지, 새 도로를 건설하면 -1을 구한다.어려움9그래프유니온 파인드+2아직 제출이 없습니다2초256 MB채점 가능
수열과 쿼리 32점 갱신이 있는 수열에서 각 구간의 xor이 주어진 작은 집합에 속하도록 전체를 분할할 수 있는지 판정한다.어려움9동적 계획법누적 합+2아직 제출이 없습니다10초512 MB채점 가능
수열과 쿼리 33부분 배열마다 서로 겹치지 않는 비어 있지 않은 연속 구간 k개를 골라 원소 합의 최댓값을 구한다.어려움9동적 계획법세그먼트 트리+1아직 제출이 없습니다5초512 MB지문만 제공
Train Tickets연도 구간이 주어질 때 첫 해 1월부터 마지막 해 12월까지 모든 달을 덮는 최소 티켓 비용을 구한다.어려움9동적 계획법분할 정복+1아직 제출이 없습니다2초512 MB지문만 제공
Ghost각 질의 시간 구간에서 일정한 속도로 움직이는 n개 직사각형의 교집합 넓이의 최댓값을 구한다.어려움9기하이분 탐색+2아직 제출이 없습니다10초512 MB지문만 제공
수열과 쿼리 36구간 [l,r] 안에서 최댓값과 최솟값의 차가 y-x인 부분 구간 [x,y]의 개수를 세는 쿼리에 답한다.어려움9세그먼트 트리분할 정복+2아직 제출이 없습니다1초512 MB지문만 제공
Be Geeks!모든 부분 배열에 대해 gcd와 최댓값의 곱을 더한 값을 1e9+7로 나눈 나머지를 구한다. N은 최대 2e5이다.어려움9수학정수론+2아직 제출이 없습니다2초512 MB채점 가능
Crimson Sexy Jalapeños초콜릿 바를 홈을 따라 두 조각으로 나눈 뒤 한 조각을 먹고, 오염된 칸이 든 조각을 먹는 사람이 지는 게임에서 이기는 수를 찾는 대화형 문제입니다.어려움9게임 이론동적 계획법+2아직 제출이 없습니다5초512 MB지문만 제공
Tiling with T-tetrominoesN 곱하기 M 격자를 T-테트로미노로 채우는 경우의 수를 998244353으로 나눈 나머지를 구한다. 회전과 뒤집기는 서로 다른 배치로 센다. N은 10^18까지, M은 15까지 주어진다.어려움9동적 계획법행렬+2아직 제출이 없습니다0.1초256 MB지문만 제공
정기 모임가중치 트리에서 두 정점 사이 거리를 경로 위 간선 가중치의 최댓값으로 정의할 때, 각 구간 [S,E]에 속한 정점들을 한 점 v로 모으는 최대 거리의 최솟값을 Q개의 질의마다 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
Draw in Straight Lines검은색과 흰색 픽셀로 이루어진 n x m 목표 그림과 선, 점 그리기 비용이 주어질 때, 덧칠 제한을 지키며 그림을 완성하는 최소 비용을 구한다.어려움9동적 계획법비트 연산+1아직 제출이 없습니다3초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채점 가능
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지문만 제공
Car washesn개의 세차장 각각에 가격을 정해, 각 고객이 예산 안에서 자신의 구간에서 가장 싼 세차장을 이용하도록 만들 때 총수입을 최대로 하는 가격을 구한다.어려움9동적 계획법구간+2아직 제출이 없습니다5초512 MB지문만 제공
Trips간선 가중치가 1에서 3인 방향 그래프에서 같은 마을이나 도로를 여러 번 지나도 되는 경로를 길이 순으로 나열할 때, k번째로 짧은 경로의 길이를 구하고 그러한 경로가 k개 미만이면 -1을 출력한다.어려움9그래프동적 계획법+2아직 제출이 없습니다2초512 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지문만 제공
Interesting Graph그래프의 임의의 7개 정점 중 두 정점이 바깥의 단절점을 지나야만 연결되도록 보장될 때, 1부터 n가지 색 각각으로 하는 적절한 색칠의 수를 구한다.어려움9그래프동적 계획법+2아직 제출이 없습니다5초512 MB지문만 제공
지식문자열 s에서 aa, bbb, ababab 블록을 넣거나 지우는 연산으로 길이가 x인 문자열을 만들 수 있는 경우의 수를 구해 998244353으로 나눈 나머지를 출력한다.어려움9문자열조합론+2아직 제출이 없습니다1초512 MB채점 가능
Disjoint LIS최장 증가 부분수열을 서로 원소를 공유하지 않는 두 개의 증가 부분수열로 나타낼 수 있는 n개 원소 순열의 개수를 998244353으로 나눈 나머지를 구한다.어려움9동적 계획법조합론+2아직 제출이 없습니다2초512 MB지문만 제공
One Goal정점 n개인 트리에서 모든 k-튜플에 대해 그 튜플의 1-중앙값 중 번호가 가장 작은 정점의 번호 합을 998244353으로 나눈 나머지를 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
Counting Cactus주어진 작은 그래프(n은 13 이하)에서 부분 그래프의 변 집합 가운데 연결되어 있고 모든 변이 많아야 하나의 단순 사이클에 속하는 것의 개수를 998244353으로 나눈 나머지를 구한다.어려움9동적 계획법그래프+2아직 제출이 없습니다2초512 MB지문만 제공
Grammarly문자열 s의 서로 다른 비어 있지 않은 부분 문자열을 정점으로 하고, a의 길이가 하나 짧은 부분 문자열 b로 향하는 간선을 둔 그래프에서 s에서 시작하는 단순 경로의 개수를 998244353으로 나눈 나머지를 구한다.어려움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지문만 제공
Seven Nevers순열에서 연속한 k개 원소를 지웠을 때 남은 수열의 최장 증가 부분 수열 길이를 모든 시작 위치마다 구한다.어려움9동적 계획법세그먼트 트리+2아직 제출이 없습니다2초512 MB채점 가능
하나의 실근|p|, |q| ≤ m인 정수 쌍 (p, q) 중에서 x^n + px + q가 실근을 정확히 하나 갖는 경우의 수를 센다.어려움9수학정수론+2아직 제출이 없습니다2초512 MB채점 가능
All Kill각 문제의 풀이 아이디어가 균등분포로 임의의 분에 도착할 때, 모든 문제를 연속된 구간으로 끝까지 코딩할 확률을 t^n배 하여 998244353으로 나눈 나머지를 구한다.어려움9확률조합론+2아직 제출이 없습니다1초512 MB지문만 제공
편집 거리 세기주어진 문자열 s와 레벤슈타인 거리가 정확히 d인 'A'부터 'Z'까지의 서로 다른 문자열 개수를 998244353으로 나눈 나머지를 구한다.어려움9동적 계획법문자열+2아직 제출이 없습니다10초512 MB채점 가능
Employees수용 인원이 k인 홀과 한 명만 작업하는 방에서 이루어지는 과정을 두 가지 방식으로 평가한 점수를 모든 순열에 대해 합산하고, 직원별로 두 점수를 곱해 10^9+7로 나눈 값을 구한다.어려움9조합론수학+2아직 제출이 없습니다2초512 MB지문만 제공
Count the Sequences0 ≤ x_i ≤ b^i - c이고 합이 n보다 작은 정수 수열 x_1, ..., x_m의 개수를 998244353으로 나눈 나머지로 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다1초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지문만 제공
기댓값 비용n개 정점의 레이블 트리를 균일하게 무작위로 고를 때, 한 정점에서 다른 모든 정점까지 거리 합의 최솟값에 대한 기댓값을 소수 모듈로로 구한다.어려움9조합론트리+2아직 제출이 없습니다3초512 MB채점 가능
Salty Fish도둑이 각 카메라의 감시 범위에서 사과를 훔칠 때, 잠글 카메라를 골라 비용을 지불하고 남는 이익이 최대가 되도록 하는 문제입니다.어려움9트리그리디+2아직 제출이 없습니다3초512 MB지문만 제공
Road Manager원형 격자에서 연속한 열 구간을 지운 뒤 남는 그래프의 최소 신장 트리 가중치를 각 질의마다 구한다. 간선 가중치는 주어진 난수 생성기로 만든다.어려움9최소 신장 트리그래프+2아직 제출이 없습니다4초512 MB지문만 제공
Minimum Spanning Trees각 정점 쌍이 독립적으로 간선이 없거나 1부터 k까지의 가중치를 확률적으로 가질 때, 그래프가 연결되어 있고 최소 신장 트리의 가중치가 주어진 s가 될 확률을 모든 s에 대해 구한다.어려움9조합론그래프+2아직 제출이 없습니다4초512 MB지문만 제공
Dense Subgraph차수가 5 이하인 트리에서, L 안에서 밀도가 최대인 연결 부분그래프의 밀도가 x 이하가 되는 부분집합 L의 개수를 세어 1e9+7로 나눈 나머지를 구한다.어려움9동적 계획법트리+2아직 제출이 없습니다3초512 MB지문만 제공
Bulbasaur층마다 k개의 구멍이 있는 방향 그래프에서 모든 층 쌍에 대해 서로 정점과 간선을 겹치지 않게 보낼 수 있는 최대 덩굴 수의 합을 구한다.어려움9그래프동적 계획법+2아직 제출이 없습니다6초512 MB지문만 제공
Eevee여러 순열을 교차 병합해 같은 돌이 k개 연속으로 나오지 않게 만드는 경우의 수를 모든 연속한 스택 구간에 대해 합해 1e9+7로 나눈 나머지를 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다5초512 MB지문만 제공
Alexey the Sage of The Six Pathsm개의 문제를 두 그룹에서 각각 한 명씩 배정하되, 구성원 i에게 c개가 배정되면 p[i][c]를 지불하고, 양쪽이 같은 문제를 고른 결과로 l개 이상 r개 이하가 풀리도록 최소 비용과 배정을 구한다.어려움9동적 계획법그리디+2아직 제출이 없습니다2초512 MB지문만 제공
그래프 세기N개 노드의 연결된 무방향 라벨 그래프 중 다리가 정확히 K개인 것의 개수를 합성수일 수 있는 M으로 나눈 나머지로 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
최고의 치킨 요리각 질의 구간 [L, R]과 값 D에 대해, [L, R] 안에서 GCD가 정확히 D인 연속 부분 배열의 개수를 센다.어려움9동적 계획법정수론+2아직 제출이 없습니다15초512 MB채점 가능
The Halfwitters각 시작 순열에서 인접 교환(비용 a), 전체 뒤집기(비용 b), 무작위 재배치(비용 c)를 써서 항등 순열에 도달하는 최소 기대 시간을 계산한다.어려움9동적 계획법그래프+2아직 제출이 없습니다5초512 MB채점 가능
Cyclic Distance가중치가 있는 트리에서 서로 다른 k개의 정점을 골라 한 바퀴 도는 경로의 총 길이가 최대가 되도록 할 때 그 최댓값을 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다3초512 MB지문만 제공
Fast as Ryser정점이 최대 36개인 무방향 그래프에서 서로 변을 공유하지 않는 변 집합 S에 대해 c^|S|의 합을 1e9+7로 나눈 나머지를 구한다.어려움9동적 계획법비트 연산+2아직 제출이 없습니다4초512 MB지문만 제공
Delegation (Platinum)트리의 간선을 경로들로 분할할 때 가능한 최소 경로 길이의 최댓값을 구한다.어려움9트리DFS+2아직 제출이 없습니다2초512 MB지문만 제공
Help Yourself (Platinum)N개의 구간으로 이루어진 모든 부분집합에 대해 합집합의 연결 성분 개수를 K제곱한 값의 합을 1e9+7로 나눈 나머지를 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
Legendary Dango Maker 3길이 3인 가로, 세로, 대각선 칸이 P-W-G 또는 G-W-P가 되도록 서로 겹치지 않게 최대한 많이 골라, 사용한 칸을 막대 방향 문자로 바꿔 격자를 출력한다.어려움9동적 계획법그리디+1아직 제출이 없습니다1초512 MB지문만 제공
Legendary Dango Maker 6P/W/G로 채워진 격자에서 가로, 세로, 대각선으로 연속한 세 칸을 한쪽 끝에서 읽어 PWG 또는 GWP가 되는 막대를 최대한 많이 고르고, 사용된 칸을 막대 방향 기호로 표시해 출력한다.어려움9동적 계획법구현+2아직 제출이 없습니다1초512 MB지문만 제공
집 떠나와 열차 타고가중 선인장 그래프에서 1번 정점에서 V번 정점으로 가는 경로가 없어지도록 지우는 간선 길이 합의 최솟값을 구하고, 불가능하면 권욱제 재입대를 출력한다.어려움9그래프DFS+2아직 제출이 없습니다3초1024 MB지문만 제공
풀 한 포기 친구 얼굴10개의 고정 명령 문자열이 주어질 때, 격자를 벗어나지 않고 (1,1)에서 (N,M)까지 도달하는 명령 번호 수열의 가짓수를 구하거나 무한히 많으면 -1을 출력한다.어려움9그래프동적 계획법+2아직 제출이 없습니다3초1024 MB지문만 제공
스프링클러 2: 알팔파의 귀환일부 칸이 막힌 N x N 격자에 옥수수 sprinkler와 alfalfa sprinkler를 놓아 모든 칸이 정확히 한 종류의 sprinkler로만 덮이도록 하는 경우의 수를 센다.어려움9동적 계획법누적 합+2아직 제출이 없습니다2초512 MB채점 가능
소의 체조N과 소수 M이 주어질 때, 모든 N!개 순열에 대해 각 순열의 위수(항등원이 될 때까지 반복한 횟수)를 곱한 값을 M으로 나눈 나머지를 구한다.어려움9조합론정수론+2아직 제출이 없습니다2초512 MB채점 가능
Circus트리 위에 K마리의 소를 서로 다른 정점에 배치할 때, 빈 인접 정점으로 소를 옮겨 서로 도달할 수 있는 배치들을 같은 부류로 묶는다. 각 K마다 배치 부류의 개수를 10^9+7로 나눈 나머지를 구한다.어려움9트리DFS+2아직 제출이 없습니다1초512 MB지문만 제공
소의 아침 운동N과 소수 M이 주어질 때, 길이 N인 순열의 위수가 K가 되는 모든 양의 정수 K의 합을 M으로 나눈 나머지를 구한다.어려움9수학정수론+2아직 제출이 없습니다1초512 MB채점 가능
남현욱길이 n인 순열 중 길이 3인 증가 부분 수열이 정확히 m개인 것들의 반전 수 합을 998,244,353으로 나눈 나머지를 구한다. 단, 0 ≤ m ≤ 3이다.어려움9조합론동적 계획법+1아직 제출이 없습니다2초1024 MB지문만 제공
Circles길이가 3 이상인 모든 접두사에 대해, 원형으로 x_i + x_{i+1} <= a_i를 만족하는 음이 아닌 x_i들의 합의 최댓값을 구한다.어려움9수학그리디+2아직 제출이 없습니다1초512 MB지문만 제공
데자 뷰배열에서 점 갱신이 일어나는 가운데, l 이후에서 시작하는 길이 4인 증가 부분수열을 끝내는 가장 작은 위치 d를 찾는 질의에 답한다.어려움9세그먼트 트리동적 계획법+2아직 제출이 없습니다5초512 MB채점 가능
Embeddings길이 10^6 이하의 문자열에서 서로 엄격히 포함되는 회문 부분문자열의 중첩 수열 개수를 998244353으로 나눈 나머지를 구한다.어려움9문자열동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
Fox Labeling무작위로 라벨을 찍는 과정을 반복해 n마리의 여우가 모두 서로 구별될 때까지 걸리는 기대 시간을 분 단위로 구한다.어려움9확률동적 계획법+1아직 제출이 없습니다3초512 MB지문만 제공
Empodia에 관한 또 다른 문제길이 i인 순열을 framed interval(최댓값과 최솟값의 차가 구간 길이에서 1을 뺀 값인 구간) 관계로 묶었을 때의 동치류 개수를 각 i마다 소수 P로 나눈 나머지로 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
왕들의 외나무다리 돌게임N개의 외나무다리마다 첫 칸에 흰 돌, 마지막 칸에 검은 돌을 놓고 자기 돌 하나를 상대 돌을 뛰어넘지 않고 빈 칸으로 옮기며, 움직일 돌이 없으면 지는 게임에서 최적으로 둘 때 이기는 왕을 판정한다.어려움9게임 이론동적 계획법+2아직 제출이 없습니다1초256 MB지문만 제공
트리 평균 가중치일부 차수가 자유로운 차수 수열이 주어질 때, 레이블 트리를 균등하게 무작위로 골라 가중치 u*sz(u)+v*sz(v)의 기댓값의 정수 부분을 구한다.어려움9조합론트리+2아직 제출이 없습니다1초256 MB채점 가능
Algebra on Segment소수 p와 배열이 주어질 때 구간 곱 갱신과 구간 원소들이 생성하는 부분군의 위수를 구하는 질의를 처리한다.어려움9정수론세그먼트 트리+2아직 제출이 없습니다10초512 MB지문만 제공
서로 다른 합mand 개수 세기양의 정수 n을 m개의 양의 정수 합으로 나타내는 모든 순서 있는 분할에 대해, 서로 다른 값의 개수 f를 모두 더한 값을 998244353으로 나눈 나머지를 구한다. n은 1e18까지, m은 500까지 주어진다.어려움9조합론수학+2아직 제출이 없습니다2초256 MB채점 가능
Gnutella Chessmastern x n 체스판에 k개의 비숍을 서로 공격하지 않게 놓는 경우의 수를 k = 1부터 2n-1까지 각각 998244353으로 나눈 나머지로 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다3초512 MB지문만 제공
Maximum Weighted Matching에지를 복사하고 세분화하는 과정으로 만들어진 그래프에서 최대 가중 매칭의 가중치 합과 그러한 최대 매칭의 개수를 10^9+7로 나눈 나머지를 구한다.어려움9동적 계획법트리+2아직 제출이 없습니다4초256 MB지문만 제공
Chiaki 수열 다시 보기자기 참조 수열 a_n = a_{n-a_{n-1}} + a_{n-1-a_{n-2}}의 처음 n개 항의 합을 10^9+7로 나눈 나머지를 구한다.어려움9수학조합론+2아직 제출이 없습니다1초256 MB채점 가능
Rikka with Equationm이 n 이하일 때 x^2+y^2≡a, xy≡b (mod m)를 만족하는 정수 x, y가 존재하는 (a,b,m)의 개수를 센다.어려움9정수론수학+1아직 제출이 없습니다2초512 MB지문만 제공
Rikka with Bridgesi와 j 사이에 간선이 없고 둘 모두 k와 인접한 경우 (i,j,k)를 브리지라 할 때, 브리지가 K개 이하인 n개 정점의 무방향 그래프 개수를 m으로 나눈 나머지를 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
Road Connectivity정점이 5개 이하인 완전 그래프에서 매일 간선 하나가 균등한 확률로 토글될 때, 각 날짜 구간 [l, r] 안에서 그래프가 연결되는 날이 존재할 확률을 구한다.어려움9확률행렬+2아직 제출이 없습니다2초256 MB지문만 제공
Good Gamen차원에서 원점부터 목표점까지 좌표가 비감소하는 경로 중 m개의 장애물을 지나지 않는 경로의 수를 10^9+7로 나눈 나머지를 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
Doublindromes길이가 k 이상이면서 팰린드롬이고 두 개의 비어 있지 않은 팰린드롬으로 나뉘는 s의 서로 다른 부분 문자열 개수를 센다.어려움9문자열문자열 매칭+2아직 제출이 없습니다3초512 MB채점 가능
택시가중치가 있는 트리에 M대의 택시와 M명의 손님을 배치하는 모든 경우에 대해, 최대 비용 완전 매칭의 총 거리 합을 10^9+7로 나눈 나머지를 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다1.5초256 MB채점 가능
Mikhail's Problem문자열과 구간 질의가 주어질 때, 각 구간에 포함된 서로 다른 회문 부분문자열의 개수를 구한다.어려움9문자열문자열 매칭+2아직 제출이 없습니다3초512 MB지문만 제공
Nice Numbers어떤 진법 d에서 자릿수가 0부터 d-1의 순열이 되는 수를 [L, R] 범위에서 세어 998244353으로 나눈 나머지를 구한다. L과 R은 최대 5000자리 정수이다.어려움9조합론정수론+2아직 제출이 없습니다1초512 MB채점 가능
K-matchingm이 4 이하인 n×m 격자 그래프에서 정확히 K개의 간선으로 이루어진 매칭의 최소 가중치 합을 구한다. n은 최대 40000이다.어려움9동적 계획법비트 연산+2아직 제출이 없습니다9초512 MB지문만 제공
주 사부와 도약자최대 100개의 장애물이 있는 거대한 격자에서 (1,1)에서 (n,m)까지 도약 말로 이동하는 단조 경로의 수를 110119로 나눈 나머지를 구한다.어려움9동적 계획법조합론+2아직 제출이 없습니다1초512 MB채점 가능
XOR의 거듭제곱n개의 정수가 주어질 때, 모든 2^n개 부분집합에 대해 부분집합 원소들의 XOR의 popcount의 k제곱을 합한 값을 1e9+7로 나눈 나머지를 구한다.어려움9비트 연산수학+2아직 제출이 없습니다6초512 MB채점 가능
Fulkerson트리가 주어질 때, 각 k에 대해 k개 정점을 골랐을 때 임의의 정점에서 가장 가까운 선택 정점까지의 최대 거리를 최소화한 값을 구해 N개의 값을 모두 출력한다.어려움9트리동적 계획법+2아직 제출이 없습니다5초512 MB지문만 제공
Joke텍스트와 최대 열 개의 패턴, 그리고 글자별 삭제 비용이 주어질 때, 어떤 패턴도 나타나지 않도록 글자를 지우는 최소 비용을 구한다.어려움9문자열 매칭동적 계획법+2아직 제출이 없습니다1초512 MB채점 가능
Strange Sequence "2"로 시작하는 look-and-say 수열의 n번째 항의 길이를 7340033으로 나눈 나머지를 구한다. n은 10^18까지 주어진다.어려움9동적 계획법행렬+1아직 제출이 없습니다2초512 MB지문만 제공
Game Relicsn개 렐릭의 개별 가격과 중복 시 절반을 환불하는 x 비용의 무작위 뽑기가 주어질 때, n개를 모두 모으는 데 드는 최소 기대 비용을 구한다.어려움9확률동적 계획법+2아직 제출이 없습니다3초512 MB지문만 제공
Konstrukcija꼭짓점 1000개와 간선 1000개 이하의 DAG를 만들어, 1번에서 N번으로 가는 모든 정렬 경로의 부호 합이 주어진 K(절댓값 10^18 이하)가 되도록 구성한다.어려움9그래프동적 계획법+2아직 제출이 없습니다1초512 MB지문만 제공
Masterpiecen×n 격자의 왼쪽 위에서 오른쪽 아래로 오른쪽/아래로만 간 뒤 왼쪽/위로만 되돌아오는 경로 중, 칠해진 칸 수가 주어진 각 행과 열의 값과 일치하는 경로의 수를 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
Enumeration of Tournamentsn명이 참가하는 단일 탈락 토너먼트에서 매 라운드 무작위로 대진을 정할 때 나타날 수 있는 서로 다른 경기 집합의 수를 2^64로 나눈 나머지를 구한다.어려움9조합론수학+2아직 제출이 없습니다1초256 MB지문만 제공
Fresh Matrixn행 m열(0과 1로 이루어진) 행렬 중에서 변을 공유하는 두 1이 없고 0인 칸들이 하나의 연결 영역을 이루는 행렬의 개수를 소수 p로 나눈 나머지를 구한다.어려움9동적 계획법행렬+2아직 제출이 없습니다6초256 MB지문만 제공
Lazy Studentk번의 시험 기회 동안 응시 사이에 합격 확률을 올릴 수 있을 때, 학생이 배워야 하는 주제 양의 최소 기댓값을 구한다.어려움9동적 계획법확률+2아직 제출이 없습니다1초256 MB지문만 제공
Knapsack and Queries무게가 항상 증가하는 쿠키를 넣고 가장 가벼운 쿠키를 빼는 연산을 반복하면서, 고른 무게 합을 MOD로 나눈 나머지가 [l, r]에 들어가는 최대 가치를 매번 구한다.어려움9동적 계획법세그먼트 트리+1아직 제출이 없습니다10초1024 MB지문만 제공
Short Random Problem각 간선 길이가 [0,1]에서 독립적으로 균등하게 정해지는 트리에서 지름의 기댓값을 1e9+7로 나눈 나머지로 구한다.어려움9트리확률+2아직 제출이 없습니다6초512 MB지문만 제공