Loading [MathJax]/jax/output/CommonHTML/jax.js

전체 글 10

Codeforces #819

A. Mainak and Array 길이 n의 배열 a가 주어진다. 배열의 [l,r] 구간을 선택, 원하는만큼 cyclically rotate하는 연산을 한 번 수행하여 얻을 수 있는 ana1의 최댓값을 구하는 문제이다. 다음과 같이 경우를 나눌 수 있다. 1) a1,an 미포함: ans=ana1 2) a1만 미포함: ans=max(a2,a3,...,an)a1 3) an만 미포함: ans=anmin(a1,a2,...,an1) 4) a1,an을 모두 포함: ans=max1in(ai1ai) (단, ..

Codeforces 2022.09.26

Equivalence Relation and Partition

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

알고리즘 2022.07.06

Codeforces #763

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

Codeforces 2022.01.02

Codeforces Educational #120

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

Codeforces 2022.01.02

Codeforces Global #18

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

Codeforces 2021.12.26

Codeforces #619

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

Codeforces 2021.12.23

스프라그-그런디 정리

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

알고리즘 2021.11.05

Codeforces #728

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

Codeforces 2021.07.17
1