본문 바로가기

2021-09-10 Problem Solving 11385. 씽크스몰 단순히 다항식의 곱셈을 FFT로 수행하면 해결할 수 있어 보인다. 하지만, 입력되는 수의 범위를 살펴보면, long double을 써도 맞기 쉽지 않음을 알 수 있다. 나는 조금 더 안전 빵으로, 소수 두 개를 이용해 NTT를 두 번 한 후, CRT를 이용해 계수들을 복원하여 문제를 해결했다. 19265. Is it a p-drome? 모든 값을 0-based index로 생각하자. 어떤 문자열이 $p$-drome 이라면, $p$를 적용한 결과물과 해당 문자열의 라빈 핑거프린트 해시 값이 같을 것이다. 고로, $i$에서 시작하는 길이 $m$인 문자열을 본다고 할 때, 원래 문자열의 해시 값은 $\sum_{j=0}^{m-1} a_{i+j} x^j$ 이 될 것이고, $p$를 적용한 결과..
"쿨 함"을 요구하는 사회에 반대한다. 몇 년 전부터 우리 사회에서는 자신에게 좋지 않은 일이나 갈등 등에 대해 소위 "쿨 하게" 대처하는 사람에 대한 예찬이 있었다. 이렇게 쿨한 모습을 보여주는 것은 대화 자리의 분위기를 깨지 않는다는 점에서 어쩌면 좋을 수도 있을 것이다. 누군가에게는 분명히 멋있어 보일 것이다. 하지만, 나는 이러한 "쿨 함"이 싫다. 소수자들이 자신에게 위협이 되는 발언을 들었을 때, 혹은 자신의 정체성을 부정하는 발언을 들었을 때, 그에 대한 "시정"을 요구하면, 이는 쿨하지 않은 행동이 되고, 쿨하지 못하다는 평가를 받는다. 때로는 분위기를 해치는 사람과 같은 취급을 받기도 한다. 사회는 이런 쿨 함을 하나의 덕목 정도로 여기며 소수자들에게 너무나도 자연스럽게 쿨해질 것을 요구하고 있다. 나는 이런 "쿨 함"을 요구..
2021-08-27 Problem Solving 요즘도 꾸준히 1일 1문제는 해결하려고 노력 중이다. 지난 번에 글 쓰고 나서 풀었던 문제들 중 일부를 뽑아서 풀이를 올려본다. 17114. 하이퍼 토마토 간단한 BFS를 통해 문제를 해결할 수 있다...만, 11차원 입력을 효율적으로 처리하는 것이 중요한 문제다. 나는 11차원 배열을 선형으로 펴고, 적절한 사칙연산을 통해 11차원 벡터와 선형 배열 인덱스 사이의 변환을 해주는 방식으로 구현했다. 나의 구현 방식으로 문제를 해결하기에는 다소 빠듯한 면이 있어서, 빠른 입출력 등의 여러 최적화를 함께 사용하여 문제를 해결했다. 22967. 구름다리 성게 그래프를 출력하면, 답이 2 이하임이 보장된다. 이제, 답을 1로 만들 수 있는지를 확인해줘야 하는데, 이는 완전 그래프인 경우에만 가능하다. 따라서, ..