PS/Codeforces
AtCoder Beginner Contest 254
A - Last Two Digits 단순 문자열 문제입니다. B - Practical Computing 문제에서 주어진 대로 구현하면 됩니다. C - K Swap 관찰하면 인덱스 \(i\)가 \(k\)로 나눈 나머지 끼리의 위치끼를 서로 swap을 해줄 수 있습니다. 그러므로 같은 나머지끼리 묶인 그룹들은 무조건 오름차순으로 정렬할 수 있습니다. 나눈 그룹들을 전체로 합친 다음 오름차순의 결과와 같은 지 확인해주면 됩니다. 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 48 49 50 51 52 53 54 55 56 ..
AtCoder Beginner Contest 243
A - Shampoo \(V\)를 \((a+b+c)\)의 합으로 나뉘어주고, 시뮬레이션을 해주면 풀 수 있다. 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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC opt..
Codeforces Round #777 (Div. 2)
A. Madoka and Math Dad 각 자릿수의 합이 N이고, 0을 제외한 숫자를 사용하고, 연속된 같은 문자가 없는 큰 수를 만드는 문제이다. 먼저 1, 2만 사용하는 것이 가장 이득이고, dp[i] = 각 자릿수의 합이 i일 때 최대 숫자로 정의하면 쉽게 풀 수 있다. 6분컷했다. 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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 8..
Codeforces Round #725 (Div. 3)
A. Stone Game 문제는 순열이 주어진다. 순열에서 앞과 뒤에서 연속적으로 빼내는 최소한의 연산으로 순열의 최댓값과 최솟값을 빼내야 된다. 최댓값, 최솟값 인덱스를 \(a,b(a
Codeforces Round #702 (Div. 3)
처음으로 Div.3 올솔했다. A. Dense Array 어떤 두 수 사이에 비율이 \(2\)이하로 내려가게 임의 수를 추가해준다면 작은 수를 계속 \(2\)를 곱해가면서 추가해주면 된다. 8분컷했다 A-1. 소스코드 #include using namespace std; typedef long long ll; typedef pair pi; typedef pair pll; int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int tc; cin >> tc; while (tc--) { int n; cin >> n; vector arr(n); for (int i = 0; i > arr[i]; int ans = 0; for (int i = 1; i =..
[Codeforce] Educational Codeforces Round 104 (Rated for Div. 2)
이번 정올 1차 결과를 보고 Competive Programming를 더 연습해야 겠다는 생각이 들었다. 1차는 무난하게 합격했지만, 조금만 더 빨리 생각했다면 풀 수 있는 문제들이 있었다. A. Arena 문제를 요약하자면 각 레벨이 있고, 임의의 히어로 두쌍을 싸움을 시키면 레벨이 높은 쪽이 레벨이 \(1\) 올라갈 때, 레벨이 \(10^{500}\)이상 올라가는 히어로가 몇 명인지 묻는 문제이다. 간단하게 생각하자면 자신보다 낮은 레벨이 있다면 무한으로 갈 수 있기 때문에 오름차순으로 정렬하고 첫번째 원소와 비교할 때 자신이 더 크면 답에 \(1\)을 더해주는 형식으로 문제를 해결할 수 있다. 2분컷했다 A-1. 소스코드 #include using namespace std; typedef long ..
[Codeforce] Codeforces Round #701 (Div. 2)
C번까지 풀었는데 내 기준으로 높은 등수를 받았다. A. Add and Divide 문제를 설명하면 \(A,B\)가 있는 데 두가지 행동을 할 수 있다. 첫번째 행동은 \(A=[\frac{A}{B}]\)이고, 두번째 행동은 \(B++\)이다. 이 행동을 통해 \(A=1\)을 만드는 최소행동수를 출력해라. 처음보고 어떻게 풀지 막막하다가 생가이 안나서 완전탐색을 하기로 했다. 각 가능한\(B\)에 대해 모든 경우를 다해보는데 어떤 \(B\)에 대해 \(A=1\)을 만드는 횟수는 최대 \(O(logA)\)이고, 가능한 \(B\)는 잘 커팅해주면 된다. \(B\)가 증가할수록 어떤 전역 최소점이 존재할텐데, 이것을 판별하는 방법은 \(B\)일 때 횟수, \(B+1\)일 때 횟수가 증가하는 형태이면 그 순간 커..
[Codeforce] Codeforces Round #697 (Div. 3)
A. Odd Divisor 문제를 설명하면 어떤 \(N\)이 주어졌을 때, 인수 중에 홀수가 있는 지 묻는 문제이다. 먼저 홀수는 무조건 가능하다. 그러면 짝수일 때는 어떻게 처리하자면, \(N\)의 인수를 구해주면서 계속 나누어주고, 남은 수가 홀수가 되면 가능한 숫자이다. 이 과정이 최대 \(O(\sqrt{N})\)인데, 이런 저격케이스가 없어서 가능한가 보다. 에디토리얼을 보면 짝수 중에 안되는 케이스는 \(2^N\)꼴 밖에 없다고 한다. 그래서 판별하는 방법으로 \(N&(N−1)=0\)로 한번에 계산해줄 수 있다고 한다. 7분 컷했다. A-1. 소스코드 #include using namespace std; typedef long long ll; typedef pair pi; typedef pair..