cho.sh

문제

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

전체 결과문제 1332개
제목난이도유형정답자시간 제한메모리 제한채점
Classical Data Structure Problem크기 2^m인 배열에 n번의 구간 갱신을 수행한다. 각 단계에서 구간의 모든 원소에 단계 번호를 더하고, 배열이 변한 만큼 x를 누적한 뒤 최종 x를 2^30으로 나눈 나머지를 구한다.어려움8세그먼트 트리연결 리스트+2아직 제출이 없습니다3초128 MB지문만 제공
N-beatx×y 격자의 부분집합으로 이루어진 B개의 화면 수열 중 연속 1, 2, 3개 화면의 켜진 버튼 합이 각각 p1, p2, p3 이하인 경우의 수를 센다.어려움8동적 계획법행렬+2아직 제출이 없습니다3초1024 MB지문만 제공
점화식과 주기점화식 x_n = a x_{n-1} + b x_{n-2}를 소수 p로 나눈 나머지 수열에서, 모든 n >= S에 대해 x_{n+T} = x_n이 성립하는 가장 작은 (S, T)를 구한다.어려움8수학정수론+2아직 제출이 없습니다0.5초512 MB지문만 제공
Защитный узорn x m 흑백 격자에서 검은 칸이 4방향 인접으로 하나의 트리(연결이고 사이클 없음)를 이루도록 뒤집을 칸 수를 최소로 하는 배치를 찾는다.어려움8동적 계획법그래프+2아직 제출이 없습니다4초1024 MB지문만 제공
Макс и расстоянияn×n 거리 행렬이 주어질 때 이를 만들어 내는 비감소 정수 배열 x와 두 순열 a, b를 복원하거나 불가능함을 판정한다.어려움8그래프행렬+2아직 제출이 없습니다2초1024 MB지문만 제공
20481부터 16까지의 값으로 채운 h×w 격자 중 가로와 세로로 인접한 칸의 값이 다른 경우의 수를 구한다. h는 6 이하, w는 10^18 이하다.어려움8동적 계획법행렬+2아직 제출이 없습니다2초1024 MB지문만 제공
마라톤각 학생 j(벌점 j점)마다 1번에서 N번까지 정확히 j+1개의 체크포인트를 지나는 최소 시간을 구해 그 합을 998244353으로 나눈 나머지를 출력한다.어려움8그래프최단 경로+2아직 제출이 없습니다2초1024 MB지문만 제공
Бестинn 곱하기 m 격자 도시에서 벽을 하나씩 허물어 갈 때, 각 단계마다 내부가 완전히 연결되고 둘레가 벽으로 둘러싸인 최대 직사각형 구역의 수를 구한다.어려움8유니온 파인드구현+2아직 제출이 없습니다2초1024 MB지문만 제공
Таблица정수 격자가 주어질 때 행 전체나 열 전체의 부호를 뒤집어 모든 행 합과 열 합이 음수가 아니게 만들거나 불가능함을 판정한다.어려움8그리디수학+2아직 제출이 없습니다2초1024 MB지문만 제공
Soccer Stadium나무가 있는 칸이 섞인 N×N 격자에서, 경기장에 속한 임의의 두 칸을 가로 또는 세로 직선 킥 두 번 이내로 오갈 수 있게 하는 빈 칸 집합의 최대 크기를 구한다.어려움8행렬누적 합+2아직 제출이 없습니다3.5초1024 MB지문만 제공
Sales PredictionR차 점화식으로 정의된 수열에서 K개마다 하나씩 뽑아 처음 N개의 합을 1,000,000,007로 나눈 나머지를 구한다.어려움8수학행렬+2아직 제출이 없습니다10초1024 MB지문만 제공
Product Oriented Recurrencec의 거듭제곱 인수가 곱해지는 곱셈 점화식의 n번째 항을 10억 7로 나눈 나머지로 구한다. n은 10^18까지다.어려움8수학정수론+2아직 제출이 없습니다1초1024 MB지문만 제공
쿼리는 락이 아니다문자열의 한 글자를 바꾸는 갱신이 있을 때 구간 안에서 ROCK과 같은 부분열의 개수를 세어 1e9+7로 나눈 나머지를 구한다.어려움8세그먼트 트리동적 계획법+2아직 제출이 없습니다2초1024 MB지문만 제공
Color Inversion on a Huge Chessboard체스판 색배치에서 시작해 행 또는 열의 색을 뒤집는 연산을 순서대로 적용하면서, 매 연산 후 같은 색으로 이어진 영역의 개수를 구한다.어려움8유니온 파인드행렬+2아직 제출이 없습니다4초1024 MB지문만 제공
순찰 업무육각 격자의 모든 칸을 주기 K에 맞춰 한 번씩 방문하는 길이 K*M의 경로를 찾거나 불가능을 판정한다.어려움8구현시뮬레이션+2아직 제출이 없습니다3초1024 MB지문만 제공
Square Grid Puzzle서로 다른 정수로 채워진 N x N 격자에서 위쪽 행이나 왼쪽 열을 떼어 순서를 바꿔 반대쪽 끝에 붙이는 연산만으로 행 우선 정렬 상태에 도달하는 방법을 찾는다.어려움8시뮬레이션구현+2아직 제출이 없습니다1초1024 MB지문만 제공
Transformer Knight's Tour4×N 격자의 왼쪽 위 칸에서 출발해 나이트와 퍼즈 이동을 번갈아 쓰며 모든 칸을 한 번씩 방문하고 제자리로 돌아오는 경로의 수를 1e9+7로 나눈 나머지를 구한다.어려움8동적 계획법조합론+1아직 제출이 없습니다3초1024 MB지문만 제공
Magic Cubex, y, z축을 기준으로 일부 층을 누적해서 회전시키면서 n x n x n 큐브의 각 칸에 있는 번호를 관리하고, 질의한 위치의 번호를 출력한다.어려움8구현시뮬레이션+2아직 제출이 없습니다1초2048 MB지문만 제공
하늘아 군대 잘 가고M명의 부원을 K초 동안 순서대로 배정해, 각 전구의 스위치 조작을 모두 합쳤을 때 N개의 전구가 처음의 꺼짐 상태로 돌아오는 배정 방법의 수를 구한다.어려움8행렬동적 계획법+2아직 제출이 없습니다0.5초1024 MB지문만 제공
현대모비스 자율 주행 테스팅 22행짜리 샘플 트랙 M종류와 그것을 이어 붙인 순서 K개가 주어질 때, 이어 붙인 2행 트랙의 첫 열 도로 칸에서 마지막 열 도로 칸까지 이동할 수 있는지 판정하고 최소 이동 횟수 또는 -1을 출력합니다. 이때 한 샘플 트랙의 상태 전이를 행렬로 압축해 이어 붙이는 것이 핵심입니다.어려움8동적 계획법행렬+1아직 제출이 없습니다1초1024 MB지문만 제공
Revenge각 질의마다 인덱스 구간 [a,b]의 간선만 사용해 u에서 v로 가는 최소 비용을 구한다. 간선을 건너뛰면 거부 비용이 든다.어려움8동적 계획법최단 경로+2아직 제출이 없습니다1초1024 MB지문만 제공
A Bug That's Not a Pill Bug격자 위의 벌레가 장애물을 만나면 왼쪽으로 돌며 이동할 때, 최대 10^18칸 이동한 뒤의 위치를 구한다.어려움8시뮬레이션행렬+1아직 제출이 없습니다8초1024 MB지문만 제공
Five배열에 구간 덧셈을 하고, 계수 5,4,3,2,1인 선형 점화식 x_k의 구간 합을 구한다.어려움8세그먼트 트리동적 계획법+2아직 제출이 없습니다0.7초1024 MB지문만 제공
배고픈 무토를 위한 피자 만들기격자 밖에서 행이나 열에 밀어넣기와 당기기를 반복해, 처음 놓인 미트볼 하나에서 목표한 N×N 배치를 2N²번 이하의 동작으로 완성하는 방법을 출력한다.어려움8구현시뮬레이션+2아직 제출이 없습니다1초1024 MB지문만 제공
바이러스비트열이 범위 갱신될 때마다 전체 문자열이 정규 표현식 (1(10)+1*|0+10)+에 맞는지 판정한다.어려움8세그먼트 트리문자열 매칭+2아직 제출이 없습니다2초1024 MB지문만 제공
Lexicopolis방향 그래프와 매우 큰 k가 주어질 때 s에서 t로 가는 길이 k 경로 중 간선 가중치 기준 사전순 최소 경로를 찾고, 없으면 -1을 출력하며, 있으면 x진법 해시를 1e9+7로 나눈 값을 출력한다.어려움8그래프그리디+2아직 제출이 없습니다2초1024 MB지문만 제공
Mosaic3x3 검은 칸 개수를 담은 R x C 행렬이 주어질 때 이를 만들어 내는 흑백 그림을 하나 복원하거나, 존재하지 않으면 0을 출력한다.어려움8그리디구현+2아직 제출이 없습니다2초1024 MB지문만 제공
세 트리중복 간선과 루프가 있는 그래프에서 각 간선에 0, 1, 2, 3을 붙여 1, 2, 3번 간선이 각각 스패닝 트리를 이루도록 하거나 불가능함을 판정한다.어려움8유니온 파인드그래프+2아직 제출이 없습니다0.5초1024 MB지문만 제공
ZOAC 7Z, O, A, C로 이루어진 N행 M열 격자에서 (1,1)에서 시작해 오른쪽이나 아래로만 이동하고 순간이동을 한 번 사용할 때, 각 문자의 수집 개수의 최댓값을 구한다.어려움8동적 계획법누적 합+2아직 제출이 없습니다2초1024 MB지문만 제공
Palindromic Word Search어떤 행 전체가 회문이고 어떤 열 전체도 회문인 부분 직사각형 중 넓이가 최대인 것을 찾는다.어려움8동적 계획법행렬+1아직 제출이 없습니다6초1024 MB지문만 제공
Sonic 3 & Knuckles 2N x M 격자에서 막힌 칸을 피하고 반대 방향 연속 이동을 하지 않으며 모든 파란 공을 제거하는 이동 문자열을 찾습니다.어려움8시뮬레이션백트래킹+2아직 제출이 없습니다1초1024 MB지문만 제공
Combination Lock3-다이얼과 5-다이얼이 체커판처럼 놓인 격자에서 목표 값을 만족하도록, 한 번의 이동이 칸과 상하좌우 이웃을 증가시킬 때 20nm 이하의 이동 순서를 찾는다.어려움8수학구현+2아직 제출이 없습니다1초1024 MB지문만 제공
Virtual Reality Playspace장애물이 있는 격자에서 각 변이 벽이나 장애물에 닿고 두 변의 길이가 s, t 이상인 빈 직사각형의 개수를 센다.어려움8스택구현+2아직 제출이 없습니다4초2048 MB지문만 제공
점화식과 쿼리초기 두 항과 n^k 항이 포함된 선형 점화식이 주어질 때, n이 10^18까지 커질 수 있는 최대 50000개의 질의에 대해 x_n을 100003으로 나눈 나머지를 구한다.어려움8수학동적 계획법+2아직 제출이 없습니다3초1024 MB지문만 제공
문자 인식여러 개의 작은 0과 1 격자 패턴이 하나의 큰 질의 격자 안에 부분 격자로 등장하는지 모두 찾아 그 번호를 출력한다.어려움8문자열 매칭해시맵+2아직 제출이 없습니다5초1024 MB지문만 제공
Parking Theory각 칸에 차량의 진입 순서가 서로 다르게 주어진 n x m 격자에서, 모든 차가 이미 주차된 차를 지나지 않고 행이나 열의 끝에서 곧장 들어와 설 수 있는 부분격자의 수를 센다.어려움8구현동적 계획법+2아직 제출이 없습니다1초2048 MB지문만 제공
Distribution Center밀어서 목적지에 도달할 수 없는 모든 칸을 표시한다. 미는 사람은 어디에든 있을 수 있다고 가정한다.어려움8BFS그래프+2아직 제출이 없습니다4초2048 MB지문만 제공
Hardcore String Counting길이 m인 소문자 문자열 가운데 주어진 패턴 s가 마지막 문자에서 처음 나타나는 문자열의 개수를 998244353으로 나눈 나머지로 구한다. n은 10^5, m은 10^9까지 주어진다.어려움8문자열 매칭동적 계획법+2아직 제출이 없습니다8초2048 MB지문만 제공
Digit DP부분집합 합으로 정의된 0부터 2^n-1까지의 배열에서 구간 덧셈과 세 원소 곱의 합을 구하는 구간 질의를 처리한다.어려움8세그먼트 트리분할 정복+2아직 제출이 없습니다5초2048 MB지문만 제공
Junctions완전 가중 그래프가 인접 행렬로 주어질 때, 어떤 두 정점 사이의 모든 최단 경로가 반드시 지나는 간선 (i,j)를 찾아 표시한다.어려움8그래프최단 경로+1아직 제출이 없습니다2초2048 MB지문만 제공
[F] Functional SequenceB = f^K(A)이고 f가 대각 차분 D_i = A_i - A_{i-1}을 읽을 때, 가능한 A를 1e9+7로 나눈 나머지로 복원한다.어려움8수학조합론+2아직 제출이 없습니다1초1024 MB지문만 제공
행렬과 쿼리행과 열을 추가하거나 제거하고 특정 원소를 바꿀 수 있는 2x2 행렬 수열에서 구간 곱을 10^9+9로 나눈 나머지를 구한다.어려움8세그먼트 트리행렬+1아직 제출이 없습니다1초1024 MB지문만 제공
지형 평탄화 탐색기격자에서 한 점의 고도를 수정하는 갱신이 반복되는 가운데, 주어진 작은 작업 계획도를 겹쳤을 때 창 안의 모든 고도가 같아지는 위치의 개수를 센다.어려움8해시맵행렬+2아직 제출이 없습니다5초1024 MB지문만 제공
벨과 와이즈의 가게 홍보순열이 주어질 때, 양 끝을 제외한 위치 중 봉우리도 골짜기도 아닌 위치 수의 최댓값과, 그 최댓값에 도달하는 최소 교환 횟수를 구한다.어려움8그리디행렬아직 제출이 없습니다1초1024 MB지문만 제공
크로스링크격자 네 변에 모두 닿고 연결된 땅 집합을 만들기 위해 새로 배치할 칸 비용의 최솟값을 구한다.어려움8동적 계획법최단 경로+2아직 제출이 없습니다1.5초1024 MB지문만 제공
조화로운 사각형네 원소로 채워진 N×M 격자에서 Q번의 직사각형 온도 또는 습도 반전이 일어날 때마다 네 원소가 모두 있는 2×2 사각형의 수를 구한다.어려움8행렬구현+1아직 제출이 없습니다2초1024 MB지문만 제공
드래곤볼: MatKor Cup 없애기무작위 과정을 거쳐 P일째와 M일째에 일곱 공이 목표 상태가 되거나 1성구부터 7성구까지 하나씩 존재할 확률을 각각 구한다.어려움8확률행렬+2아직 제출이 없습니다0.7초1024 MB지문만 제공
극대 찾기숨겨진 N×N 순열에서 세로·가로 구간 최댓값 질의를 최대 27번 사용해 극대점 하나를 찾는다.어려움8이분 탐색분할 정복+1아직 제출이 없습니다1초1024 MB지문만 제공
타카하시의 기차 퍼즐 놀이 2높이가 짝수이고 6 이하인 직사각형을 네 가지 고정 블록으로 빈틈없이 채우는 경우의 수를 구해 10^9+7로 나눈 나머지를 출력한다.어려움8동적 계획법행렬+1아직 제출이 없습니다1.5초512 MB지문만 제공
직사각형 채우기N x M 격자에 1부터 NM/4까지의 수를 각각 네 번씩 축에 평행한 직사각형의 네 꼭짓점에 놓아 직사각형 넓이의 합이 최대가 되게 배치한다.어려움8그리디구현+2아직 제출이 없습니다1초1024 MB지문만 제공
Server Room빈 칸, 꺼진 서버, 켜진 서버로 이루어진 격자에서 인접한 두 서버가 동시에 켜지지 않도록 꺼진 서버를 최대한 켜고, 그 최대 개수를 이루는 방법의 수를 998244353으로 나눈 나머지를 구한다.어려움8동적 계획법비트 연산+2아직 제출이 없습니다5초2048 MB지문만 제공
행렬 교환0과 1로 이루어진 행렬 A를 행렬 B로 바꾸는 데 필요한 최소 인접(대각선 포함) 교환 횟수를 셀별 사용 한도 행렬 C 아래에서 구하는 문제입니다.어려움9그래프최단 경로+2아직 제출이 없습니다2초128 MB채점 가능
모든 순환 이동 길이방향 그래프에서 각 길이 x마다 닫힌 보행이 존재하는지 판별한 뒤, 결국 주기적인 0/1 수열을 비반복 구간과 반복 구간 길이의 합이 최소가 되도록 표현합니다.어려움9그래프행렬+2아직 제출이 없습니다2초128 MB채점 가능
구역 나누기(n+1)x(m+1) 인구 격자에서 가로 도로 X개와 세로 도로 X개를 골라 나눈 구역들 중 최대 인구를 최소화하는 문제입니다.어려움9이분 탐색그리디+2아직 제출이 없습니다2초128 MB채점 가능
도미노 덮기일부 칸 사이에 선이 그려진 N행 M열 격자를 도미노로 빈틈없이 덮는 배치 중 사전순으로 가장 작은 것을 구하거나 불가능하면 -1을 출력합니다.어려움9그래프BFS+2아직 제출이 없습니다5초128 MB채점 가능
과수원겹치지 않는 최대 2500개의 색칠된 직사각형 과수원이 주어질 때, 한 가지 과일로만 완전히 채워지는 최대 넓이의 축 정렬 직사각형을 구합니다.어려움9기하행렬+2아직 제출이 없습니다2초64 MB채점 가능
행렬과 피보나치 수의 합지수가 등차수열로 커지는 피보나치 수와 행렬 거듭제곱의 곱을 N이 10^1000까지 갈 수 있는 경우에 대해 소수 모듈로로 합산하는 문제입니다.어려움9행렬수학+2아직 제출이 없습니다5초512 MB채점 가능
표준 문제0과 1로 이루어진 표에서 최대 백만 개의 질의마다 지정된 행 범위 안에 있는 최대 크기의 0 사각형 면적을 구합니다.어려움9세그먼트 트리분할 정복+2아직 제출이 없습니다3초128 MB채점 가능
좋은 접두사길이 L인 문자열 중 모든 접두사에서 각 문자의 등장 횟수 차이가 2 이하인 문자열의 개수를 K와 함께 세어 1e9+7로 나눈 나머지를 구한다. L은 10^18까지 커진다.어려움9동적 계획법조합론+2아직 제출이 없습니다1초128 MB채점 가능
그라디언트 광산 찾기회색조 격자가 주어질 때 값이 세로, 가로, 또는 대각선 방향으로 균일하게 변하는 가장 큰 정사각형 부분 격자를 찾아 그 넓이를 출력한다.어려움9동적 계획법구현+2아직 제출이 없습니다10초128 MB채점 가능
켜지고 꺼지는 불빛들조명 격자에서 k번째 행 옆 버튼을 누르면 바로 위 행과 XOR되고, 임의의 부분집합과 순서로 눌렀을 때 나타날 수 있는 맨 아래 행 패턴의 가짓수를 센다.어려움9비트 연산수학+2아직 제출이 없습니다1초128 MB채점 가능
고속도로각 도시가 다음 도의 도시로만 향하는 단방향 고속도로망에서 차선 수가 수시로 바뀔 때, 두 도시 사이 경로의 수를 d로 나눈 나머지를 구한다.어려움9행렬세그먼트 트리+1아직 제출이 없습니다1초128 MB채점 가능
덮어쓰기 게임좌상단 prefix 직사각형을 무작위로 덧칠해 목표 배치와 처음 일치할 때까지 칠한 칸 수의 기댓값을 기약분수로 구합니다.어려움9확률행렬+1아직 제출이 없습니다8초512 MB채점 가능
업적의 노예 2N개 재료로 단도를 최대한 만들고 단도마다 0개부터 K개까지 재료를 무작위로 회수하는 과정을 반복한 뒤 N개 미만으로 남은 재료의 분포를 구합니다.어려움9확률동적 계획법+1아직 제출이 없습니다3초256 MB채점 가능
Watering - 75R 곱하기 5C 격자에서 허수아비가 없는 모든 칸을 세 칸짜리 스프링클러로 덮고, 울타리에 뚫는 구멍 수를 줄이도록 배치를 출력한다.어려움9구현완전 탐색+2아직 제출이 없습니다1초128 MB지문만 제공
문자열의 개수길이가 L*K 이상 L*K+N 이하이고 주어진 패턴 S가 서로 겹치지 않게 최대 K번만 나타나는 소문자 문자열의 개수를 센다.어려움9동적 계획법문자열 매칭+2아직 제출이 없습니다2초512 MB채점 가능
보행의 개수인접 행렬로 주어진 방향 그래프에서 길이 L인 보행의 수가 O(L^K)로 증가하는 최소 K를 구하고, 그런 K가 없으면 -1을 출력합니다.어려움9그래프동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
이것도 해결해 보시지N x L 행렬에서 3N열 구간을 A, B, C 세 개의 N x N 행렬로 나눠 A*B=C가 성립하는 구간들을 서로 겹치지 않게 골라 칠한 칸 수의 최댓값을 구한다.어려움9행렬동적 계획법+2아직 제출이 없습니다5초512 MB채점 가능
격납고 화물 운반막힌 칸과 빈 칸으로 이루어진 n x n 격자에서 두 빈 칸 사이를 이동할 수 있는 가장 큰 정사각형 상자의 크기를 묻는 q개의 질의에 답한다.어려움9유니온 파인드BFS+2아직 제출이 없습니다8초512 MB채점 가능
NPM998244353 (Hard)0부터 MM까지의 각 자릿수 합 상한에 대해, P로 나누어떨어지는 길이 N의 숫자열 개수를 998244353으로 나눈 나머지로 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다5초512 MB채점 가능
자릿수 합이 제한된 배수 세기길이가 N인 숫자열 가운데 P로 나누어떨어지고 자릿수의 합이 M 이하인 것의 개수를, 각 M마다 998244353으로 나눈 나머지로 구한다.어려움9동적 계획법조합론+2아직 제출이 없습니다2초512 MB채점 가능
블록 2N x M 직사각형을 1 x N부터 N x N까지의 블록으로 빈틈없이 채우는 방법의 수를 1999로 나눈 나머지를 구한다. M은 10^10까지 커질 수 있다.어려움9조합론동적 계획법+2아직 제출이 없습니다1초256 MB채점 가능
TV 동물 농장n마리의 개와 m마리의 고양이 사이 호감도 행렬이 주어질 때, 인접한 두 관계를 뒤집는 두 가지 작업만으로 목표 상태를 만들 수 있는지 판정하고 최소 횟수의 작업 순서를 출력한다.어려움9수학그리디+2아직 제출이 없습니다2초512 MB지문만 제공
Superstition가중 무방향 그래프에서 총 이동 시간이 K 이하이면서 D로 나누어떨어지는 경로의 수를 1,000,000,007로 나눈 나머지를 구한다.어려움9그래프행렬+2아직 제출이 없습니다2초512 MB지문만 제공
Ranks이진 행렬이 주어질 때 각 원소를 뒤집었을 때 F2 위에서 계수가 감소하는지, 같은지, 증가하는지를 판별해 출력한다.어려움9수학행렬+2아직 제출이 없습니다3초512 MB지문만 제공
색 타일 2주어진 1×1과 1×2 타일을 H×W 판에 겹치지 않게 배치해 인접한 타일 사이 점수 합이 최대가 되도록 하고, 각 타일의 좌표를 출력한다.어려움9동적 계획법구현+2아직 제출이 없습니다1초512 MB채점 가능
메시지길이 n인 소문자 문자열 가운데 주어진 패턴 p를 부분 문자열로 포함하는 것의 개수를 m으로 나눈 나머지를 구한다. n은 10^12까지, p의 길이는 최대 50이다.어려움9동적 계획법문자열 매칭+2아직 제출이 없습니다5초512 MB채점 가능
연결그래프의 모든 간선의 저항이 1Ω일 때, 간선으로 직접 이어진 모든 점 쌍 A, B 사이 합성저항 값의 총합을 구해 소수점 넷째 자리에서 반올림한 값을 출력하는 문제모든 간선의 저항이 1인 연결 그래프에서 각 간선 양 끝점 사이의 등가 저항을 모두 더한 값을 소수점 셋째 자리까지 반올림해 구한다.어려움9그래프행렬+2아직 제출이 없습니다1초512 MB채점 가능
Magic Chessboard고정된 위치를 기준으로 하는 직사각형 영역의 최대공약수를 구하는 질의와, 임의의 직사각형 영역에 같은 값을 더하는 갱신을 함께 처리한다. N 곱하기 M은 500000 이하이고 연산 수는 100000 이하이다. 문제에서 주어진 조건만으로 판단할 때 2차원 GCD 세그먼트 트리와 차분 배열을 결합해야 하는 매우 어려운 문제이다. 인터뷰 문제가 아니라 대회용 고난도 문제에 해당한다. 19930324 같은 특수한 숫자는 정답 횟수와 관련된 장치일 뿐 알고리즘에는 영향을 주지 않는다. 갱신이 값을 더하는 형태이므로 GCD의 차분 성질을 이용해야 한다. 각 행과 열에 대해 차분 배열을 관리하고 GCD 세그먼트 트리로 구간 GCD를 유지하는 방식이 필요하다. 쿼리 영역이 고정된 위치를 기준으로 확장되므로 그 점을 활용한 최적화가 가능하다. 난이도는 9로 평가한다.어려움9세그먼트 트리정수론+2아직 제출이 없습니다5초512 MB지문만 제공
일하는 세포주기 T로 반복되는 N개 허브의 가중 유방향 그래프가 주어질 때, 모든 허브 i에서 출발해 정확히 D초 후 허브 j에 도착하는 경로의 수를 1,000,000,007로 나눈 나머지로 각각 구한다.어려움9행렬분할 정복+2아직 제출이 없습니다1초512 MB채점 가능
수열과 쿼리 33부분 배열마다 서로 겹치지 않는 비어 있지 않은 연속 구간 k개를 골라 원소 합의 최댓값을 구한다.어려움9동적 계획법세그먼트 트리+1아직 제출이 없습니다5초512 MB지문만 제공
Train Tickets연도 구간이 주어질 때 첫 해 1월부터 마지막 해 12월까지 모든 달을 덮는 최소 티켓 비용을 구한다.어려움9동적 계획법분할 정복+1아직 제출이 없습니다2초512 MB지문만 제공
Tiling with T-tetrominoesN 곱하기 M 격자를 T-테트로미노로 채우는 경우의 수를 998244353으로 나눈 나머지를 구한다. 회전과 뒤집기는 서로 다른 배치로 센다. N은 10^18까지, M은 15까지 주어진다.어려움9동적 계획법행렬+2아직 제출이 없습니다0.1초256 MB지문만 제공
체스판 이동N×M 체스판에서 홀수 행은 같은 색 인접 칸으로만, 짝수 행은 색 제약 없이 인접 칸으로 이동할 수 있을 때 1행에서 N행에 도착하는 경로의 수를 10^9+7로 나눈 나머지를 구한다.어려움9동적 계획법행렬+2아직 제출이 없습니다2초512 MB채점 가능
착한 말 나쁜 말N×N 격자의 각 세균이 직교 이웃으로 한 칸 이동하는 데 a, 좋은 칸에서 체비쇼프 거리 D 이내로 뛰는 데 b의 에너지가 들 때, 각 회의 칸마다 모든 세균이 모이는 최소 총에너지를 구한다.어려움9최단 경로그래프+2아직 제출이 없습니다2.5초1024 MB채점 가능
모듈로 마방진각 행, 각 열, 두 대각선의 합이 모두 같은 상수와 합동이 되는 Z_m 위의 n x n 행렬의 개수를 n과 m이 10^9까지일 때 센다.어려움9수학조합론+2아직 제출이 없습니다1초512 MB채점 가능
Bulbasaur층마다 k개의 구멍이 있는 방향 그래프에서 모든 층 쌍에 대해 서로 정점과 간선을 겹치지 않게 보낼 수 있는 최대 덩굴 수의 합을 구한다.어려움9그래프동적 계획법+2아직 제출이 없습니다6초512 MB지문만 제공
Knowledge-Oriented Problem그래프를 k번 복사하고 연속한 복사본의 같은 정점끼리 연결한 그래프에서 신장 트리의 개수를 10^9+7로 나눈 나머지를 구한다.어려움9그래프행렬+2아직 제출이 없습니다5초512 MB지문만 제공
Legendary Dango Maker 6P/W/G로 채워진 격자에서 가로, 세로, 대각선으로 연속한 세 칸을 한쪽 끝에서 읽어 PWG 또는 GWP가 되는 막대를 최대한 많이 고르고, 사용된 칸을 막대 방향 기호로 표시해 출력한다.어려움9동적 계획법구현+2아직 제출이 없습니다1초512 MB지문만 제공
풀 한 포기 친구 얼굴10개의 고정 명령 문자열이 주어질 때, 격자를 벗어나지 않고 (1,1)에서 (N,M)까지 도달하는 명령 번호 수열의 가짓수를 구하거나 무한히 많으면 -1을 출력한다.어려움9그래프동적 계획법+2아직 제출이 없습니다3초1024 MB지문만 제공
Road Connectivity정점이 5개 이하인 완전 그래프에서 매일 간선 하나가 균등한 확률로 토글될 때, 각 날짜 구간 [l, r] 안에서 그래프가 연결되는 날이 존재할 확률을 구한다.어려움9확률행렬+2아직 제출이 없습니다2초256 MB지문만 제공
K-matchingm이 4 이하인 n×m 격자 그래프에서 정확히 K개의 간선으로 이루어진 매칭의 최소 가중치 합을 구한다. n은 최대 40000이다.어려움9동적 계획법비트 연산+2아직 제출이 없습니다9초512 MB지문만 제공
Strange Sequence "2"로 시작하는 look-and-say 수열의 n번째 항의 길이를 7340033으로 나눈 나머지를 구한다. n은 10^18까지 주어진다.어려움9동적 계획법행렬+1아직 제출이 없습니다2초512 MB지문만 제공
Fresh Matrixn행 m열(0과 1로 이루어진) 행렬 중에서 변을 공유하는 두 1이 없고 0인 칸들이 하나의 연결 영역을 이루는 행렬의 개수를 소수 p로 나눈 나머지를 구한다.어려움9동적 계획법행렬+2아직 제출이 없습니다6초256 MB지문만 제공
Multi-stage Marathon각 플레이어가 진출 간선으로 균등하게 이동하는 유향 그래프 위의 확률 보행에서, 시각 1부터 T까지 정점 n에 있는 플레이어 기대 수의 XOR을 구한다.어려움9그래프행렬+2아직 제출이 없습니다3초512 MB지문만 제공
행렬과 쿼리N x N 정수 행렬 A와 Q개의 x가 주어질 때 각 x에 대해 det(A - xI)를 998244353으로 나눈 나머지를 구한다.어려움9수학행렬+2아직 제출이 없습니다5초512 MB채점 가능
SemaforM개의 5세그먼트 디스플레이에서 K번째 이동마다 유효한 숫자가 되도록 세그먼트를 켜고 끄는 이동 순서의 수를 각 최종 숫자별로 10^9+7로 나눈 나머지를 구한다.어려움9동적 계획법행렬+2아직 제출이 없습니다4초512 MB지문만 제공
Spaceship단추 번호가 더 큰 단추를 누른 뒤에만 같은 단추를 다시 쓸 수 있다는 규칙 아래, (s, b_s)에서 (t, b_t)로 가는 방과 단추 누름의 순서 열의 개수를 1e9+7로 나눈 나머지로 구한다.어려움9동적 계획법행렬+2아직 제출이 없습니다1초512 MB지문만 제공
Number of Colorful Matchings이분 그래프의 완전 매칭을 사용한 빨간 간선 수에 따라 분류하고, 각 개수를 2로 나눈 나머지로 구한다.어려움9조합론행렬+2아직 제출이 없습니다2초512 MB지문만 제공
Числа Фибоначчиn과 k가 주어질 때 처음 n개 피보나치 수의 k제곱의 합을 10^9+23으로 나눈 나머지를 구한다.어려움9수학행렬+1아직 제출이 없습니다5초256 MB지문만 제공