본문 바로가기

문제 풀이

문제 풀이/Codeforces 2021. 3. 20. Educational Codeforces Round 106 A - Domino on Windowsill Problem - A - Codeforces codeforces.com \(2 \times n\)크기의 격자가 있다. 첫번째 열의 첫 \(k_1\)개 칸과 두번째 열의 첫 \(k_2\)개 칸이 흰색으로 칠해져 있고, 그 외의 칸은 검은색으로 칠해져 있다. \(w\)개의 흰색 도미노와 \(b\)개의 검은색 도미노가 있다. 도미노의 크기는 모두 \(2 \times 1\)이고, 두 칸의 도미노의 색과 격자의 칸이 모두 같으면 그곳에 도미노를 놓을 수 있다. 도미노를 겹쳐서 놓을 수는 없을 때, 모든 도미노를 격자에 놓는 것이 가능한지 알아내야 한다. 관찰을 잘 하면, 각 색깔의 도미노의 면적보다 격자의 면적이 더 작지만 않으면 무조건 가능하다는 것을 알 수 있다. ..
문제 풀이/Codeforces 2021. 3. 18. Codeforces Round #708 (Div. 2) A - Meximization Problem - A - Codeforces codeforces.com \(n\)길이의 배열 \(a\)가 주어진다. 이 \(a\)의 원소들의 순서를 재배열해서, 모든 prefix의 MEX값의 합이 최대가 되도록 해야 한다. 큰 MEX값이 최대한 빨리 나와야 함을 알 수 있다. 앞에서부터 \(a_i = i\) (0-index)가 되도록 최대한 수를 채우면 된다. 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 38 39 40 41 42 43 44 45 46 47 #include using namespace std; typedef long lon..
문제 풀이/Codeforces 2021. 3. 14. Codeforces Round #707 (Div. 1, Div. 2) A - Alexey and Train Problem - A - Codeforces codeforces.com 하라는 대로 구현하면 된다. 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 38 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; } int n; int a[101], b[101]; int tim[101]; int main() { ios::sync_..
문제 풀이/Codeforces 2021. 2. 19. Codeforces Round #703 (Div. 2) A - Shifting Stacks Problem - A - Codeforces codeforces.com \(n\)묶음의 블록이 있다. 각각의 묶음에는 \(h_i\)만큼의 벽돌이 있다. \(i\)번째 묶음에서 (블록이 1개이상 존재한다면) 블록 하나를 \(i+1\)번째 묶음으로 옮기는 연산을 할 수 있을 때, 블록의 개수가 오름차순이 되도록 할 수 있는지 알아내야 한다. 직접 시뮬레이션 하자. \(i\)번째 묶음에 \(i\)개의 블록만을 놔두고 나머지는 전부 다음 묶음으로 옮기면 된다. (0-index) 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 38 39 #inc..
문제 풀이/Codeforces 2021. 2. 2. Educational Codeforces Round 103 A - K-divisible Sum Problem - A - Codeforces codeforces.com 두 정수 \(n, k\)가 주어진다. \(n\)길이의 양의 정수 배열 \(a\)를 만드는데, \(a\)의 모든 원소의 합이 \(k\)로 나누어 떨어져야 하고 \(a\)의 원소중 최대값이 최소가 되어야 한다. 이 때 \(a\)의 원소의 최대값을 구해야 한다. 해설은 생략한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; ll gcd(ll a, ll b) { for (; b; a %= ..
문제 풀이/Codeforces 2021. 1. 31. Codeforces Round #698 (Div. 1, Div. 2) A - Nezzar and Colorful Balls Problem - A - Codeforces codeforces.com \(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 27 28 29 30 31 32 33 34 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; l..
문제 풀이/Codeforces 2021. 1. 21. Codeforces Round #696 (Div. 2) A - Puzzle From the Future Problem - A - Codeforces codeforces.com \(n\)길이의 이진 문자열 \(b\)가 주어진다. 여기에 새로운 \(n\)길이의 이진 문자열 \(a\)를 만들어서, 두 이진 문자열을 더하려고 한다. 두 이진 문자열은 자리올림 없이 더해진다. (결과에 2가 포함되어 있을 수 있다) 더해진 다음, 연속된 같은 숫자들은 1개로 압축된다. 두 이진 문자열을 더했을 때 합이 최대가 되는 \(a\)를 알아내야 한다. 자릿수가 클 수록 큰 수가 되므로, 더한 후에 연속된 같은 숫자들이 없는것이 무조건 이득이다. 이를 만족하도록 앞에서부터 더한 결과가 최대한 큰 수가 되도록 \(a\)를 만들어 주면 된다. 1 2 3 4 5 6 7 8 9 10 1..
문제 풀이/Codeforces 2021. 1. 8. Codeforces Round #694 (Div.1, Div. 2) A - Strange Partition Problem - A - Codeforces codeforces.com \(n\)길이의 배열 \(a\)가 주어진다. 이 배열의 인접한 두 원소를 합치는 연산을 원하는 만큼 할 수 있을 때, \(\sum^k_{i=1} \lceil \frac{b_i}{x} \rceil\)의 최소값과 최대값을 구해야 한다. 배열의 값을 전부 합쳤을 때가 최소값이고, 한 번도 합치지 않았을 때가 최대값이다. 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 #include using namespace std; typedef long long ll; typedef pai..

티스토리툴바