01.16 ~ 01.26 PS

[PS 기록들] - 01.01 ~ 0.15 PS

짜치게 notorious 뭐시기로 뚝딱한거는 취급 안 했다.

검수 했던 코드 공개됐을때 낸 것도 취급 안 했다.

백준에서 푼 것만 적었다.

열심히 좀 해보자.

• 16일. [P4] LRH 식물(http:boj.kr/2934)
• 17일. [G1] 모노디지털 표현(http:boj.kr/2287)
• 17일. [G1] 건포도(http:boj.kr/5463)
• 17일. [P5] 순열복원(http:boj.kr/1777)
• 18일. [P3] 달리기(http:boj.kr/16930) 추천!
• 18일. [P3] IQ Test(http:boj.kr/18665) 비추천!
• 18일. [P3] 수들의 합 3(http:boj.kr/2007) 추천!
• 18일. [P3] 버스(http:boj.kr/1161)
• 18일. [P5] 쿨한 물건 구매(http:boj.kr/1214) 추천!

• 나만 어렵게 푼 것 같긴 하더라.
• 시간 복잡도 맞출라고 루트로 쪼개고 DP 돌리고 gcd 빼주고 동전 공식 써주고 그렇게 풀었는데
• 그냥 대충 짜도 TLE 이슈 없이 맞는다는 것 같다.
• 내 풀이상으로는 P3 정도 받아야 할 것 같다.

• 19일. [P5] 호떡 뒤집기(http:boj.kr/31421) 추천!
• 20일. [P5] 동민 수열(http:boj.kr/1529)
• 21일. [D3] 교차 구간 크기 합(http:boj.kr/30808)
• 21일. [D4] 서로 다른 수와 쿼리 2(http:boj.kr/14898) 추천!

• PST를 개념만 알고 한 번도 안 짜봤는데, 저번에 Jakarta 2024 리저널을 돌면서 친구가 서로 다른 수 쿼리를 PST로 해결할 수 있다며 팀노트 달라길래 기억해뒀었다.
• 막상 PST로 짜봤는데 구현이 어렵진 않았고 그냥 PST를 어떻게 쓸 지 문제 아이디어 자체가 어려웠다.
• 이 정도로 쉽게 짤 수 있는 자료구조인 줄 알았으면 진작 배워둘 걸 그랬다.

• 21일. [D5] 송도고 레일 정비 사업(http:boj.kr/32223) 추천!

• 코드마스터 2024의 문제이다. 후배가 출제한 문제고, 굉장히 잘 만든 문제라고 생각한다.
• 몇 달 전에 보니까 과거 JOISC에 출제된 Abduction 2와 문제 상황이 겹쳐 보였고, 비슷하게 풀 수 있는 것처럼 보인다.
• 이 문제의 지문을 내가 뒤집으면서 동서-레일과 남북-레일이라는 워딩을 적용했는데 정확히 위 문제가 그 워딩을 사용하고 있어서 놀랐다.
• 이 글의 [18일]에 풀었던 달리기와도 철학이 공유되는 것 같기도 하고 아닌 것 같기도 하고...

• 23일. [P4] 유럽여행(http:boj.kr/1185)
• 23일. [P2] 티켓(http:boj.kr/2095) 추천! 웰메이드..
• 23일. [G3] 수학은 너무 쉬워(http:boj.kr/2904)
• 24일. 2025 선발고사 Day 1 오픈 컨테스트
• 24일. [P4] 과자의 분할(http:boj.kr/5561)
• 24일. [P5] 수열의 장인(http:boj.kr/10885)
• 24일. [P4] NP-hard(http:boj.kr/9520)
• 24일. [P4] 유니콘(http:boj.kr/1048) 추천! 뭔가 독특하다. 구현은 ㅅㄱ...
• 25일. [P5] 팩토리얼과 점화식(http:boj.kr/13439)
• 25일. [P4] PROSJEK(http:boj.kr/10742)
• 26일. [D5] XorSum(http:boj.kr/21860)

• 어제 새벽에 참가한 COCI 2024/2025 Contest #4에서 3번 문제를 로그제곱 풀이로 만점 직전까지 긁어뒀다.
• 로그만 떼면 되는 상황이었는데, 한국에서 같이 참가한 dadas08님이 백준에 똑같은 문제라고 소개해주셨다.
• 그래서 오늘 로그를 떼서 맞췄다.
• $2^k$ 비트가 켜졌다는 것은, $\sum_{i\le j}\left \lfloor \frac{a_i+a_j}{2^k} \right \rfloor$가 짝수라는 것.
• 이 식을 정리하면 $\frac{n+1}{2^k} \cdot \sum a_i - \sum_{i\le j} \left [ (a_i+a_j) \bmod {2^k} \right ]$이다. 첫 항은 쉽게 구할 수 있다.
• 또 정리하면 $\sum_{i\le j} \left [ (a_i+a_j) \bmod {2^k} \right ] = (n+1) \cdot \sum \left [ a_i \bmod {2^k} \right ] - 2^k \cdot g(k)$이다. 첫 항은 마찬가지로 쉽다.
  • 여기서 $g(k):=\sum_{i\le j} I \left\{(a_i\bmod{2^k}) + (a_j\bmod{2^k}) \ge 2^k \right \}$로 정의한다. $I\{\cdot \}$는 괄호 안의 명제가 참이면 $1$, 아니면 $0$인 함수이다.
• 이제 $g(k)$만 구할 수 있으면 끝난다.
• 로그제곱 풀이: $b_k[i]:=a_i\bmod{2^k}$라면, $b_k[\cdot]$을 항상 오름차순으로 정렬해두고 이진탐색으로 $O(n \log n)$에 매 $g(k)$를 계산한다. 따라서 전체 시간 복잡도는 $O(n\log n\log A)$이다.
• 로그 풀이: $b_k[i]$를 전부 오름차순으로 정렬하는 것을 가려뒀던 비트를 하나씩 펼쳐주는 식으로 상위 비트의 정렬 결과를 빌려서 정렬해나가는 방식으로 구현하면 일단 정렬에 필요한 시간 복잡도에서 로그가 하나 떼진다. 그리고, $g(k)$에서 이진탐색으로 수행했던 부분을 양쪽에서 시작하는 두 포인터로 처리하면 매번 $O(n)$에 된다. 따라서 전체 시간 복잡도는 $O(n\log A)$이다.

• 26일. [P3] 점프(http:boj.kr/32383)