전체 글
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..
[Codeforce] Hello 2018
어느 블로그에서 좋은 문제들이 있는 셋이라고 들어서 버추얼을 돌렸다. A. Modular Exponentiation 문제를 설명하면 \(N,M\)이 주어지면 \(M\;mod\;2^N\)을 출력하는 문제, 간단해 보이지만 범위가 어마무시하게 크다. 잘 생각해보면 \(M n >> m; ll lo = log2l(m); if (lo
[Codeforce] Codeforces Round #696 (Div. 2)
버추얼 컨테스트 시간 내에 C번까지 풀 수 있어서 1400등 정도 좋은 등수를 얻을 수 있었다. A. Puzzle From the Future 문제를 설명하자면 이진수 \(A,B\)를 합쳐서 어떤 수 \(D\)를 만들려고한다. 만약 \(A,\)$가 각각 \(110,011\)이면 \(D=121\)이라는 수가 만들어진다. 또한 이 \(D\)는 121111 이런식으로 한 문자가 연속으로나타나면 \(121\)이런식으로 줄여버린다. \(B\)가 주어질때 \(D\)가 가장 크게 만드는 \(A\)를 찾는 문제이다. 사실 보면 문자열이 제일 긴 것이 가장 클 것이고, 이말은 즉슨 모든 문자가 달라야 된다는 것이다. 그리도 그 중에서 가장 커야 되니까 \(1\)을 넣을 수 있다면 넣는 방식으로 쉽게 만들수 있다. 7분 ..
[Codeforce] Educational Codeforces Round 103
너무 아쉬운 셋 A. K-divisible Sum \(N,K\)가 있고, \(N\)길이의 수열 \(A\)를 만들 수 있다고 한다. \(∑A_i\)이 성립하고 각 \(A\)의 원소들을 최소로 할때 그때 수열 \(A\)의 최대 원소를 묻는 문제이다. \(N \le K\)이면 \(\frac{N}{K}\)씩 나누어주고 나머지가 존재한다면 \(1\)씩 다시 나누어 주어야 하므로 답은 \(\frac{N}{K}\)이고, \(N\;mod\;K>0\)인 경우 \(1\)을 더해주면 된다. \(N>K\)이면 \(K\)개씩을적당히 분배해주면 된다. 답은 \(1\)이고 \(N\;mod\;K>0\)인경우 1을 더해준다. \(2\)번째 케이스에서 실수해서 9분컷했다. A-1.소스 코드 #include using namespace ..