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 ..

이번 학기에 어떤 일이 있었는지 간단하게 정리해두려고 한다. 1학기와 마찬가지로 알고리즘 학술소모임 CTP에서 활동했다. 주 2회 스터디에 참여했고, 스터디 때는 ruz님의 알고리즘 강의를 듣거나 시간 제한을 두고 문제를 풀었다. 각자 알고리즘 하나씩 선택해서 블로그에 포스팅하고 스터디 시간에 발표했는데, 나는 스프라그 그런디 정리를 골랐다. 스터디를 계기로 미뤄뒀던 알고리즘을 공부할 수 있었다. 39dll님, yooshnn님과 함께 인하대학교 프로그래밍 경진대회 IUPC에 참가했고, 대상을 수상했다. 이에 대해서는 여기에 자세히 기록해두었다. IUPC가 끝나고 일주일 뒤에 ruz님, 12201808님과 함께 ICPC에 참가했다. 당일 문제 배분과 내 실수 때문에 결과가 좋지 못했다. 그래도 팀원들과 같..

A. Robot Cleaner Problem - A - Codeforces Problem - A - Codeforces codeforces.com \(n \times m\) 사이즈의 보드판이 주어진다. 로봇의 좌표는 \((r_b, c_b)\), 목표칸의 좌표는 \((r_d, c_d)\)이다. 로봇은 1초마다 \((dr, dc)\)만큼 움직인다. 즉, \((r, c) \rightarrow (r+dr, c+dc)\) 초기 \(dr=1, dc=1\)이다. 수직벽에 닿으면 \(dc \rightarrow -dc\), 수평벽에 닿으면 \(dr \rightarrow -dr\)로 값이 변한다. 로봇은 다음 칸으로 이동하기 전에 현재 행과 열을 청소한다. 목표칸을 청소하기까지 몇 초가 걸리는지 구하는 문제이다. 가로 방..

A. Construct a Rectangle Problem - A - Codeforces Problem - A - Codeforces codeforces.com 세 막대 \(a, b, c\)가 주어진다. 이 중 하나의 막대를 쪼개 두 개의 막대로 만든다. 막대 네 개로 직사각형을 만들 수 있으면 YES, 없으면 NO이다. WLOG, 막대 \(c\)를 쪼갠다고 가정하자. \(c\)를 쪼개어 얻은 막대 두 개를 각각 \(p, q\)라고 하자. 다음과 같이 경우를 나눌 수 있다. 1) \(p\)와 \(q\)가 마주보는 경우: \(c \% 2 = 0\) and \(a = b\) 2) \(p\)와 \(q\)가 이웃한 경우: \(a + b = c\) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ..

A. Closing The Gap Problem - A - Codeforces Problem - A - Codeforces codeforces.com 타워 \(n\)개가 주어진다. 타워의 최대 높이 - 최소 높이의 값을 최소화하는 문제이다. 타워들의 높이 합이 \(n\)으로 나누어 떨어지면 0, 나누어 떨어지지 않으면 1이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include using namespace std; typedef long long ll; typedef pair pii; int main(void) { int t; cin >> t; while (t--) { int n; cin >> n; int sum = 0; for (int i = 0; i > t..

A. Erasing Zeroes Problem - A - Codeforces Problem - A - Codeforces codeforces.com 길이 \(n\)의 binary string \(s\)가 주어진다. \(1\)과 \(1\) 사이에 존재하는 \(0\)의 개수를 세는 문제이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include using namespace std; int main(void) { int t; cin >> t; while (t--) { string s; cin >> s; int cnt = 0; int prv = -1; for (int i = 0; i > g >> b; ll h = (n + 1) / 2; ll q = h / g; l..

A. Three Strings Problem - A - Codeforces Problem - A - Codeforces codeforces.com 길이 \(n\)의 문자열 \(a, b, c\)가 주어진다. \(a\)의 \(i\)번째 문자를 \(a_i\)라고 하자. (\(b_i, c_i\)도 동일하게 정의) \(i(1\le i \le n)\)에 대해, \(c_i\)를 \(a_i\) 또는 \(b_i\)와 바꾼다. 모든 swap이 끝났을 때 \(a\)와 \(b\)가 같아질 수 있으면 YES를, 그렇지 않으면 NO를 출력한다. \(c_i \ne a_i\) && \(c_i \ne b_i\)를 만족하는 \(i\)가 존재하면 NO이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ..

다음 조건을 만족하는 게임에 대해 논의할 것이다. 이는 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를 잡고 있던 시은 님과 상의하고 문제를 바꿨다. 생각보다 금방 아이디어를 떠올려서 바로 구..