상위 99.99%의 PS

https://codeforces.com/contest/1706 Dashboard - Codeforces Round #809 (Div. 2) - Codeforces codeforces.com 나는 미국 세터를 진짜 싫어한다. 문제들에서 유사코 맛이 난다... A (00:05) 그리디하게 무조건 앞쪽부터 A로 바꾸면 된다. B (00:16) 타워의 높이를 늘리는 조건은, 그 다음 수의 인덱스가 홀수만큼 떨어져 있는 것이다. C (00:29) N이 홀수일 때는 그냥 구하면 된다. N이 짝수일 때는, 단 한 곳에서만 2칸의 간격이 생기게 된다. 왼쪽 끝에서 1칸씩 띄고 누적 합을 만들고, 오른쪽 끝에서도 똑같이 해주자. \(L_{i} + R_{i + 3}\)의 최솟값이 답이다. D1 (01:10) \(x\)가..

골랜디. BOJ 22345 - 누적 거리 (G2) 더보기 배열을 좌표 기준으로 정렬하고, 각 쿼리마다 이분 탐색을 통해 인덱스를 찾으면 된다. 누적 합을 사용해야 안 터짐 BOJ 16207 - 직사각형 (G2) 더보기 두 개씩 짝을 지을 수 있는 막대들을 긴 것부터 사각형을 만들면 된다. BOJ 14941 - 호기심 (G2) 더보기 홀수 짝수 인덱스 누적 합 배열을 각각 만들어 주고, upper_bound로 소수 배열의 인덱스 구간\(l\), \(r\)을 찾을 수 있다. BOJ 2464 - 비밀번호 (G2) 더보기 코포 1A로 잘 나올 것처럼 생긴 문제다. 작은 수는, 가장 오른쪽의 '10'을 찾아서 '01'로 바꾼 다음, 이 뒤쪽에 나오는 1들을 왼쪽으로 싹 몰아주면 된다. 큰 수는 반대로 하면 된다...

A는 웰논이라 바로 풀었다. 증명은 예전에 다른 문제를 풀 때 해서 스킵했다. B는 재미가 없었는데, 코너케이스를 확인 할 때 continue를 안하고 그냥 return 0했다. 이거 때문에 그렇게 느낀 듯. C는 재밌었다. 이러고 gg쳤다. D는 잘 모르겠다. E는 문제만 읽고 그냥 껐다.

슬프다!!! A (00:10) 정렬하고 앞 절반 뒤 절반 비교하기 B (00:12) 0 개수 + sum(A_1 ... A_{N-1}) C (00:32) c

https://codeforces.com/contest/1703 Dashboard - Codeforces Round #806 (Div. 4) - Codeforces codeforces.com 재밌다. D부터 풀이를 쓰도록 하겠다. D (00:38) map을 사용해서 부분 문자열이 존재하는지를 찾으면 된다. E (00:18) 왼쪽 위 사분면에서 확인하면 된다. (a, b)는 (n - b, a), (n - a, n - b), (b, n - a)로 돌아간다. F (00:28) https://www.acmicpc.net/problem/10090 G (00:57) bad key를 사용했다면, 그 이후로는 무조건 bad key만을 사용하는 것이 이득이다. good key를 사용하는 쪽은 prefix sum을 사용하..

파이썬이라 당했다고 생각했지만, 그냥 해시 저격데이터로 당한 것이었다. 무지성 set이 아니라 cnt 배열로 서로 다른 원소들의 개수를 셌어야 했다. -150받고 블루로 내려가겠지만, 신기한 것을 배웠기에 딱히 화가 나지는 않는다. 근데 파이썬이라 당한거였으면 화가 났을 것 같다. 어쨌든, 아무리 내려가더라도 원래 있던 자리로 언제든 돌아갈 수 있으니 별로 짜증나는 건 없다. 블루에 있을 때는 레이팅에 목숨을 걸다시피 했는데, 깨달음을 얻고 퍼플로 올라오니 마음이 편안해진것 같다. positive delta를 항상 챙겨간다면 내가 퍼플(블루 강등예정)이 아니라 레드였겠지..라는 마인드도 코포에 부담을 느끼지 않게 도와줬다. 그래도 닉네임 색이 다시 파랑으로 돌아가는건 슬프다..ㅎ

백준을 요즘 대충하는 관계로 문제가 느리게 쌓였다. 게임을 줄여야 하는데... BOJ 16854 - 편안한 문자열 (G2) 더보기 "()))((()" 같은 대칭 여부, 올바른 괄호 문자열 여부를 확인하면 된다. 무지성 N^2. BOJ 16853 - 필름 (P3) 더보기 각 단색광은 독립적이기 때문에, 빨파초 3개를 각각 처리해주어 2-sat을 하면 된다. BOJ 25323 - 수 정렬하기, 근데 이제 제곱수를 곁들인 (G1) 더보기 정렬 후를 B라고 하면, A_i * B_i가 제곱수여야 정렬 가능한 형태가 된다. BOJ 16855 - 일해라, 류트! (P4) 더보기 r의 범위가 작으므로, 가능한 모든 순서쌍 \((r_i, r_{i+1})\)에 대해 전처리가 가능하다. 이를 통해 i번째의 약물을 언제 넣어..

https://www.acmicpc.net/problem/25213 25213번: 조각 케이크 (Hard) 조각 케이크들을 골랐을 때, 고른 조각 케이크를 모두 합쳐서 케이크 한 판으로 만들 수 있는 경우의 수를 출력한다. 답이 매우 커질 수 있으므로, \(10^9+7\)로 나눈 나머지를 출력한다. www.acmicpc.net [알고리즘 분류] Meet in the Middle Combinatorics Prefix Sum Meet in the Middle을 공부하고 풀어본 문제다. 몇 가지 관찰이 필요하다. 1. lcm(2~25)는 그렇게 크지 않으므로, 분모를 통일할 수 있다. (계산이 편해진다.) 2. 모든 크기의 조각들이 무한히 존재할 때, 이들을 잘 모아 케이크 한 판으로 만들기 위해서는 많아봤자..

https://codeforces.com/contest/1699 Dashboard - Codeforces Round #804 (Div. 2) - Codeforces codeforces.com 2000점은 확정이다. 3솔해도 오렌지 퍼포가 나오다니.. 나쁜 생활 습관으로 인한 역류성 식도염때문에 스트레스가 심해졌다. 진짜 늦어도 2시에는 자야겠다;; A (00:01) 짝수: n/2, n/2, 0 홀수: 불가능 B (00:07) 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 타일로 채우면 된다. C (00:23) 0, 1의 인덱스로 [L, R] 구간을 잡고 시작하자. 다음 수 k의 인덱스가 구간 [L, R]에 들어온다면, (구간의 크기) - k를 ans에 곱해주 자. k의 인덱스가 구간 밖에 존재..

조민수가 블루아카 픽업 20연챠에 뽑았다고 적어달라네요 라는 정신 나간 팀명을 들고, hodudragon0405, greedev, lem0nad3 (me)가 ucpc에 나가게 되었다. 팀명에 있는 저 이름은 블로그 공지에 있는 이름의 주인이다. 근데 팀원 3명 중 누구의 이름도 아니다 팀 연습으로 ICPC Regional Seoul 2018 ICPC Regional North America Championship 2022 shake! 2021 를 풀었는데, 위 2개는 진짜 힘들었다;; 나와 greedev에게도 너무 어려운 문제 셋이었는데, hodu에게는 더 어려울 게 당연했다. 그렇게 우리 모두의 자신감 상승을 위해 shake 2021을 풀었고, 3시간동안 7솔을 해냈다. 그렇게 본 대회에서 문제를 많이..