cho.sh

문제

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

전체 결과문제 730개
제목난이도유형정답자시간 제한메모리 제한채점
소수방진5×5 격자에서 다섯 행, 다섯 열, 두 대각선이 모두 다섯 자리 소수가 되고, 그 소수들의 자릿수 합이 입력으로 주어진 값과 같으며 왼쪽 위 칸의 숫자가 고정된 격자를 모두 찾아 사전순으로 출력한다.어려움8백트래킹정수론+2아직 제출이 없습니다1초128 MB채점 가능
정사각형 복권N x N 격자에 1부터 N^2까지를 배열한 모든 순열에 대해, 정사각형의 네 꼭짓점을 이루는 네 수가 뽑힐 때 당첨 티켓 수의 기댓값을 구하고 상금을 나눈다.어려움8조합론수학+2아직 제출이 없습니다1초128 MB채점 가능
(베이지안) 사냥개와 토끼토끼의 무작위 이동과 잡음 섞인 관측을 베이즈 확률분포로 갱신한 뒤, 격자 미로에서 기대 최단거리를 최소화하는 방향으로 사냥개를 한 칸씩 움직인다.어려움8확률BFS+2아직 제출이 없습니다1초128 MB채점 가능
술 취한 산책가중치가 있는 DAG에서 최대 한 개의 간선을 제거해 정점 0에서 출발한 무작위 보행의 기대 길이를 최대로 만든다.어려움8그래프동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
이봐, 더 나은 도박사최종 손실 환급률과 절반 미만인 매 베팅 승률이 주어질 때 모든 중단 전략 가운데 기대 이익 최댓값을 계산합니다.어려움8확률동적 계획법+1아직 제출이 없습니다4초128 MB채점 가능
조직원 매수남은 예산을 보고 다음 매수 대상을 골라 최소 c명의 배신자를 얻을 확률을 최대로 만듭니다.어려움8동적 계획법확률아직 제출이 없습니다5초128 MB채점 가능
크러셔의 코드최대 8개 원소 배열을 두 무작위 교환 정렬로 정렬할 때 끝날 때까지 걸리는 반복 횟수의 기댓값을 계산합니다.어려움8확률동적 계획법+1아직 제출이 없습니다10초128 MB채점 가능
색 섞기각 토큰에서 색 하나를 골라 규칙대로 인접한 토큰을 합쳐 선택한 확실도 곱이 가장 큰 최종 색을 구하고 동률이면 ASCII 순서가 앞선 색을 출력합니다.어려움8동적 계획법확률아직 제출이 없습니다5초128 MB채점 가능
팰린드롬 여행s에서 t까지 균일한 무작위 이동으로 만든 문자열이 팰린드롬일 확률을 구합니다.어려움8확률그래프+2아직 제출이 없습니다10초128 MB채점 가능
Pachinko맨 위 행 열린 칸에서 시작한 구슬이 무작위로 이동할 때 각 목표 칸에 도달할 확률을 구합니다.어려움8확률그래프+1아직 제출이 없습니다6초512 MB채점 가능
업적의 노예 3M개의 나뭇조각으로 제작과 분해를 반복하면 N개 미만이 남으며 각 나머지가 될 확률을 1e9+7로 나눈 나머지로 출력합니다.어려움8확률동적 계획법+2아직 제출이 없습니다3초256 MB채점 가능
마지막 마법사10개 수치는 1에서 시작해 T번의 무작위 증가를 거친 뒤 그 곱의 기댓값에 A의 T제곱을 곱한 값을 1000000007로 나눈 나머지를 구합니다.어려움8확률조합론+2아직 제출이 없습니다1초256 MB채점 가능
생일 파티N명의 손님이 각각 다른 무작위 손님에게 선물을 주며 k명이 방향성 선물 순환을 이룰 확률을 구합니다.어려움8조합론확률+1아직 제출이 없습니다5초256 MB채점 가능
압수르디스탄의 도로 2N개 도시가 각각 무작위로 다른 도시 하나와 도로를 연결할 때 전체 도로망이 연결될 확률을 구합니다.어려움8조합론확률+2아직 제출이 없습니다1초256 MB채점 가능
그냥 퀴즈일 뿐알려진 질문 중 하나가 단어 단위로 출제될 때 중간에 답을 외쳐 제한 시간 안에 기대 점수를 최대화합니다.어려움8동적 계획법트라이+1아직 제출이 없습니다1초256 MB채점 가능
소수가 될 때까지 쪼개기N에서 시작해 합성수를 무작위 약수 쌍으로 나누는 과정을 모든 수가 소수가 될 때까지 반복할 때 필요한 평균 분할 횟수를 구합니다.어려움8확률동적 계획법+2아직 제출이 없습니다1초256 MB채점 가능
나비 효과앞선 사건 결과가 뒤따르는 사건 확률을 바꾸는 n개 사건에서 이중 주사위 개입 k번을 배분해 마지막 사건이 성공할 확률을 최대화합니다.어려움8동적 계획법확률아직 제출이 없습니다5초256 MB채점 가능
ARAM (큰 데이터)리롤 재화를 써서 무작위 챔피언을 교체할 시점을 정해 장기 승률을 최대화합니다.어려움8동적 계획법확률+2아직 제출이 없습니다120초512 MB채점 가능
Proper Shuffle (Small)크기 1000의 순열 120개가 주어지며, 각 순열이 올바른 Fisher-Yates 알고리즘에서 나왔는지 변형된 잘못된 알고리즘에서 나왔는지 최소 109개를 맞혀야 한다.어려움8확률수학+2아직 제출이 없습니다60초512 MB지문만 제공
관람차 (큰 입력)원형 관람차에서 시작 위치가 균일하게 무작위인 방문객들이 빈 곤돌라를 모두 채울 때까지 받는 평균 총요금을 계산합니다.어려움8확률동적 계획법+1아직 제출이 없습니다5초512 MB채점 가능
떨어지는 다이아몬드 (큰 입력)다이아몬드 N개가 x=0에 떨어져 좌우로 무작위로 미끄러질 때 주어진 좌표에 다이아몬드가 놓일 확률을 구합니다.어려움8확률시뮬레이션+1아직 제출이 없습니다5초512 MB채점 가능
위층과 아래층사용 횟수 제한 안에서 K개 이상 활동을 고르고 순서대로 배치해 잠든 일리아가 깰 확률을 최소화합니다.어려움8확률동적 계획법+2아직 제출이 없습니다5초512 MB채점 가능
위층과 아래층사용 횟수 상한이 있는 활동들을 K개 이상 골라 나열하고 잠들었다가 다시 깨는 확률을 최소화합니다.어려움8확률그리디+1아직 제출이 없습니다100초512 MB채점 가능
출근 전쟁 (Large)매시간 출발하는 노선과 반복되는 무작위 검사 지연이 있을 때 기대 이동 시간이 가장 짧은 환승 경로를 구합니다.어려움8최단 경로확률+1아직 제출이 없습니다5초512 MB채점 가능
구글 로얄A달러를 V달러로 불리기 위해 동전 던지기 배팅과 더블링을 선택해 파산 전 성공 확률을 최대화합니다.어려움8동적 계획법확률+1아직 제출이 없습니다5초512 MB채점 가능
챔피언 소트 (스몰)1부터 N까지의 순열을 부분 집합 셔플로 오름차순 정렬할 때 필요한 셔플 횟수 기댓값의 최솟값을 구합니다.어려움8확률조합론+1아직 제출이 없습니다5초512 MB채점 가능
시험 통과 확률 (대형 입력)제출 횟수 M과 문항별 독립 확률이 주어질 때, 한 번의 제출이 전부 정답일 확률이 최대가 되도록 답을 고른다.어려움8확률동적 계획법+1아직 제출이 없습니다5초512 MB채점 가능
백만장자 되기각 라운드에서 보유 금액의 일부를 걸어 마지막에 100만 달러 이상을 남길 확률을 최대로 만든다.어려움8동적 계획법확률+1아직 제출이 없습니다5초512 MB채점 가능
백만장자 (큰 입력)승리 확률 P인 M번의 라운드에서 보유 자금의 일부를 걸 수 있을 때, 마지막에 100만 달러 이상을 가질 확률을 최대로 만든다.어려움8동적 계획법확률아직 제출이 없습니다20초512 MB채점 가능
파리채 (작은 입력)원형 링과 원기둥 모양 줄이 만든 격자에 임의로 놓인 파리 원판이 닿을 확률을 구해 소수점 여섯 자리까지 출력한다.어려움8기하수학+2아직 제출이 없습니다5초512 MB채점 가능
파리채 (라지)라켓의 기하 구조가 주어질 때, 바깥 원 안에 균일하게 놓인 반지름 f인 파리의 중심이 링이나 줄과 겹칠 확률을 계산한다.어려움8기하수학+2아직 제출이 없습니다20초512 MB채점 가능
원 위의 점단위원 위에 무작위로 놓인 n개의 점이 중심각 p도 이하인 어떤 호 안에 모두 들어갈 확률의 -log2 값을 구한다.어려움8확률수학+2아직 제출이 없습니다2초512 MB채점 가능
의자왕각자 1/2 확률로 앉거나 서는 N명의 궁녀를 배치해, 뒤에 있는 사람이 앞사람보다 키가 큰 순서쌍 개수의 기댓값이 최대가 되도록 만든다.어려움8정렬그리디+2아직 제출이 없습니다1초32 MB채점 가능
목공N개의 널빤지가 필요한 상자를 분해할 때 회수되는 널빤지 수의 확률이 주어질 때, M개의 널빤지로 시작해 만들 수 있는 상자 개수의 기댓값을 구한다.어려움8동적 계획법확률+1아직 제출이 없습니다7초512 MB채점 가능
악수N명이 무작위로 악수할 때 모두가 한 덩어리로 아는 사이가 되는 악수 횟수의 기댓값을 1e9+7로 나눈 값으로 구한다.어려움8확률동적 계획법+2아직 제출이 없습니다4초512 MB채점 가능
흑백각 칸이 검정 또는 흰색일 확률이 1/2일 때, 모든 칸이 검정인 부분직사각형의 수와 모두 흰색인 부분직사각형의 수의 곱의 기댓값을 구한다.어려움8조합론확률+2아직 제출이 없습니다2초512 MB채점 가능
카지노N명의 참가자, M개의 구역, K번의 무작위 탈락이 주어질 때 단체가 살아남을 최대 확률을 구한다.어려움8동적 계획법확률+1아직 제출이 없습니다2초512 MB채점 가능
수열의 아름다움각 나무의 높이가 구간에서 균등 독립적으로 정해질 때, 지그재그 부분수열의 최대 아름다움의 기댓값을 구한다.어려움8동적 계획법확률아직 제출이 없습니다2초512 MB채점 가능
뜨거운 감자각 질의 구간마다 균등한 확률로 출발한 함수 그래프 이동에서 게임이 끝날 확률과 끝나지 않을 확률의 차이를 최대로 만드는 가장 작은 X를 구한다.어려움8그래프확률+2아직 제출이 없습니다2초512 MB채점 가능
시험각 학생의 고정된 학기 점수와 시험 점수 확률분포가 주어질 때, 성적 문자열이 금지된 부분 문자열을 하나도 포함하지 않을 확률을 구한다.어려움8동적 계획법문자열 매칭+2아직 제출이 없습니다1.5초512 MB채점 가능
연결 요소 개수의 기댓값각 정점 i가 확률 P_i로 선택될 때, gcd가 1보다 큰 두 선택 정점을 연결한 부분그래프의 연결 요소 개수의 기댓값을 구하고 E × 100^N을 1e9+7로 나눈 나머지를 출력한다.어려움8확률수학+2아직 제출이 없습니다5초512 MB채점 가능
정렬길이가 8 이하인 배열에 대해 두 가지 무작위 교환 방식이 정렬될 때까지 걸리는 기대 걸음 수를 각각 구한다.어려움8확률동적 계획법+1아직 제출이 없습니다2초128 MB채점 가능
게임 레벨 나누기n개 레벨을 k개의 연속한 그룹으로 나눠 무작위 코인 뽑기 과정의 총 소요 시간 기댓값이 최소가 되게 하고, 그 값을 소수점 여섯 자리까지 출력한다.어려움8동적 계획법분할 정복+2아직 제출이 없습니다2초512 MB채점 가능
피아노확률이 같은 N개의 건반 음이 있을 때, 고정된 M개 음렬이 처음 나타날 때까지의 기대 타건 수를 모든 접두사에 대해 구한다.어려움8문자열 매칭동적 계획법+2아직 제출이 없습니다1초64 MB채점 가능
코어 훈련 (Small2)N개의 코어에 U개의 훈련 단위를 나누어 각 단위마다 성공 확률을 1씩 올릴 때(최대 1), K개 이상의 코어가 성공할 확률을 최대로 만드는 값을 구한다.어려움8동적 계획법그리디+2아직 제출이 없습니다5초512 MB채점 가능
고스트버스터즈각 버튼의 독립적인 누름 확률이 주어질 때, 관측된 행에서 열로의 연결 신호를 만드는 가장 확률이 높은 누름 버튼 집합을 구한다.어려움8그래프동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
정치의 불확실성각 청문회는 시작 시각과 [a,b] 구간의 정수 길이를 가지며, 청문회를 끝까지 참석하는 전략으로 기대 참석 수를 최대로 만들어야 한다.어려움8동적 계획법확률+2아직 제출이 없습니다2초512 MB채점 가능
위쳐와 흥정하기NPC가 [L,R]에서 균등하게 고른 값을 모르는 채, 한 번 시도하거나 세이브를 다시 불러올 때마다 100ms가 소모되고 T가 한계일 때 받을 수 있는 기대 금액의 최댓값을 구한다.어려움8동적 계획법수학+2아직 제출이 없습니다2초512 MB채점 가능
The Battle for Wesnothd*b가 m 이하가 되도록 양의 정수 d와 b를 골라, 각각 확률 p/100로 명중해 d의 피해를 주는 b번의 독립 공격이 체력 h인 유닛을 죽일 확률을 최대로 만든다. 최적해들 중 d가 가장 작고 그다음 b가 가장 작은 것을 출력하며, 불가능하면 1 1을 출력한다.어려움8확률수학+2아직 제출이 없습니다0.1초1024 MB채점 가능
도박 안내서무방향 그래프에서 1번 도시에서 n번 도시로 갈 때, 원하지 않는 표를 버릴 수 있다는 조건 아래 필요한 무작위 표 개수의 최소 기댓값을 구한다.어려움8그래프확률+2아직 제출이 없습니다3초512 MB채점 가능
멀티섹트실패한 리비전이 n개 후보 중 하나이고 한 라운드에 최대 K개를 동시에 검사할 수 있을 때, i개가 실패한 라운드의 비용이 T_i일 때 기대 총비용을 최소로 하는 전략을 구한다.어려움8동적 계획법이분 탐색+2아직 제출이 없습니다2초512 MB채점 가능
비행기 잡기각 버스가 주어진 확률로 독립적으로 운행할 때, 시간 k까지 역 1에 도착할 확률을 최대로 만드는 전략을 구한다.어려움8동적 계획법확률+2아직 제출이 없습니다10초1024 MB채점 가능
보석 섬매일 보석 하나가 무작위로 선택되어 둘로 쪼개질 때, d일 뒤 가장 많은 보석을 가진 r명이 가진 보석 수 합의 기댓값을 구한다.어려움8확률동적 계획법+2아직 제출이 없습니다3초1024 MB채점 가능
난수 생성기1부터 N까지의 값 중 아직 안 나온 개수와 한 번만 나온 개수를 바탕으로, 모든 값이 두 번 이상 나올 때까지 필요한 추가 추첨 횟수의 기댓값을 구한다.어려움8확률동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
Nice Report방향 그래프의 각 정점에서 도달 가능한 정점 수를 참값의 두 배 이내로 근사해 출력한다.어려움8그래프확률+1아직 제출이 없습니다5초512 MB지문만 제공
호스밋8x8 체스판에서 두 나이트가 무작위로 이동할 때, 상대방의 칸에 먼저 도착할 확률이 더 높은 쪽을 판정한다.어려움8확률그래프+2아직 제출이 없습니다2초512 MB채점 가능
수열 생성기길이가 같은 H/T 패턴 여러 개가 주어질 때, 그중 하나가 처음 연속으로 나올 때까지 던진 동전 횟수의 기대값을 구합니다.어려움8문자열 매칭해시맵+2아직 제출이 없습니다2초512 MB채점 가능
Random Manhattan Distance볼록 다각형 내부에서 균일하게 무작위로 고른 두 점 사이 맨해튼 거리의 기댓값을 구한다.어려움8기하확률+1아직 제출이 없습니다2초512 MB지문만 제공
밸런스 빔각 위치에서 현금 수령과 동전 이동을 선택해서 양 끝에서 멈추는 무작위 이동의 기댓값을 시작 위치마다 최대화합니다.어려움8동적 계획법수학+2아직 제출이 없습니다2초512 MB채점 가능
무게중심A, B 타일의 질량을 주어진 범위에서 무작위로 뽑을 때 그물 무게중심이 빈 칸에 떨어질 확률을 구합니다.어려움8기하확률+2아직 제출이 없습니다2초512 MB채점 가능
Heaps of Fun각 노드 i가 [0, b_i] 구간에서 균등분포로 실수를 뽑을 때, 모든 부모의 값이 자식의 값보다 작아 힙 조건을 만족할 확률을 10^9+7로 나눈 나머지로 구한다.어려움8확률동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
소 데이팅각 소가 초대를 수락할 확률 p_i가 주어질 때, 정확히 한 마리만 수락할 확률이 최대가 되는 연속 구간을 찾아 10^6을 곱한 값을 내림하여 출력한다.어려움8수학투 포인터+2아직 제출이 없습니다2초512 MB채점 가능
Lost In The Park정점 n개, 간선 m개이고 사이클이 많아야 하나인 연결 그래프에서 시작 정점과 다음 이동을 무작위로 고를 때, 현재 정점과 그 이웃이 모두 방문될 때까지의 단순 경로 기대 길이를 구한다.어려움8동적 계획법확률+2아직 제출이 없습니다1초512 MB지문만 제공
룰렛트리 위의 놀이기구에서 룰렛을 돌려 이웃으로 이동하거나 집으로 돌아가는 확률 과정에서, S번에서 출발해 E번을 마지막으로 타고 집에 갈 확률을 각 쿼리마다 10^9+7로 나눈 값으로 구한다.어려움8트리확률+2아직 제출이 없습니다4초1024 MB지문만 제공
주사위와 사다리주사위를 굴려 사다리 게임 판을 통과할 때, 주어진 확률 p 이상으로 게임을 끝낼 수 있는 최소 굴림 횟수를 구한다.어려움8확률동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
Expecting Rain시간과 거리가 연속인 1m/s 보행에서 지붕 아래에서 기다리는 시점을 정해, 시간 구간과 세기, 확률을 가진 구름들로부터 맞을 비의 기댓값을 최소로 만든다.어려움8동적 계획법그리디+2아직 제출이 없습니다2초512 MB지문만 제공
홀드할까, 계속할까?각 질의에서 캐틀린의 점수, 호스터의 점수, 현재 턴 합계가 주어질 때, 두 사람이 최적으로 플레이한다고 가정하고 캐틀린의 승률을 최대화하는 선택이 홀드인지 계속인지 판정한다.어려움8동적 계획법확률+2아직 제출이 없습니다2초512 MB채점 가능
그놀 가설n개의 생성 확률과 무작위로 뽑는 k개의 타입 풀이 주어질 때, 선택되지 않은 타입의 확률이 원형으로 다음 선택된 타입에 더해진 뒤 각 타입의 기대 생성 확률을 구한다.어려움8확률동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
순례의 끝최근 방문한 N개 성지가 주어질 때, 이후 N번의 방문이 모두 서로 다른 곳이 될 때까지 걸리는 시간의 기댓값을 소수 X로 나눈 나머지로 구한다.어려움8확률수학+2아직 제출이 없습니다1초1024 MB지문만 제공
Expected Value연결된 평면 그래프에서 매초 이웃 정점으로 균등하게 이동하는 무작위 걷기가 정점 n에 처음 도달하는 시각의 기댓값을 구해 998244353으로 나눈 나머지를 출력한다.어려움8그래프확률+2아직 제출이 없습니다1.5초512 MB지문만 제공
기댓값인접한 두 원소를 무작위로 골라 왼쪽 값을 두 값의 차로 바꾸고 오른쪽 원소를 지우는 과정을 하나가 남을 때까지 반복할 때, 마지막 원소의 기댓값을 10^9+7로 나눈 나머지로 구한다.어려움8동적 계획법확률+2아직 제출이 없습니다3초16 MB채점 가능
버스 정류장n개 노선의 대기 시간이 각각 [0, di]에서 독립적으로 균등 분포할 때 최솟값의 기댓값을 구해 998244353으로 나눈 나머지로 출력한다.어려움8확률수학+2아직 제출이 없습니다2초512 MB채점 가능
Nonsense Time무작위 순열의 원소가 한 번에 하나씩 사용 가능해질 때, 매 단계마다 현재 사용 가능한 원소들로 이루어진 최장 증가 부분 수열의 길이를 구한다.어려움8동적 계획법이분 탐색+2아직 제출이 없습니다12초512 MB채점 가능
Alakazam배열에서 구간을 무작위로 섞는 연산이 여러 번 주어질 때, 특정 위치에 있는 값의 기댓값을 구하는 문제입니다.어려움8수학확률+2아직 제출이 없습니다2초512 MB채점 가능
Hypno각 도로의 Hypno에 1/2 확률로 면역인 상황에서 1번 교차점에서 n번 교차점까지 도달하는 최소 기대 시간을 구한다.어려움8그래프확률+2아직 제출이 없습니다2초512 MB지문만 제공
Graph Measurement각 변을 무작위로 검게 칠한 뒤 각 꼭짓점에 인접한 검은 변의 개수를 k번 측정한 결과가 주어질 때, 원래의 단순 무향 그래프를 복원한다.어려움8그래프확률+2아직 제출이 없습니다30초512 MB지문만 제공
Erase Nodes노드 n개와 간선 n개로 이루어진 연결 그래프에서 활성 노드를 무작위로 하나씩 지울 때, BFS 갱신 횟수의 기댓값을 998244353으로 나눈 나머지로 구한다.어려움8그래프확률+2아직 제출이 없습니다7초512 MB지문만 제공
가짜 퀵소트재귀 깊이 제한 k가 있는 잘못된 퀵소트를 크기 n의 균등 무작위 순열에 실행했을 때 생기는 역전 수의 기댓값에 n!을 곱한 값을 998244353으로 나눈 나머지를 구한다.어려움8조합론확률+2아직 제출이 없습니다2초512 MB채점 가능
Expn마리의 몬스터를 차례로 잡으며 각 몬스터가 i(0 이상 k 이하)의 경험치를 확률 p_i로 주고 총 경험치가 x를 넘으면 x로 잘릴 때, 잘린 총 경험치의 기댓값을 998244353으로 나눈 나머지로 구한다.어려움8확률동적 계획법+2아직 제출이 없습니다5초512 MB채점 가능
Joy자신의 실력 x를 n개의 위치 각각에 넣었을 때 토너먼트에서 우승할 확률을 구한다.어려움8확률동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
문제를 푸는 문제 (미니 앨범)한 장을 살 때마다 크기 A, C, E인 세 집합에서 각각 B, D, F개를 무작위로 받을 때, 모든 원소를 모으는 데 필요한 구매 횟수의 기댓값을 1e9+7로 나눈 나머지를 구한다.어려움8확률조합론+2아직 제출이 없습니다1초512 MB지문만 제공
Binary String숨겨진 1000비트 이진 문자열을 찾는다. 각 질의는 구간의 실제 1의 개수이거나 무작위로 고른 다른 값이며, 같은 구간을 두 번 질의할 수 없다.어려움8확률구현아직 제출이 없습니다2초256 MB지문만 제공
Jump Jump Jump좌표가 음이 아닌 k개의 서로 다른 점프 벡터가 주어질 때, (0,0)에서 출발한 토끼가 각 x에 대해 대각선 점 (x,x)에 처음으로 갇힐 확률을 n까지 구한다.어려움8동적 계획법조합론+2아직 제출이 없습니다5초512 MB지문만 제공
In The End각 열에서 케이크가 행 확률 p_i로 독립적으로 놓일 때, 로봇이 한 걸음당 수집하는 평균 케이크 수의 극한값을 구한다.어려움8동적 계획법확률+1아직 제출이 없습니다2초512 MB지문만 제공
좌석n개의 상금 값이 주어질 때, 각 좌석에서의 무작위 경합을 고려해 한 선수의 기대 상금이 최대가 되도록 좌석 확률분포를 정하는 문제이다.어려움8확률수학+2아직 제출이 없습니다1.5초256 MB채점 가능
형제와 자매0번 소녀와 1번부터 n번까지의 소녀로 이루어진 함수형 그래프에서 무작위 탐색으로 0번에 도달할 때까지 물어본 소녀 수의 기댓값을 10^9+7로 나눈 나머지를 구한다.어려움8그래프수학+2아직 제출이 없습니다1.5초512 MB채점 가능
Kolmogorov매분 무작위로 하나의 간선에 불이 들어오는 연결 무향 그래프에서, 최적으로 움직이는 사람이 1번 정점에서 N번 정점까지 가는 최소 기대 시간을 구한다.어려움8그래프동적 계획법+2아직 제출이 없습니다1초512 MB채점 가능
Greater Number Wins0부터 b-1까지의 눈이 나오는 주사위로 d칸짜리 수를 만드는 게임에서 조지가 번갈아 두는 방식과 순차 방식 각각에서 보장할 수 있는 최대 승률을 구한다.어려움8동적 계획법게임 이론+2아직 제출이 없습니다2초512 MB지문만 제공
피보나치의 악몽이전 두 항을 무작위로 골라 더해 만든 수열에서 n번째 항의 분산을 10^9+7로 나눈 나머지를 구한다.어려움8확률동적 계획법+2아직 제출이 없습니다2초256 MB채점 가능
Pattern Matchingn개의 집합에 무작위로 문자를 추가하는 연산이 균등 확률로 이루어질 때, 주어진 패턴이 연속한 집합들에서 처음 나타날 때까지 걸리는 라운드 수의 기댓값을 구한다.어려움8확률수학+2아직 제출이 없습니다2초256 MB지문만 제공
Expected Shoppingn!개의 방문 순서 각각에 대해, 가격이 B 이하인 상점을 만나면 남은 캔을 모두 사고 끝나는 규칙으로 지출한 총액의 기댓값을 기약분수로 출력한다.어려움8조합론확률+2아직 제출이 없습니다4초256 MB지문만 제공
Those Russian Hackers각 시간 구간의 검사 시각과 해킹 소요 시간이 확률분포로 주어질 때, 검사와 겹치지 않고 작업을 끝낼 최대 확률을 구한다.어려움8동적 계획법확률+1아직 제출이 없습니다3초256 MB지문만 제공
2084승부 조작이 가능한 팀들이 결과를 정할 때, 유일한 정직한 팀이 k-탈락 토너먼트에서 우승할 확률의 최솟값과 최댓값을 구한다.어려움8동적 계획법확률+1아직 제출이 없습니다5초256 MB지문만 제공
Random Numbers무작위로 생성된 큰 수 a_i와, 알려지지 않은 m과 k로 (a_i + k) mod m을 취한 뒤 섞은 b_i가 주어질 때, 가능한 (m, k)를 하나 찾는다.어려움8정수론수학+2아직 제출이 없습니다5초512 MB지문만 제공
Forest Game무작위로 노드를 하나씩 제거하며 그 순간 연결 성분의 크기를 점수에 더할 때, 최종 점수의 기댓값에 N!을 곱한 값을 10^9+7로 나눈 나머지를 구한다.어려움8트리확률+2아직 제출이 없습니다4초512 MB지문만 제공
Almost Longest Increasing Subsequence무작위 순열의 원소를 다음 원소를 보기 전에 실시간으로 선택해, 실제 최장 증가 부분 수열 길이의 최소 0.65배인 증가 부분 수열을 만든다.어려움8그리디확률+1아직 제출이 없습니다13초256 MB지문만 제공
LCP의 기댓값각 문자가 독립적으로 균등하게 생성되는 n개의 무한 이진 문자열에서 가장 긴 공통 접두사의 기댓값을 구해 분수 형태로 1e9+7로 나눈 값을 출력한다.어려움8확률조합론+2아직 제출이 없습니다1.5초256 MB채점 가능
Guess the Distributionp가 같은 30개 표본에 대해, 표준화된 이항분포에 잡음을 더한 분포에서 n을 1부터 100 사이로 추정한다.어려움8확률수학+1아직 제출이 없습니다7초256 MB지문만 제공
DreissigK100의 간선 색칠 게임에서 후수 플레이어로서, 매 턴 검은 간선 30개를 무작위로 고르는 상대를 맞아 흰 간선 하나씩을 칠해 100판 중 최소 95판에서 흰 해밀턴 사이클을 완성해야 한다.어려움8그래프그리디+2아직 제출이 없습니다15초256 MB지문만 제공
Rumpf단위 정사각형 안에 무작위로 놓인 n개의 점의 볼록 껍질이 주어진 한 점을 포함할 확률을 구한다.어려움8확률기하+2아직 제출이 없습니다2초256 MB지문만 제공