RMQ 문제 풀이: 슈퍼 피아노, 빈도 값, 인구 조사 문제
P2048 [NOI2010] 슈퍼 피아노
연속 부분 수열의 합을 전처리하고 RMQ를 사용하여 최대값을 찾습니다.
우선순위 큐를 사용하여 최적의 답을 저장합니다.
힙의 맨 위 요소를 꺼내서 계산한 후, 해당 지점을 제외하고 두 개의 새로운 구간을 다시 큐에 추가합니다. 이 과정을 k번 반복합니다.
#include <iostream>
#include <vector>
#include <queue>
#inc ...
7월 2일 00:21에 게시됨
Codeforces Round 864 (Div. 2) E. Li Hua and Array
문제 개요
배열의 각 원소에 대해 오일러 함수를 반복적으로 적용하면서, 특정 범위 내의 모든 원소가 동일한 값으로 수렴하는 최소 연산 횟수를 구하는 문제입니다. 이 과정에서 선형 시간 전처리와 세그먼트 트리, 그리고 LCA(Lowest Common Ancestor) 기법을 결합하여 효율적인 쿼리를 처리합니다.
핵심 아이디어
오일러 함수 φ(n)는 정수 n에 대해 1부터 n까지의 자 ...
6월 19일 02:59에 게시됨
AtCoder Beginner Contest 357 문제 분석 및 풀이
A - 손 소독하기
N명의 외계인이 순차적으로 손을 소독하려고 합니다. 각 외계인은 H_i개의 손을 가지고 있으며, 전체를 소독해야 합니다. 소독제는 총 M회 사용할 수 있습니다. 한 외계인이 소독을 할 때 필요한 양만큼만 사용하며, 부족하면 남은 양만 소모합니다. 모든 손을 소독한 외계인의 수를 구하세요.
단순히 앞에서부터 순회하면서 소독제 잔량을 갱신하고, 소진 ...
6월 13일 19:05에 게시됨
적용된 알고리즘과 문제 해결 전략
총점: \(100+100+30+45=275\)
시작 10분 동안 문제 A에 접근했으나, 한 시간 후 포기하고 다른 문제로 이동.
문제 B를 빠르게 해결한 후 C에 도전하였으나 실패.
D의 폭력적인 해법을 작성하고 남은 30분 동안 다시 A를 시도.
A: H 군의 블록
상단과 하단의 숫자를 모두 세그먼트 트리에 추가합니다. 만약 숫자가 두 번 이상 등장하면 이를 후보로 설정하며, 각 단계에서 ...
6월 4일 03:09에 게시됨
2018년 제9회 복건성 대학생 프로그래밍 경시대회 팀 연습 문제 분석
A. 기호 기반 계산 시스템 구현
주어진 명령어 집합(정의, 곱셈, 나눗셈, 덧셈, 뺄셈, 모듈러 연산)을 기반으로 간단한 식 계산 시스템을 구현한다. 각 명령어는 변수에 대한 연산을 수행하며, 결과는 항상 모듈러 연산을 통해 유지된다.
#include <set>
#include <map>
#include <iostream>
using namespace std;
typedef long long LL;
const LL MOD ...
6월 1일 01:20에 게시됨
AGC005 문제 해설
A - STring
스택을 이용한 시뮬레이션으로 해결합니다. 문자열을 순회하면서 'S'는 스택에 추가하고, 'T'가 등장할 때 스택 상단이 'S'이면 제거합니다. 최종적으로 남은 스택 크기가 정답입니다.
#include <iostream>
#include <stack>
using namespace std;
int main() {
string str;
cin >> str;
stack<char> stk;
for (char c ...
5월 31일 02:30에 게시됨
NOI 2025 연습 문제 풀이 기록 (제5회)
라운드 #77 - 20250521
A. 직렬 연결 (link)
문제 요약
각 정점에 두 가중치 \(a_i, b_i\)를 가진 트리가 주어진다. 단순 경로가 "좋은 경로"가 되려면 경로상의 \(b\) 합계와 경로상의 최소 \(a\) 값의 곱이 상수 \(V\) 이상이어야 한다. 모든 좋은 경로 중 \(\sum b\)의 최솟값을 구한다.
핵심 아이디어
정점 분할을 적용하면 조건은 \((B_u+B_v)\min(A_u,A_v) \ge V\) ...
5월 24일 02:35에 게시됨