yuja의 블로그

A. Mainak and Array 길이 \(n\)의 배열 \(a\)가 주어진다. 배열의 \([l, r]\) 구간을 선택, 원하는만큼 cyclically rotate하는 연산을 한 번 수행하여 얻을 수 있는 \(a_n - a_1\)의 최댓값을 구하는 문제이다. 다음과 같이 경우를 나눌 수 있다. 1) \(a_1, a_n\) 미포함: \(ans = a_n - a_1\) 2) \(a_1\)만 미포함: \(ans = max(a_2, a_3, ..., a_n) - a_1\) 3) \(a_n\)만 미포함: \(ans = a_n - min(a_1, a_2, ..., a_{n-1})\) 4) \(a_1, a_n\)을 모두 포함: \(ans = max_{1 \le i \le n}(a_{i-1} - a_i)\) (단, ..

UCPC 2022 예선 글 읽기 - UCPC 2022 예선이 종료되었습니다! 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 25323번: 수 정렬하기, 근데 이제 제곱수를 곁들인 25323번: 수 정렬하기, 근데 이제 제곱수를 곁들인 양의 정수로 이루어진 길이가 $N$ 인 수열 $A_1,A_2,\cdots ,A_N$이 존재할 때, 다음 행동을 원하는 만큼 반복할 수 있다. $1\leq i,j\leq N;i\neq j$이면서 $A_i\times A_j$가 제곱수인 $i$, $j$를 선택해, $A_i$와 $A_j$ www.acmicpc.net 이번 UCPC 해설 덕분에 명확하게 알게 된 성질을 정리해보았다. TL;DR: An equivalence relation on a nonempty ..

다음 조건을 만족하는 게임에 대해 논의할 것이다. 이는 backward induction을 위한 조건으로 볼 수 있다. Combinatorial game 1. 두 명의 플레이어가 번갈아가면서 게임을 진행한다. 2. 플레이어는 게임의 상태를 모두 알 수 있다. 3. 행동에 따른 게임 상태의 변화가 운에 의해 결정되지 않고 확정적이다. 4. 게임은 반드시 종료된다. (무한히 진행되지 않는다.) 5. 게임의 승패가 반드시 결정된다. (무승부가 존재하지 않는다.) Impartial game 취할 수 있는 행동은 오직 게임 상태에 의해 결정된다. 플레이어에 따라 취할 수 있는 행동이 달라지지 않는다. ex) Nim, 31 게임 cf. 체스 Normal game: 마지막에 움직이는 플레이어가 승리한다. Misére..

내가 누구? 2021 IUPC 대상 수상자 팀명: 수퍼겁쟁이들의 쉼터 팀원: 39dll, yooshnn, yuja 대회 前 39dll님의 제안을 받아 팀으로 합류했다. 처음으로 팀 대회에 참여하는 것이기에 기대도 됐지만 걱정이 앞섰다. 이 부분은 나보다 경험도 많고 작년 대회에서 좋은 성적을 거둔 팀원들과 연습하면서 점차 나아졌다. 비대면으로 참여할 수도 있었지만 의사 소통의 편의를 위해 한 곳에 모여서 진행하기로 했다. 조금 일찍 만나 점심을 먹었고, 대회 시작 20분 전에 스터디룸에 도착했다. 대회 中 제일 먼저 B를 읽었다. 보자마자 완탐인 건 알았지만 나보다 다른 팀원이 푸는 게 나을 것 같았다. 그래서 C를 잡고 있던 시은 님과 상의하고 문제를 바꿨다. 생각보다 금방 아이디어를 떠올려서 바로 구..

A. Pretty Permutations https://codeforces.com/contest/1541/problem/A Problem - A - Codeforces codeforces.com $n$마리의 고양이가 일렬로 늘어서 있다. $i$번째 고양이는 $i$번째 자리에 위치해 있다. 어떤 고양이도 이전에 있던 자리에 있지 않도록 자리를 바꿔야 한다. 1) $n=2k$ $1 \le i \le \frac{n}{2}$, $2i-1$번째 고양이와 $2i$번째 고양이가 짝을 지어 자리를 바꾼다. 2) $n=2k-1$ 처음 3마리의 고양이끼리 자리를 바꾼다. [1, 2, 3] $\rightarrow$ [3, 1, 2] $2 \le i \le \frac{n}{2}$, $2i$번째 고양이와 $2i+1$번째 고양이..

lower bound [s, e] 구간에 속한 원소 중 어떤 성질이 성립하는 가장 작은 원소를 $hi$에 담는다. 구간 내의 어떤 지점에서도 성질이 성립하지 않으면 $hi = e+1$이다. 1 2 3 4 5 6 7 8 // lower bound int lo = s-1, hi = e+1; // 1 while (lo + 1