Codeforces Round #695 (Div. 2) 후기
Codeforces Round #695 (Div. 2) A. Wizard of Orz 약간 함정스러운 문제였다. 무조건 \(989\cdots \)로 시작하는게 가장 크다. B. Hills And Valleys \(a_i\)를 바꿨을 때, 개수가 변하는 요인은 \([a_{i-2},a_{i-1},a_i]\)과 \([a_{i-1},a_{i},a_{i+1}]\)과 \([a_{i},a_{i+1},a_{i+2}]\)로 세 가지 뿐이니 \(a_i\)를 적당히 바꾼 뒤에 개수를 비교해주면 된다. 이 때 적당히가 어느정도인지가 관건인데, \(a_{i-1}\)또는 \(a_{i+1}\) 중 하나가 답이 될 수 있다. 나는 대회 때는 적당히 저 둘을 포함한 \(10\)가지 정도 다 검사했다. C. Three Bags 첫 문단..
Codeforces Round #694 (Div. 1) 후기
Codeforces Round #694 (Div. 1) A. Strange Birthday Party 처음엔 감도 안 잡혀서 포기할까 생각하다가 조금 더 고민해보니 \(c\)를 기준으로 이분탐색할 수 있다고 생각했는데 그렇게 거의 다 짜고난 뒤에 안 된다는걸 깨달았다. 그래서 더 고민해보니 \(k\)를 기준으로 정렬한 뒤 앞에서부터 몇번째까지는 현금으로 주고 나머지에게 선물을 주는 식으로 계산을 할 수 있었다. 그리고 그 방식이 가능한 시점은 이분탐색으로 찾을 수 있다. 이렇게 구현했는데, 구현도 매끄럽게 안 되고 심지어 냈는데 한 번 틀리기까지 해서 이미 멘탈이 나갔다. B. Strange Definition 보자마자 소인수분해하고 각 소인수의 개수의 홀짝이 모두 같은 쌍이 인접한 거라는건 알았는데 일..
Codeforces Round #541 (Div. 2) 후기
Codeforces Round #541 (Div. 2) 보라색 달려고 2시간 정말 꽉꽉 채워서 해봤다... A. Sea Battle생각해보면, 모든 경우에서 \(4+2\text{max}(w_1,w_2)+2h_1+2h_2\)가 답이 된다.대충 생각해보고 그냥 제출해놨다가 다른거 다 풀고 다시풀려고했는데, 시간을 풀로 써서 다시 풀 시간이 없었다.그래도 이 방법이 맞아서 다행이다. 12345678910#include int main() { int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d); printf("%d", 4 + 2 * (std::max(a, c) + b + d)); return 0;}Colored by Color Scriptercs B. Draw!일단 \..
Pictures with Kittens (easy version) (http://codeforces.com/problemset/problem/1077/F1) Pictures with Kittens (hard version) (http://codeforces.com/problemset/problem/1077/F2) 난이도가 easy가 2100, hard가 2300인데 사실 그 정도는 아닌 것 같다. Div3 마지막 문제들이었는데 내 힘으로 풀어서 조금 뿌듯하다. 근데 대회에서 푼 건 아니라서 조금 아깝다. 이런 dp 최적화는 간단하고 충분히 또 나올만 해서 풀이를 적어둬야겠다. easy는 간단하게 dp로 풀 수 있다. 일단 \(D_{i,j}\)를 \(i\)번째 사진을 선택하고 총 \(j\)개를 골랐을 때의..
Codeforces Round #520 (Div. 2) 후기
Codeforces Round #520 (Div. 2) 사실 B번은 너무나도 틀리기 쉬운문제라서 내 것도 당연히 반례가 있을거라고 생각하긴 했다. 그래도 왠만한거 다 해보고 잠근다음에 핵을 하려 했는데... 너무 졸려서 그냥 중간에 잤다. 시스템테스트에서 너무 많이들 틀려서 순위가 크게 바뀌지 않은게 다행이긴 하다. 레이팅이 1814에서 1825로 11점 올랐는데, B번을 맞았으면 50점은 올랐을 것 같은데 조금 아쉽다. 다시 떨어지더라도 보라색 달고싶은데... A. A Prank 증가하는 수열에서 다시 복구할 수 있도록 원소들을 지우라는건데, 당연히 1씩 증가하는 부분의 길이를 구하면 된다. 문제는 복구할 때 원소들이 1부터 1000사이라는 점인데, 수열 양 옆에 1과 1000을 넣어두면 깔끔하게 처리..
Cloud Computing (http://codeforces.com/problemset/problem/1070/C) \(1\sim n\)번 칸에서 각각 최대 \(k\)개의 코어를 사야 하는데, 당연히 살 수 있는 코어 중에서 가격이 싼 것 부터 차례대로 사는게 이득이다. 그렇다고 계획들을 정렬한 뒤 싼 것부터 하나하나 추가해가다보면, 어떤 칸에서 코어를 \(k\)개 넘게 샀는지를 확인하기 힘들다. 그래서 계획별로 보지 않고, 칸 별로 어떤 계획을 사용할지를 확인해야한다.현재 \(i\)번째 칸에서 적용할 계획을 확인하고 있다면, 구간에 \(i\)가 포함되는 계획들을 찾아야 한다. 어차피 \(1\)번째 칸부터 \(n\)번째 칸까지 차례대로 볼 것이므로, \(i\)가 계획의 시작점일 때 계획 후보에 넣고, ..
Educational Codeforces Round 50 (Rated for Div. 2) 후기
Educational Codeforces Round 50 (Rated for Div. 2) A. Function height 문제 설명도 길고 그래프까지 나와있어서 무서웠는데, 해석만 하면 간단하다. 어떤 점의 높이를 1올리는 것은 넓이를 1올리는 것과 같다. 그러니 점들에 넓이를 나눠준다고 생각하면 된다.12345678910#include int main() { long long n, k; scanf("%lld %lld", &n, &k); printf("%lld", (n + k - 1) / n); return 0;}Colored by Color Scriptercs B. Diagonal Walking v.2 우선 \(k\)보다 큰 좌표에는 도달할 수 없다. 그리고, \(x\)좌표와 \(y\)좌표 모두 마..