본문 바로가기

반응형

codeforces

[Codeforces] Round #709 (div. 2) A ~ D 풀이 2021.03.21 22:20 ~ 00:35 본 라운드 참여 (performance = 1844) 테크노컵은 뭔가 항상 어려운 느낌이다... 생각보다 퍼포먼스가 나쁘지 않게는 나왔는데, 개인적으로 요즘 코포 폼이 조금 올라왔다고 생각해서 더 아쉬운 기분이 든다. A. Prison Break (*800) 모든 칸들에서 밖으로 나갈 수 있기 위해서 제거해야 하는 벽의 수의 최소를 구하는 문제이다. 답은 가로 * 세로, 즉 칸의 개수이고 대회중에는 직관적으로 빠르게 해결했다. 정확한지는 모르겠으나 증명을 하자면, 각 칸마다 해당 칸에서 시작해서 밖으로 나갈 수 있는지 없는지를 상태로 표현하고, 벽이 제거된 이웃한 칸은 하나의 칸으로 합쳐진다고 생각하자. 벽을 하나 제거했을 때 밖으로 나갈 수 없었던 2개 이상..
[Codeforces] Round #559 (Div. 2) A ~ E 풀이 21.03.05 23:35 virtual 참가 / performance = 2391 A. A pile of stones (*800) +가 주어질 때는 돌이 1개 증가하고, -가 주어질 때는 돌이 1개 감소한다. 처음에 보유할 수 있는 돌은 임의로 정할 수 있고, 중간에 돌이 0개일 때 -가 들어오면 안 될 때, 최종적으로 가능한 최소 돌의 개수를 구하는 문제이다. 처음의 돌 수를 직접 정할 수 있으므로, 단순하게 -가 들어오는 경우, 만약 현재 돌이 0개이면 그대로 유지시켜주면 된다. 이 과정이 결국 처음의 돌 수를 1개 증가시키는 과정과 동일하다. [소스 코드] #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin..
[Codeforces] Educational Round 102 A ~ E 풀이 2달 만에 본계로 참가했다. 부계로 계속 못 올라가는 게 현타 와서 마음을 다 비우고 본계로 했는데 약간 올랐다... 한동안 1800 퍼포 이상을 찍어본적이 없었는데 아이디에 적응하는 건가....? CF 1473A. Replacing Elements 배열의 어떤 원소를 다른 두 원소의 합으로 바꿀 수 있다. 이때, 배열의 모든 원소를 d 이하로 만들 수 있는지에 대한 문제이다. 기본적으로 주어지는 모든 원소가 d 이하이면 아무런 작업을 하지 않아도 된다. 만약 d보다 큰 원소가 하나 이상 존재한다면, 해당 원소를 바꿔주는 최적의 경우는 배열의 모든 원소 중 제일 작은 값 2개를 골라 바꿔주는 경우이므로, 배열을 오름차순으로 정렬하여 A[1] + A[2]가 d이하이면 YES이다. [소스코드] #includ..
[Codeforces] Round #694 (Div. 2) 풀이 2021. 01. 05 23:35 본 라운드 참가 실력이 정체되어있다. 예전엔 더 올라갈 수 있는데 운이 안 따라주는 느낌이었다면 지금은 느낌이 좀 다르다.... 재활이 꽤 오래 걸릴 것 같다. 1471A. Strange Partition 주어진 배열에서 인접한 두 원소를 대신해서 두 원소의 합으로 대체할 수 있다. 배열의 원소는 1개만큼 줄어든다. 이 연산을 원하는 만큼 한 후에, 배열의 각 원소를 x으로 나눈 값을 올림 하여 모두 더한 합의 최솟값과 최댓값을 구해야 한다. 최대인 경우는 연산을 한번도 하지 않은 원래의 배열에서 합을 구해주는 경우이고, 최소인 경우는 연산을 n-1번 적용한, 즉 배열의 원소가 1개만 남았을 때이다. [소스 코드] #include using namespace std; u..
[Codeforces] Round #551 (Div. 2) A ~ D 풀이 2021.01.03. 15:00 virtual 참가 / performance = 1563 [풀이] 1153A. Serval and Bus (*1000) 버스별로 정류장에 처음 도착하는 시간과 배차간격이 주어질 때, 버스정류장에 t초에 도착했을 때 제일 먼저 탈 수 있는 버스를 구하는 문제이다. 처음에 A번치고 생각보다 까다로웠으나, n이 100이고 t가 10만이기 때문에 각 버스별로 정류장에 도착하는 시간을 모두 구해줘도 무방하다. 나는 priority_queue를 이용하여 현재 pq에 담겨있는 버스들의 도착 시간 중에 제일 빠른 것을 확인해서, t보다 작다면 배차간격만큼 더해줘서 다시 넣어주고, 처음으로 t보다 큰 값이 나온 경우에 출력을 해주었다. #include using namespace std;..
[Codeforces] Educational Round 76 (A ~ E) 풀이 2021.01.01 23:00 virtual 참가 / Performance = 1841 [풀이] 1257A. Two Rival Students 수직선상에 두 사람이 서있고, 한번 작업을 수행하면 두 사람의 거리를 1만큼 더 멀게 할 수 있다. 최대 x번 작업을 수행할 수 있으므로, 멀어질 수 있을 만큼 최대한 이동시켜준다. int main(void) { int T; cin >> T; while (T--) { int n, x, a, b; cin >> n >> x >> a >> b; if (a > b) swap(a, b); cout T; while (T--) { int x, y; cin >> x >> y; if (x >= y) cout > n; vector cnt(n + 1); int ans = MAX; f..
Codeforces Round #690 (Div. 3) 풀이 A. Favorite Sequence 입력으로 문제의 그림과 같이 위치가 바뀐 수열이 들어온다. 다시 원래의 수열을 출력해주면 된다. (처음엔 바뀐 수열을 출력하라는 줄 알았다. 꽤나 비슷한 실수를 한 사람들이 많은 것 같다) #include using namespace std; int A[301]; int main(void) { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int T; cin >> T; while (T--) { int n; cin >> n; for (int i = 1; i > A[i]; for (int i = 1; i
Round #686 (Div. 3) 후기 및 풀이 처음으로 '언레가 되어버린 라운드'가 아닌 '언레로 적용되는' 라운드에 참여했다. 사실 부계도 1600을 이미 넘겨서 그냥 잘까 하다가 코포 중독증에 걸려버린 나로서는 그냥 자기는 아쉬워서 참가했는데 그냥 잤어야 했다... 다음날이 너무 힘들었다. 가볍게 참가해서 제출도 대충대충 하다 보니 WA가 많이 나왔다. rated 라운드였어도 신중하게 제출하지 않았을 것 같아서 조금 주의할 필요가 있을 것 같다. A. Special Permutation p[i] != i 를 만족하는 순열을 만드는 것이다. 1, 2, ... n 순서대로 구성된 순열을 한 칸씩 밀기만 하면 만족한다. #include using namespace std; int main(void) { ios::sync_with_stdio(false)..