AtCoder Grand Contest 002 알고리즘 문제 풀이 및 코드 최적화 분석
A - Range Product
주어진 구간 [A, B]에 속한 모든 정수의 곱의 부호를 판별하는 문제입니다. 구간에 0이 포함되면 곱은 0이 됩니다. 모든 수가 양수라면 결과는 양수입니다. 모든 수가 음수라면 음수의 개수(B - A + 1)가 짝수일 때 양수, 홀수일 때 음수가 됩니다.
#include <iostream>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.t ...
9월 9일 12:02에 게시됨
이기 게임 이론: 스프래그 - 그런디 함수의 구현 및 활용
스프래그 - 그런디 (Sprague-Grundy) 함수 개요
조합론 게임 이론에서 가장 핵심적인 개념 중 하나는 스프래그 - 그런디 정리입니다. 이 정리는 임의의 공정한 게임 (Impartial Game) 을 니무 게임으로 환원하여 승패를 판별할 수 있음을 보여줍니다. 각 상태에 할당되는 값을 그런디 수 (Grundies Number), 또는 편의상 SG 값이라고 부릅니다.
SG 함수의 정의는 다음과 ...
7월 30일 17:00에 게시됨
Codeforces Round 960 (Div. 2) 효율적인 문제 풀이 전략
A. Submission Bait (게임 이론)
앨리스와 밥이 $n$개의 원소를 가진 배열 $a$를 사용하여 게임을 진행합니다. 초기 mx 값은 0이며, 각 플레이어는 자신의 차례에 $a_i \ge mx$인 인덱스 $i$를 선택하여 mx를 $a_i$로 갱신하고 $a_i$를 0으로 만듭니다. 더 이상 움직일 수 없는 플레이어가 패배할 때, 앨리스의 필승 전략 존재 여부를 판별해야 합니다.
이 문제의 핵심은 ...
7월 30일 12:49에 게시됨
선형 기저(Linear Basis)를 활용한 XOR 최적화 문제 분석
2024 CCPC Online Contest: 최댓값의 최소화 문제
2024 CCPC 인터넷 예선 J번 문제는 두 시퀀스의 XOR 합을 조정하여 그 중 최댓값을 최소화하는 문제입니다. 길이 $n$인 두 수열 $a, b$가 주어지며, 동일한 인덱스 $i$에 대해 $a_i$와 $b_i$를 교환하는 연산을 원하는 만큼 수행할 수 있습니다. 이때 $f(a) = \bigoplus_{i=1}^n a_i$와 $f(b) = \bigoplus_{i=1}^n b_i$를 ...
7월 23일 08:18에 게시됨