cho.sh

문제

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

전체 결과문제 730개
제목난이도유형정답자시간 제한메모리 제한채점
나무판자N그루의 나무가 매일 각자 p_i 퍼센트 확률로 높이 1만큼 자랄 때, M일 차 하늘선에서 만들 수 있는 가장 큰 축에 나란한 직사각형 넓이의 기댓값을 998244353으로 나눈 나머지로 구한다.어려움8확률동적 계획법+2아직 제출이 없습니다5초1024 MB지문만 제공
Doing the Container Shuffle컨테이너 1부터 n까지를 두 스택에 무작위로 넣었을 때, 주어진 순서대로 꺼내는 데 필요한 이동 횟수의 기댓값을 구한다.어려움8확률수학+2아직 제출이 없습니다2초1024 MB지문만 제공
사다리 게임 만들기N개의 세로선 사다리에 M개의 가로선을 무작위로 추가할 때, S번째 세로선에서 출발한 구슬이 E번째 세로선으로 나올 확률을 계산한다.어려움8동적 계획법확률+2아직 제출이 없습니다1초1024 MB지문만 제공
Manhattan Walkr x c 격자의 왼쪽 위에서 오른쪽 아래로 이동할 때, 각 칸의 방향이 무작위 타이머에 따라 뒤집히고 현재 칸의 정보만 볼 수 있을 때 기대 대기 시간의 최솟값을 구한다.어려움8동적 계획법확률+2아직 제출이 없습니다1초2048 MB지문만 제공
All Survived?정해진 순서대로 n명이 행동하며, 아군의 공격 대상은 우리가 정하고 적군은 무작위로 공격할 때 아군이 한 명도 죽지 않을 확률의 최댓값을 구한다.어려움8동적 계획법확률+2아직 제출이 없습니다8초1024 MB지문만 제공
過去問の共有K번의 단계마다 무작위로 간선 하나를 골라 두 학생의 기출문제 집합을 합칠 때, 학생 1이 가지게 되는 과목 수의 기대값을 998244353으로 나눈 나머지로 구한다.어려움8확률동적 계획법+2아직 제출이 없습니다8초1024 MB지문만 제공
엉엉이의 저주 탈출턴 수 N과 상수 M이 주어질 때 원 분할 조각 수의 홀짝 게임에서 현철이가 이길 확률을 10^9+7로 나눈 나머지로 구한다.어려움8수학조합론+2아직 제출이 없습니다2초1024 MB지문만 제공
고장난 키보드각 숫자 자판이 한 글자 또는 두 글자를 입력하고 백스페이스가 한 글자 또는 두 글자를 지울 때, 주어진 인증번호를 입력하는 최소 기댓값을 구한다.어려움8동적 계획법확률+1아직 제출이 없습니다1초1024 MB지문만 제공
잘못 생성된 데이터크기 1000인 순열 1000개가 주어지고, 각 순열을 만든 것이 두 생성기 중 어느 쪽인지 판별한다. 90% 이상 맞히면 정답이다.어려움8확률수학+2아직 제출이 없습니다5초1024 MB지문만 제공
택틱성공 확률과 득점, 실점이 정해진 N개의 택틱을 순서대로 실행할 때, 최종 점수가 양수일 확률과 그 조건부 평균, 음수일 확률과 그 조건부 평균을 구한다.어려움8확률동적 계획법+2아직 제출이 없습니다2초1024 MB지문만 제공
Training, Round 3n개 원소에서 무작위로 고른 p개짜리 부분집합 k개가 서로 겹치지 않을 확률을 소수 모듈러스로 구한다.어려움8조합론확률+2아직 제출이 없습니다1초2048 MB지문만 제공
Kruidnoten가중 그래프와 각 상점의 재고 확률이 주어질 때, 1번에서 n번까지 가는 최단 경로 중 재고가 있는 상점을 하나 이상 지나는 경로 길이의 기댓값을 구한다.어려움8최단 경로동적 계획법+2아직 제출이 없습니다4초2048 MB지문만 제공
Mouse Trap볼록 다각형이 주어질 때, 내부의 균등 무작위 점이 세 꼭짓점으로 만든 삼각형 안에 엄격히 들어가는 꼭짓점 삼중쌍 개수의 기댓값을 구한다.어려움8조합론기하+1아직 제출이 없습니다3초2048 MB지문만 제공
Fugitive Frenzy경찰관과 숨어 있는 도망자가 트리에서 추격 게임을 벌일 때, 최적의 혼합 전략에서 기대 체포 시간을 구한다.어려움8게임 이론트리+2아직 제출이 없습니다5초2048 MB지문만 제공
Dice Encryption Algorithm10^100 이하의 수를 18500번의 주사위 굴림 과정으로 선택해 암호화하고, 기록을 이용해 원래 수를 복호화하는 인터랙티브 문제다.어려움8확률수학+1아직 제출이 없습니다3초2048 MB지문만 제공
Coconuts코코넛별 내구도는 알지만 어느 코코넛이 어느 내구도인지 모를 때, 정확히 k번의 타격으로 깨뜨릴 수 있는 코코넛 수의 기댓값을 최대로 만든다.어려움8동적 계획법확률+1아직 제출이 없습니다3초2048 MB지문만 제공
"Memo" Game With a Hint카드 뒷면의 회전 표시로 추가 정보를 부호화해, 메모 게임에서 평균 13.5회 이하의 실수로 끝내는 전략을 설계한다.어려움8조합론그리디+2아직 제출이 없습니다2초2048 MB지문만 제공
Fortune Wheeln개 칸의 바퀴에서 x번 칸에서 시작해 K개의 고정 점프와 무작위 칸으로 이동하는 수단을 써서 0번 칸에 도달하는 최소 기대 횟수를 구한다.어려움8그래프정렬+2아직 제출이 없습니다1초2048 MB지문만 제공
Sugar Sweet IIn개의 이벤트가 무작위 순서로 일어나며, i번 아이가 b_i번 아이보다 사탕이 적으면 w_i개를 받는다. 모든 이벤트가 끝난 뒤 각 아이가 가질 사탕 수의 기댓값을 1e9+7로 나눈 나머지로 구한다.어려움8확률그래프+1아직 제출이 없습니다2초2048 MB지문만 제공
수열과 쿼리와 확률 1M번의 연산이 무작위로 i번째 원소를 i배 하거나 모든 원소를 (N+1-i)/N배 할 때, 최종 합 또는 곱과 초기 값의 비의 기댓값을 구한다.어려움8수학확률+2아직 제출이 없습니다1초1024 MB지문만 제공
수열과 쿼리와 확률 3수열에 네 종류의 연산 중 하나를 균일한 확률로 M번 독립적으로 적용할 때, 최종 합 또는 곱과 초기 값의 비의 기댓값을 1e9+7로 나눈 나머지로 구한다.어려움8수학조합론+2아직 제출이 없습니다1.5초1024 MB지문만 제공
Gopher Residence방들이 1번 방을 뿌리로 하는 트리를 이루고, 각 고퍼는 확률 1/2로 남으며, 이후 부분 트리 용량을 지키며 무작위로 방을 채운다. 최종 생존 수의 기댓값을 구한다.어려움8트리확률+2아직 제출이 없습니다3초2048 MB지문만 제공
불의 군주 라그나로스 2체력 H_i인 하수인 M마리가 있을 때, X 피해를 주는 불의 군주 N마리가 상대 영웅을 처치하는 경우의 수를 센다.어려움8조합론동적 계획법+2아직 제출이 없습니다7초1024 MB지문만 제공
Kaz's Partyn명의 친구가 있을 때, 모든 사람이 원하는 음료를 받을 때까지 교환 과정이 걸리는 기대 라운드 수를 최대로 만드는 순열을 찾아 그 값을 출력한다.어려움8확률조합론+2아직 제출이 없습니다2초2048 MB지문만 제공
Another Expected Value Problem무작위로 원소를 골라 나머지를 한 칸씩 끌어당기는 연산을 k번 수행한 뒤 무작위 원소의 기댓값을 1e9+7로 나눈 나머지로 구한다.어려움8수학확률+2아직 제출이 없습니다1초2048 MB지문만 제공
Egzamin각 문제의 정답 확률이 독립일 때, t점 이상을 받을 확률이 최대가 되도록 답할 문제 집합을 고른다.어려움8동적 계획법정렬+2아직 제출이 없습니다3초2048 MB지문만 제공
g-raph 신앙 (Hard)트리에서 간선 하나를 균일한 확률로 지우고 인접하지 않은 정점 쌍 하나를 균일한 확률로 이어 붙이는 마술을 두 번 할 때, 매번 트리 조건이 유지될 확률을 구한다.어려움8조합론수학+2아직 제출이 없습니다1초1024 MB지문만 제공
Split the SSHS 5트리의 각 건물에서 함정 하나가 무작위로 작동해 이웃을 잠그며, 1번에서 각 목적지에 도달할 확률을 998244353으로 나눈 나머지로 구한다.어려움8확률트리+2아직 제출이 없습니다1초1024 MB지문만 제공
드래곤볼: MatKor Cup 없애기무작위 과정을 거쳐 P일째와 M일째에 일곱 공이 목표 상태가 되거나 1성구부터 7성구까지 하나씩 존재할 확률을 각각 구한다.어려움8확률행렬+2아직 제출이 없습니다0.7초1024 MB지문만 제공
Mingle고리 모양으로 놓인 방들에서 각 플레이어가 자기 번호에서 k 이내의 방을 균등하게 무작위로 고를 때, 정확히 한 명만 들어간 방의 기댓값을 구한다.어려움8동적 계획법조합론+2아직 제출이 없습니다1초2048 MB지문만 제공
Last Celebration길이 D인 벽에 N개의 구간 칠하기 작업이 무작위 순서로 수행될 때, 같은 색이 이어진 극대 구간의 기대 개수를 998244353으로 나눈 나머지로 구한다.어려움8확률조합론+2아직 제출이 없습니다5초1024 MB지문만 제공
카우보이돌아가며 사격하는 카우보이들이 명중률에 따라 최적의 표적을 선택할 때 각자가 최후 생존자가 될 확률을 구하는 문제입니다.어려움9게임 이론동적 계획법+2아직 제출이 없습니다2초128 MB채점 가능
조작인가 아닌가g개의 조, 시드 팀, 포트, 연맹 제약이 주어질 때, 가능한 모든 유효한 조 추첨에서 특정 팀이 같은 조에서 만나는 상대들의 힘 합의 평균을 구한다.어려움9조합론확률+2아직 제출이 없습니다1초128 MB채점 가능
카드 더미 게임의 성공 확률각각 n장인 카드 묶음 k개를 잘 섞어 n개의 더미로 나눈 뒤, 카드에 적힌 번호를 따라 이동하는 게임이 최대 m번의 재시작 안에 성공할 확률을 구해 소수점 r자리까지 출력한다.어려움9확률조합론+2아직 제출이 없습니다1초128 MB채점 가능
병렬 실행의 기댓값두 프로그램의 명령어를 무작위로 번갈아 실행할 때 모든 공유 변수의 최종 값의 기댓값을 구한다.어려움9확률동적 계획법+1아직 제출이 없습니다1초128 MB채점 가능
시험각 학생의 시험 점수 확률분포가 주어질 때, 모든 학생의 유럽 성적을 이어 붙인 문자열이 주어진 금지 문자열을 하나도 포함하지 않을 확률을 정확한 기약분수로 구한다.어려움9동적 계획법문자열 매칭+2아직 제출이 없습니다2초128 MB채점 가능
마르코프 열차각 열차가 취소될 수 있고 취소되면 다음 열차를 기다리는 상황에서, 목적지에 제때 도착할 확률이 가장 높은 경로를 찾는다.어려움9동적 계획법확률+1아직 제출이 없습니다1초128 MB채점 가능
우유를 마시는 용구간 [m, M]에서 독립적으로 균등하게 뽑은 소 n마리의 우유 생산량 합이 h보다 작을 확률을 소수점 d자리까지 버림하여 출력한다.어려움9확률수학+2아직 제출이 없습니다1초128 MB채점 가능
비디오 포커주어진 비디오 포커 배당표에 대해, 최적 기대값 전략이 정확히 0, 1, 2, 3, 4, 5장을 버리게 되는 2,598,960개 초기 패의 개수를 각각 센다.어려움9완전 탐색조합론+2아직 제출이 없습니다1초128 MB채점 가능
톨게이트모든 주민이 모든 음식점을 무작위 최단 왕복 경로로 방문할 때 기대 통행료 수입이 가장 큰 도로를 찾습니다.어려움9최단 경로그래프+2아직 제출이 없습니다2초256 MB채점 가능
숨겨진 미로홀수 거리인 모든 정점 쌍의 경로 간선 가중치 중앙값 기댓값을 기약분수로 출력합니다.어려움9분할 정복트리+2아직 제출이 없습니다2초256 MB채점 가능
덮어쓰기 게임좌상단 prefix 직사각형을 무작위로 덧칠해 목표 배치와 처음 일치할 때까지 칠한 칸 수의 기댓값을 기약분수로 구합니다.어려움9확률행렬+1아직 제출이 없습니다8초512 MB채점 가능
업적의 노예 2N개 재료로 단도를 최대한 만들고 단도마다 0개부터 K개까지 재료를 무작위로 회수하는 과정을 반복한 뒤 N개 미만으로 남은 재료의 분포를 구합니다.어려움9확률동적 계획법+1아직 제출이 없습니다3초256 MB채점 가능
무작위 신호각 방송국이 독립적인 균일 전원을 추첨해 원반 신호를 송출할 때 평면 전체에서 가장 강한 수신 세기를 적분한 값의 기댓값을 계산합니다.어려움9기하확률+1아직 제출이 없습니다12초256 MB채점 가능
카드 등급 부호화네 가지 카드 등급의 확률이 주어질 때 N회 뽑기 결과를 나타내는 최적 이진 코드의 최소 기대 길이를 구합니다.어려움9그리디힙+2아직 제출이 없습니다3초128 MB채점 가능
카지노승률이 p퍼센트인 게임에서 m달러로 시작해 n달러에 도달할 확률이 가장 높아지도록 매 회차 베팅액을 정합니다.어려움9확률동적 계획법+1아직 제출이 없습니다2초256 MB채점 가능
몽유병에 걸린 양두 목양견이 매 차례 이웃한 칸 두 개를 막아 무작위로 움직이는 양을 집으로 유도할 때 기대 이동 횟수의 최솟값을 구합니다.어려움9확률게임 이론+1아직 제출이 없습니다20초1024 MB채점 가능
제비뽑기빨간 제비는 버리고 초록과 파란 제비는 다시 넣을 때, 파란 제비를 K번 뽑을 때까지의 기대 뽑기 횟수를 구한다.어려움9확률수학+1아직 제출이 없습니다2초512 MB채점 가능
위험한 복권정확히 한 명만 쓴 수 중 가장 작은 수를 쓴 학생이 이기는 복권에서 대칭 혼합 내시 균형 전략을 구해 각 번호의 확률을 소수 다섯째 자리까지 출력한다.어려움9게임 이론확률+2아직 제출이 없습니다2초512 MB채점 가능
타로 점괘 허풍길이 n인 무작위 문자열에서 {R,P,S}로 이루어진 같은 길이의 문자열 최대 10개가 연속 부분 문자열로 나타날 확률을 비교해 큰 순서대로 정렬한다.어려움9문자열 매칭확률+2아직 제출이 없습니다2초512 MB채점 가능
최대공약수의 기댓값K개의 값이 각자의 구간에서 균등하게 독립적으로 선택될 때, 선택된 수들의 최대공약수의 기댓값을 유리수로 구해 10^9+7로 나눈 값을 출력합니다.어려움9확률수학+2아직 제출이 없습니다2초512 MB채점 가능
Satan Game기대 주사위 굴림 횟수가 5*10^19 이상이 되도록 칸 수 100 이하의 뱀과 사다리 보드를 설계해 출력한다.어려움9확률동적 계획법+1아직 제출이 없습니다2초512 MB지문만 제공
달콤새콤사탕 나라 선수 중 누구에게 단맛과 신맛을 무작위로 바꾸는 물약을 먹일지 골라, 모든 무작위 순서와 경기 종류에서 사탕 나라가 얻는 기대 점수를 최대로 만든다.어려움9확률조합론+2아직 제출이 없습니다1초512 MB채점 가능
연결그래프의 모든 간선의 저항이 1Ω일 때, 간선으로 직접 이어진 모든 점 쌍 A, B 사이 합성저항 값의 총합을 구해 소수점 넷째 자리에서 반올림한 값을 출력하는 문제모든 간선의 저항이 1인 연결 그래프에서 각 간선 양 끝점 사이의 등가 저항을 모두 더한 값을 소수점 셋째 자리까지 반올림해 구한다.어려움9그래프행렬+2아직 제출이 없습니다1초512 MB채점 가능
코포빵 토너먼트서로 다른 레이팅 구간 [A, B]마다 참가자 순서를 무작위로 정했을 때 기록자가 적는 서로 다른 숫자 개수의 기댓값을 1e9+7로 나눈 나머지로 구한다.어려움9확률조합론+2아직 제출이 없습니다5초1024 MB지문만 제공
Closest Pair Algorithm평면을 무작위 각도로 회전한 뒤 가장 가까운 두 점을 찾는 알고리즘이 거리 함수를 호출하는 횟수의 기댓값을 계산한다.어려움9기하확률+2아직 제출이 없습니다10초512 MB지문만 제공
Unfair Card Deck가중 추출 과정에서 얻은 100000개의 카드 뽑기 순서를 보고, 모든 쌍의 비율이 실제 비율과 가깝도록 각 카드 종류의 가중치를 복원한다.어려움9확률수학+2아직 제출이 없습니다2초512 MB지문만 제공
Battle Royale선분 안 고정된 위치에 있는 n명의 플레이어가 매초 줄어드는 안전 구역 밖에서 각각 ai초 버틸 수 있을 때, 구역이 한 점으로 줄어들면 마지막까지 살아남을 확률을 각 플레이어마다 구한다.어려움9수학확률+2아직 제출이 없습니다2초512 MB지문만 제공
All Kill각 문제의 풀이 아이디어가 균등분포로 임의의 분에 도착할 때, 모든 문제를 연속된 구간으로 끝까지 코딩할 확률을 t^n배 하여 998244353으로 나눈 나머지를 구한다.어려움9확률조합론+2아직 제출이 없습니다1초512 MB지문만 제공
Eevee여러 순열을 교차 병합해 같은 돌이 k개 연속으로 나오지 않게 만드는 경우의 수를 모든 연속한 스택 구간에 대해 합해 1e9+7로 나눈 나머지를 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다5초512 MB지문만 제공
Flip각 팀 인원이 n명으로 제한된 동전 던지기 배정 과정에서, 주어진 사람 집합이 모두 같은 팀이 될 확률을 998244353으로 나눈 나머지로 구한다.어려움9조합론수학+2아직 제출이 없습니다10초512 MB지문만 제공
레이저 증폭아래 왼쪽에서 들어온 광자 하나가 w x h 격자에서 n개의 확정 결함 칸을 제외한 나머지 칸이 확률 1-p로 결함일 때 오른쪽 위에서 기대값 k개의 광자를 내도록 하는 p를 구하고, 불가능하면 -1을 출력한다.어려움9수학조합론+2아직 제출이 없습니다2초64 MB채점 가능
Fox Labeling무작위로 라벨을 찍는 과정을 반복해 n마리의 여우가 모두 서로 구별될 때까지 걸리는 기대 시간을 분 단위로 구한다.어려움9확률동적 계획법+1아직 제출이 없습니다3초512 MB지문만 제공
RMQ 유사 수열수열 A가 주어질 때, 모든 부분 구간에서 A와 같은 RMQ 결과를 내는 [0,1] 구간의 무작위 실수 수열 B의 기댓값 합을 1e9+7로 나눈 나머지를 구한다.어려움9트리조합론+2아직 제출이 없습니다2초256 MB채점 가능
Road Connectivity정점이 5개 이하인 완전 그래프에서 매일 간선 하나가 균등한 확률로 토글될 때, 각 날짜 구간 [l, r] 안에서 그래프가 연결되는 날이 존재할 확률을 구한다.어려움9확률행렬+2아직 제출이 없습니다2초256 MB지문만 제공
Jitterbug꼭짓점 1에서 n까지의 무작위 걷기가 평균 b번 이상 움직이도록 n개 꼭짓점 위의 연결된 단순 그래프를 만든다.어려움9그래프수학+1아직 제출이 없습니다2초256 MB지문만 제공
Game Relicsn개 렐릭의 개별 가격과 중복 시 절반을 환불하는 x 비용의 무작위 뽑기가 주어질 때, n개를 모두 모으는 데 드는 최소 기대 비용을 구한다.어려움9확률동적 계획법+2아직 제출이 없습니다3초512 MB지문만 제공
공항 체크인각 창구의 승객당 처리 시간과 현재 승객의 남은 시간이 무작위로 정해질 때, 가장 먼저 끝나는 창구가 승객당 처리 시간이 가장 짧은 창구일 확률을 구한다.어려움9확률수학+1아직 제출이 없습니다1초256 MB채점 가능
Lazy Studentk번의 시험 기회 동안 응시 사이에 합격 확률을 올릴 수 있을 때, 학생이 배워야 하는 주제 양의 최소 기댓값을 구한다.어려움9동적 계획법확률+2아직 제출이 없습니다1초256 MB지문만 제공
Short Random Problem각 간선 길이가 [0,1]에서 독립적으로 균등하게 정해지는 트리에서 지름의 기댓값을 1e9+7로 나눈 나머지로 구한다.어려움9트리확률+2아직 제출이 없습니다6초512 MB지문만 제공
지진각 경로는 다리의 전부가 살아 있어야 통행할 수 있다. 어느 경로든 연결이 되는지 판정할 때까지 필요한 검사 횟수의 기댓값이 최소가 되도록 검사 순서를 정한다.어려움9확률동적 계획법+2아직 제출이 없습니다1초512 MB채점 가능
Do I Wanna Know?번호가 작은 원숭이가 이길 확률 p가 고정일 때, 어떤 k마리가 나머지 전부를 이길 확률에 g(k)를 곱한 합을 998244353으로 나눈 나머지를 구한다.어려움9조합론수학+1아직 제출이 없습니다2초512 MB지문만 제공
동전 던지기두 사람이 길이 20 이하의 H/T 문자열을 하나씩 고르고, 공정한 동전을 던져 둘 중 하나 또는 둘 다 처음 나타날 때까지 진행할 때 앨리스 승리, 밥 승리, 무승부 확률을 각각 구한다.어려움9확률동적 계획법+2아직 제출이 없습니다1초256 MB채점 가능
Multi-stage Marathon각 플레이어가 진출 간선으로 균등하게 이동하는 유향 그래프 위의 확률 보행에서, 시각 1부터 T까지 정점 n에 있는 플레이어 기대 수의 XOR을 구한다.어려움9그래프행렬+2아직 제출이 없습니다3초512 MB지문만 제공
Randomized Binary Search Tree무작위 키와 우선순위를 가진 N개의 원소를 트립에 삽입할 때, 최종 높이가 h가 될 확률을 각 h마다 구한다.어려움9확률동적 계획법+2아직 제출이 없습니다2.5초512 MB지문만 제공
Generator가중치가 주어진 무작위 숫자 스트림에서 n개의 서로 다른 길이 L 수열이 모두 한 번 이상 나타날 때까지의 기대 시간을 구해 1e9+7로 나눈 값을 출력한다.어려움9동적 계획법확률+2아직 제출이 없습니다3초256 MB지문만 제공
인간의 실수각 차례에 인접한 말 하나를 잡아 없애야 하는 격자 게임에서, 두 선수가 후보 수 집합의 크기를 각자의 오차 계수로 제한할 수 있을 때 최적 전략 아래에서 저스틴이 이길 확률을 구한다.어려움9게임 이론비트 연산+2아직 제출이 없습니다1초512 MB채점 가능
Landlords매번 A_i 위치에서 덱을 나눈 뒤 두 더미를 무작위 순서로 합치는 과정을 m번 반복한 후, 특정 위치에 있는 카드의 f(i) 기댓값을 구한다.어려움9확률수학+2아직 제출이 없습니다1초512 MB지문만 제공
거리의 기댓값새 정점을 이전 정점에 a_j에 비례하는 확률로 붙여 트리를 만들 때, 두 정점 사이 거리의 기댓값을 10^9+7로 나눈 나머지로 구하는 문제다.어려움9트리확률+2아직 제출이 없습니다4초1024 MB지문만 제공
Robust DefenseM개의 통신탑이 각각 확률 S/100로 살아남을 때, 모든 군사 기지가 두세 개의 살아남은 탑으로 덮일 확률을 유리수로 구해 모듈로 출력한다.어려움9기하조합론+2아직 제출이 없습니다6초512 MB지문만 제공
Hit the Hay아기의 수면 상태를 연속시간 마르코프 연쇄로 모델링하고, 고정된 알람 시각 전까지 부모가 얻을 수 있는 최대 기대 수면 시간을 구한다.어려움9확률동적 계획법+2아직 제출이 없습니다5초512 MB지문만 제공
Paris Escape마크는 0번 방에서 n-1번 방까지 정해진 경로로 이동하고 경찰관들은 각자 무작위로 걷는다. 같은 방에 동시에 있을 때마다 충돌로 세며, 기대 충돌 횟수를 최소로 하는 경로를 찾는다.어려움9그래프확률+2아직 제출이 없습니다2초512 MB지문만 제공
Infection Estimation인구 중 감염자 수를 하루 최대 50번의 적응적 집단 검사로 실제 값의 2배 이내로 추정하는 문제다.어려움9이분 탐색수학+2아직 제출이 없습니다1초1024 MB지문만 제공
Ah, It's Yesterday Once More최대 20x20 크기이고 연결되어 있으며 사이클이 없는 격자를 만들어, 길이 50000의 무작위 이동열이 25퍼센트 이상의 확률로 캥거루들을 서로 다른 칸에 남겨두도록 해야 한다.어려움9확률수학+2아직 제출이 없습니다1초512 MB지문만 제공
Fireworks폭죽 하나를 만드는 데 n분이 걸리고 완벽할 확률은 p/10000이며, 완성된 폭죽을 모두 점화하는 데 m분이 들 때, 완벽한 폭죽이 하나 이상 나올 때까지 걸리는 최소 기대 시간을 구한다.어려움9확률수학+2아직 제출이 없습니다2초512 MB지문만 제공
지애 상수시에르핀스키 삼각형에서 독립적으로 균등하게 고른 두 점 사이의 평면 거리 기댓값을 소수점 아래 222자리까지 반올림해 출력한다.어려움9수학확률+1아직 제출이 없습니다22.222초222 MB지문만 제공
Game of Slots앨리스가 1번부터 N번 슬롯에 카드를 배치하면 밥이 이를 보고 최적으로 대응할 때, 밥 카드 값이 무작위인 상황에서 앨리스가 얻는 최적 기대 점수를 구한다.어려움9게임 이론확률+2아직 제출이 없습니다1초1024 MB지문만 제공
Digit Blocks무작위로 나오는 숫자 블록을 높이 B인 N개 탑에 배치해, 각 탑을 위에서 아래로 읽은 수들의 합이 최대가 되도록 만든다.어려움9그리디동적 계획법+2아직 제출이 없습니다60초1024 MB지문만 제공
Swapping Inversions무작위로 균등하게 선택한 인접 역전 쌍을 교환해 순열을 정렬할 때, 교환한 값 차이의 절댓값 합의 기댓값을 구한다.어려움9확률수학+2아직 제출이 없습니다1초256 MB지문만 제공
Sweep Stakes각 칸 (i,j)에 지뢰가 있을 확률이 pi+qj인 격자에서 전체 지뢰 수가 정확히 t일 때, 질의한 부분집합의 지뢰 수 분포를 구한다.어려움9확률동적 계획법+2아직 제출이 없습니다20초2048 MB지문만 제공
Sum Modulo가중치 A_i로 1부터 N까지의 정수를 뽑는 생성기에서, 현재 값에 누적해 M으로 나눈 나머지가 처음 K가 될 때까지의 기댓값을 998244353으로 나눈 나머지로 구한다.어려움9수학확률+2아직 제출이 없습니다4초1024 MB지문만 제공
Guess Two Strings두 비밀 이진 문자열 s와 t 중 하나에서 무작위로 K개 위치를 뒤집어 만든 샘플만 보고 제한된 질의 횟수 안에 s와 t를 알아내는 문제다.어려움9확률수학+2아직 제출이 없습니다2초1024 MB지문만 제공
Пожиратель кактусов미생물이 선인장 그래프의 임의 정점에 내려 정점과 인접 간선을 먹는 과정을 그래프가 완전히 사라질 때까지 반복할 때, 방출되는 총에너지의 기댓값을 구한다.어려움9트리확률+2아직 제출이 없습니다2초512 MB지문만 제공
Gachapon중첩된 스텝업 가챠 롤에서 각 성급 아이템의 기대 개수와 합법 확률의 곱을 구한다.어려움9확률동적 계획법+2아직 제출이 없습니다5초512 MB지문만 제공
Twisty Little Passages차수를 확인할 수 있는 방에서 무작위 통로 이동과 순간이동을 합쳐 K번 이하의 조작으로 미지의 무방향 그래프의 전체 간선 수를 2/3배에서 4/3배 오차 안으로 추정한다.어려움9그래프확률+2아직 제출이 없습니다120초1024 MB지문만 제공
E(length(CH))각 점 i가 확률 p_i로 활성화되고 처음 세 점은 항상 활성화될 때, 활성화된 점들의 볼록 껍질 둘레의 기댓값을 구한다.어려움9기하확률+2아직 제출이 없습니다2초256 MB지문만 제공
Leaderboard Effect현재 해결 수에 비례해 문제를 고르는 팀들의 행동을 모형화하고, 팀 수가 무한히 많을 때 각 문제를 푸는 팀의 기대 비율을 구한다.어려움9확률동적 계획법+1아직 제출이 없습니다3초1024 MB지문만 제공
Infectious Diseasen명의 도시에서 감염과 백신 접종이 매일 확률적으로 퍼질 때 모든 환자가 완치되는 날의 기댓값을 1e9+7로 나눈 나머지로 구한다.어려움9확률동적 계획법+1아직 제출이 없습니다5초1024 MB지문만 제공
Game of Questionsn개의 문제마다 m명 참가자의 정답 여부가 0과 1로 주어지고, 문제 순서를 무작위로 섞어 틀린 사람이 탈락할 때 참가자 1이 최종 우승자가 될 확률을 구한다.어려움9조합론비트 연산+2아직 제출이 없습니다5초1024 MB지문만 제공
Expected Cycle Size일부 자리가 고정되고 나머지가 와일드카드인 순열 패턴이 주어질 때, 패턴을 따르는 모든 순열에서 각 위치가 속한 사이클 크기의 기댓값을 998244353으로 나눈 나머지로 구한다.어려움9조합론확률+2아직 제출이 없습니다2초1024 MB지문만 제공