굉장히 오랜만에 블로그에 글을 쓰는 느낌이다. 대학원생이 된 이후로 바빠서 문제를 풀더라도 블로그에 글을 쓸 시간이 안 났다. 짬이 생긴 터라 오늘 푼 문제의 풀이를 작성한다.이 문제를 품으로서 수학 태그레이팅이 2600에 도달했다. 2700까지 올리고는 싶으나 아직 내가 그럴 만한 체급이 안 되는 것 같기도 하다. 천천히 올리자. 급하게 하지 말고.문제두 음이 아닌 정수 \(a,b\)에 대하여 \(a\wedge b, a\vee b\)는 각각 이들의 bitwise AND, bitwise OR를 나타낸다.음이 아닌 정수로 구성된 길이 \(2^N\)의 정수열 \(A_0,A_1,\cdots,A_{2^N-1}\)에 대해 \(A_i+A_j 입력첫째 줄에 음이 아닌 정수 \(N\)이 주어진다. \((0\le N\l..

요즘 수학에 관심이 있고 잘 하는 사람 몇 명이 solved.ac 디스코드에 모여서 같이 어려운 수학 문제를 썰고 있다. 나도 나름 수학을 잘 한다고 생각하지만, 당연히 세상은 넓다. 이제 자부심은 떼야 할 것 같다.그 디스코드 채널에서 나온 이야기다. 언제나처럼 두 명이서 수학 문제 관련된 이야기를 하고 있었는데, 조금 끔찍한 생각이 떠올라서 말을 꺼냈다. 그러고 나서 구현할 시간과 자신이 없어서 잠시 접어 뒀다가, 한 번 더 이야기를 꺼내고 구현을 시작했다. 아무리 봐도 답이 안 나와서 내가 망하고 있을 때 다른 분이 구현 된다고 검증하고 나서 디스코드에서 핑을 찍었다. 정작 나는 오타나 구현 오류 잡는다고 그 핑을 못 봤다. 1시간 정도 지나서 결정적인 오타 하나를 잡아낸 것 같다.누구에게서 문제 ..

2월 12일에 SUAPC 대비를 위한 팀연습을 치뤘다. 우리 팀 중 한 명은 갑작스럽게 잡힌 일정에 대비하지 못해서 대타 버스기사 kiwiyou를 데리고 팀연습을 치루었다. 상대 팀은 전 ICPC 팀메이트였던 changhw의 팀. 진짜 강적이었다... kiwiyou가 빡구현 문제, blackstar0223이 아이디어성이 높은 그리디 문제에서 승리하지 못했으면 내가 구멍이 되었을 것이다. 난... 3문제를 풀기는 했는데 발목에 추만 달아 준 느낌이라... 셋은 UCPC 2021 예선. 내가 B, F, G를, blackstar0223이 C, D를, 그리고 kiwiyou가 A, I를 잡아내서 7문제를 풀 수 있었다. 그런데 이거 3시간 셋을 억지로 5시간으로 늘린 거라 이 멤버로 했어도 본선은 못 갔을 것 같..

백준에는 가끔씩 농도가 너무 높은 수학 문제들이 올라온다. 구현보다는 수학에 강점이 있는 나에게는 그런 문제들이 아주 맛 좋은 먹잇감이다. 오늘의 문제인 쉬운 문제도 그러하다. 글을 쓰는 지금 기준 Diamond III이라는 정말 높은 난이도를 자랑하지만 내가 이 문제를 보고 구현을 마치기까지 걸린 시간은 1시간도 안 걸렸다. 그렇다고 단체로 착각해서 이 문제를 어렵게 봤다는 말은 아니다. 제목 값을 전혀 하지 못하는 문제 중 하나라고 감히 자부까지 할 수 있다. 다만 이 문제의 풀이법이 KMO에서는 너무나도 웰노운이었을 뿐... 그럼 본격적으로 풀이에 돌입해 보자. 문제 1보다 큰 정수 \(k\)가 주어졌을 때, 다음 식을 만족하는 양의 정수 \((a, b, c)\)는 무수히 많다는 것을 증명할 수 있..

SUAPC 2023 Summer B번 문제이며, 내가 출제한 세 번째 문제이다. 출제 여담은 SUAPC 2023 Summer 출제 후기에 충분히 썼으니 이번에는 이 문제의 수학적인 해결법에 대해 논하고자 한다. 에디토리얼에 있는 풀이 두 가지 대신 출제 때부터 마음 속에 품고 있었던 야매 풀이 하나와 어제 생각해 낸 제4의 풀이 이렇게 두 가지로. 그럼 본격적으로 풀이에 돌입해 보자. 문제 행렬식은 선형대수학에서 다루는 기초적인 대상 중 하나이다. 이항계수는 조합론에서 다루는 기초적인 대상 중 하나이다. 두 기초적인 대상을 섞은 문제는 기초적이므로, 다음 행렬의 행렬식을 구하는 문제는 기초적인 문제이다. $$A(a_1,a_2,\cdots,a_N)=\left({a_i\choose {j-1}}\right)_..

모든 시험이 오늘부로 종료되었다. 성적이 나온 과목은 몇 개 있는데 하나는 생각보다 덜 만족스러웠다. 어쩌겠는가, 이미 안다고 자만하며 공부를 조금 소홀히 한 내 잘못이지. 이번 문제는 정수론적 지식이 매우 강력하게 필요한, 무려 다이아몬드 IV 문제이다. 소인수분해 과정에서 밀러-라빈과 폴라드-로까지 사용해야 하는 매우 복잡한 문제. 혹시 그 쪽에 대한 지식이 필요하다면, 이 포스트를 참조하라. 심지어 이 문제를 약간 발전시킨 문제는 루비 IV에 랭크되어 있다! 그 코드도 거의 다 만들었으나, 의문의 시간초과로 인해 난항이다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 ..