2024-05-21 PS 공부

PS/공부

woojin042 2024. 5. 21. 22:08

시험 기간에 기분 전환할 겸 랜디를 돌렸습니다!

코드포스 스타일의 문제를 조금 연습하고 싶어서 그리디, 수학, 애드 혹, 구성적, 조합론, 정수론 문제 중 S2 ~ G3인 문제들을 골라 풀었습니다.

방정식 $x^3 = 1$의 허근 $\omega$의 성질을 잘 활용하면 되는 문제이다.

H를 기준으로 앞에 있는 W의 개수와 뒤에 있는 E의 개수를 적절히 세어 주면 된다.

H 앞에 W가 W[i]개만큼 있고, 뒤에 E가 E[i]개만큼 있으면, 만들 수 있는 유사 휘파람 문자열의 수는 $W[i] \cdot (2^{E[i]}-E[i]-1)$ 개이다.

W[i]와 E[i]를 누적합 비슷한 dp로 처리해주고, 모든 H에 대해 결과를 더해주면 답이 된다.

단, 이 때 2의 거듭제곱이 너무 커질 수 있기 때문에 전처리로 2의 거듭제곱을 mod한 값을 계산해 주어야 한다..!

- tag: number_theory

- link: boj.ma/1241

각 학생별로 자신의 약수를 들고 있는 학생이 몇 명인지 세는 문제이다.

나는 Harmonic lemma를 이용해 풀었다. 수 크기의 제한이 백만 이하이기 때문에, 1부터 백만까지의 모든 약수-배수 쌍을 for문으로 순회해도 시간복잡도는 $O(m\log{m})$이 된다! (m은 숫자의 크기 상한)

굳이 이렇게 생각하지 않아도 약수 판별을 $O(\sqrt{m})$에 할 수 있기 때문에 각 수마다 모든 약수를 구하는 식으로 풀어도 간당간당하게 통과하는 것 같다.

연속한 수들의 XOR을 구하는 문제이다. $1$부터 $n$까지의 모든 수를 XOR한 값은, $1$부터 $n$까지의 모든 자연수에서, 각 자리에서 켜진 비트가 나오는 개수를 카운팅해서 구할 수 있다.

따라서, $1$부터 $B$까지의 XOR 값을 구해 각 비트별 등장 빈도를 나타내는 배열을 채우고, $1$부터 $A-1$까지의 XOR 값을 구해 만든 배열에서 값들을 빼주면, 결론적으로 $A$부터 $B$까지의 모든 자연수를 XOR한 값을 알 수 있게 된다!

비트 연산자를 long long 범위에서 사용할 때 1LL처럼 상수의 타입을 고려해주지 않아 맞왜틀을 조금 했다 ㅠㅠ

별해로 0부터 숫자 네 개씩 끊어 XOR하면 항상 값이 0이 나온다고 한다..? 이왜진?

위의 25306번 문제의 십진수 버전이다. 기여 창에 문제 번호가 있어서 풀어보았다.

이전과 똑같이 카운팅해 주면 되는데, 00010과 같은 숫자에선 앞의 세 0은 세 주면 안 되므로, 0은 따로 처리해 주어야 한다.

아무래도 태그에 수학이 껴 있다 보니 정수론/조합론이 아닌 수학 문제가 꽤 많이 나온 것 같네요 ㅠㅠ

다음에는 tag:math는 빼고 돌려야 할 듯