본문 바로가기

문제 풀이

문제 풀이/그외 2020. 8. 22. SCPC 2020 Round 1 1. 다이어트 길이 \(N\)인 배열 \(A, B\)가 있다. 각 배열에서 원소를 \(K\)개씩 골라 (A의 원소, B의 원소)로 이루어진 순서쌍을 \(K\)개 만든다. 각 순서쌍의 합의 최대값을 최소화한 값을 알아내야 한다. \(A, B\)를 각각 정렬한 다음, \(A\)에서 가장 작은 \(K\)개의 값과 \(B\)에서 가장 작은 \(K\)개의 값만을 사용하자. \(A_i\)와 \(B_{k+1-i}\)를 각각 매칭 시켜주면 최적임을 알 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include using namespace std; typedef long ..
문제 풀이/Codeforces 2020. 8. 18. Codeforces Global Round 10 A - Omkar and Password Problem - A - Codeforces codeforces.com \(n\)길이의 배열 \(a\)가 주어진다. 이 배열의 연속된 두 원소 \(a_i, a_{i+1}\)를 골라서, 두 원소의 값이 다르다면 \(a_i, a_{i+1}\)를 삭제하고 그자리에 \(a_i + a_{i+1}\)를 추가하는 연산을 할 수 있다. 이 연산을 원하는 만큼 수행했을 때, 결과 배열의 길이의 최소값을 구해야 한다. 우선 모든 배열의 값이 같다면, 답은 \(n\)이다. 그렇지 않다면, 배열에서 가장 큰 원소를 하나 골라, 이 원소와 인접한 원소가 현재 원소와 같지 않다면 이 두 원소에 대해 연산하는 것을 반복하자. 그러면 무조건 배열의 길이를 1로 줄일 수 있음을 알 수 있다. ..
문제 풀이/Codeforces 2020. 8. 15. Educational Codeforces Round 93 A - Bad Triangle Problem - A - Codeforces codeforces.com \(n\)길이의 배열이 \(a\)가 주어진다. 이 배열은 비내림차순으로 정렬되어 있다. 이 배열의 서로 다른 인덱스 \(i,j,k\)를 골라, 변의 길이가 각각 \(a_i, a_j, a_k\)인 삼각형이 존재하지 않도록 만들 수 있는지 여부를 알아내야 한다. 가능하다면, 골라야 하는 인덱스를 출력한다. 삼각형의 세 변의 길이를 \(a,b,c\)라고 하고, 그 중 \(c\)가 가장 길다고 가정하자. 그러면 \(c \lt a+b\)여야 삼각형을 만들 수 있다. 다시 말하면 \(c \ge a+b\)이면 삼각형을 만들 수 없으므로, 가장 큰 수 1개와 가장 작은 수 2개를 골라 삼각형을 만들 수 있는지 확인하면..
문제 풀이/Codeforces 2020. 8. 10. Codeforces Round #663 (Div. 2) A - Suborrays Problem - A - Codeforces codeforces.com 다음을 만족하는 \(n\)길이의 순열 \(p\)를 알아내야 한다. - 모든 인덱스 쌍 \(i,j\) \((i \le j)\)에 대해, \((p_i\) OR \(p_{i+1}\) OR \(\cdots\) OR \(p_{j-1}\) OR \(p_j) \ge j-i+1\) \(a, b\)를 bitwise OR 한 결과는 \(\max(a,b)\)보다 작아지지 않는다. 모든 순열에 대해서, \(n\)개의 연속한 수 중에 \(n\)보다 크거나 같은 수가 항상 존재하므로, 모든 순열은 위를 만족한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26..
문제 풀이/Codeforces 2020. 8. 8. Codeforces Round #662 (Div. 2) A - Rainbow Dash, Fluttershy and Chess Coloring Problem - A - Codeforces codeforces.com \(n \times n\)크기의 격자가 있다. 이 격자를 한 사람은 파란색으로, 나머지 사람은 노란색으로 번갈아가며 칠해서 격자를 체스판 무늬로 만드려고 한다. 단 격자를 칠할 때, 새로 칠하는 칸들은 모두 이전에 칠해진 칸들과 인접해 있어야 한다. 초기에 격자 바깥에 있는 칸들이 이전에 칠해져있었다고 가정한다. 이 때, 필요한 최소 색칠 횟수를 구해야 한다. 관찰을 통해, \(\lfloor \frac n2 \rfloor + 1\)회가 최소임을 알 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ..
문제 풀이/Codeforces 2020. 8. 6. Codeforces Round #661 (Div. 3) A - Remove Smallest https://codeforces.com/contest/1399/problem/A codeforces.com \(n\)개의 원소를 가진 배열 \(a\)가 주어진다. 한 번의 연산으로, 배열의 서로 다른 두 인덱스 \(i,j\)를 고른다음, \(a_i\)와 \(a_j\)의 차이가 1 이하라면 둘 중 작은 값을 삭제할 수 있다. 두 값이 같다면 둘 중 아무거나 하나를 삭제한다. 이 연산을 반복해서 배열에 원소 1개만 남아있도록 하는 것이 가능한지 알아내야 한다. 배열을 정렬한다음, 인접한 두 원소를 각각 확인하자. 차이가 2 이상인 인접한 원소가 있다면 불가능하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ..
문제 풀이/Codeforces 2020. 8. 3. Codeforces Round #660 (Div. 2) A - Captain Flint and Crew Recruitment Problem - A - Codeforces codeforces.com 정수 \(n\)이 주어진다. nearly prime은 서로 다른 두 소수의 곱으로 나타낼 수 있는 정수를 말한다. \(n\)을 서로 다른 4개의 양의 정수의 합으로 나타내야 하는데, 그 중 적어도 3개가 nearly prime일 수 있는지 여부를 알아내고, 가능하다면 실해를 출력해야 한다. 가장 작은 3개의 nearly prime인 6, 10, 14와 \(n-30\)을 하면 일반적으로 답이다. \(n-30\)이 6, 10, 또는 14와 같거나 양의 정수가 아닐 경우 각각 예외처리를 해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ..
문제 풀이/Codeforces 2020. 7. 30. Educational Codeforces Round 92 A - LCM Problem Problem - A - Codeforces codeforces.com 정수 \(l, r\)이 주어진다. \(l \le x \lt y \le r\)을 만족하면서, \(l \le LCM(x,y) \le r\)을 만족하는 \(x,y\)가 존재하는지 알아내고, 존재한다면 출력해야 한다. 서로 다른 \(x,y\)에 대해서, \(LCM(x,y)\)가 가장 작아지는 경우는 \(y = 2x\)인 경우이다. \(2l \le r\)이면 \(l, 2l\)을 출력하면 되고, 그렇지 않다면 불가능하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using namespace std; typedef unsigned long l..

티스토리툴바