난 세그먼트 트리를 모른다. 그런데 어느 날 balbad.ac solved.ac의 태그를 보다 보니 내가 세그먼트 트리 태그가 달린 문제를 푼 게 아닌가. 그것도 두 문제나. 이것은 기여가 잘못되었거나 아니면 비슷한 난이도의 다른 풀이가 있거나 둘 중 하나. 아니나 다를까 세그먼트 트리를 전혀 쓰지 않는 풀이법이 있었다. 대신 일정 이상의 수학 지식과 직관력이 요구되는 문제였다. 젠장 또 수학 문제야. 나는 수학 문제를 보고 말았어. 이제 나는 수학 문제를 풀어야만 해... 아무튼. 그럼 본격적으로 풀이에 돌입해 보자. 문제 상근이는 빵집에서 일한다. 상근이의 퇴근하기 전에 하는 마지막 업무는 빵을 사장이 원하는 순서대로 정렬하는 것이다. 최근에 상근이는 선영이에게 신기한 기술을 하나 배웠다. 이제 상근..

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

TBU (11월 26일의 나) 라고 놔둔 지 장장 1개월 하고도 몇 일이 지난 뒤에야 후기를 쓴다. 머리가 멍청해질 대로 멍청해진 데다가, 7전공 1청강의 미친 기말고사 스케줄을 완주하느라 ICPC 추억을 버리고 그 공간에 벼락을 넣어버린 터라 잘 기억이 안 나지만... 그럼에도 불구하고 어떻게든 더듬어 쓰려고 한다. 발단은 jhnah917님이 solved.ac 디스코드에 들고 온 raararaara님(서강대의 유명한 월파출신 코치. 올해는 진행요원 역할이셨다.)의 후기였다. 시간이 나면 써야지 하며 벼르고 있었는데, 정말 절대 올 것 같지 않은 종강이 오고 여유 시간이 제법 남은 지금도 조금씩 후기 쓰기를 미루고 있다. 이 게으른 천성은 작정하지 않으면 거스르기 힘든가 보다. 아니면 이번처럼 그럴싸한 ..

사실 이번 게시글은 자기성찰성이 깊은 게시글이다. 수학 원툴에서 쓸 수 있는 도구를 다변화시킬 필요가 있어서 우선 dp를 연습하기로 하고 골드 범위 내에서 랜덤으로 뽑기를 반복했는데, dp 문제임을 알고 있어도 dp로 못 접근한 문제가 있기 때문이다. 이게 그렇고, 다른 것도 하나 있는데... 하여튼 생각해보다가 안 되니 아득하게 높은 레벨의 풀이를 정말 억지로 끌고 와서 겨우겨우 풀어냈다. 닭 잡는 데 핵폭탄을 떨어트린 느낌이라고 해야 하나... 그럼 본격적으로 풀이에 돌입해 보자. 문제 양의 정수 \(N\) \((1\le N\le 2000)\)을 서로 다른 자연수의 합으로 나타내는 방법은 여러 가지가 있다. 예를 들어, \(N=5\)인 경우 \(N=5=2+3=1+4\)로 총 3가지 방법이 있다. \(..

ICPC 온라인 예선이 끝났다. 본선 진출인지 아닌지는 아직 확실하지 않지만, 그래도 프리즈 전 스코어보드만 따지면 나름 합격점을 주고 싶다. 나름 잘 했다. 정말로. 결과만은... 오히려 내가 본선 진출 가능성에 불확정성을 집어넣어 줘서 미안하기 그지없다. 팀원 중 한 명은 내년이 졸업이라 이번이 마지막 ICPC라는데, 이 사람이 하필 나와 엮여서 올라갈 수 있음에도 온라인 예선에서 ICPC를 마무리짓게 된다면 정말 미안해서 고개를 들 수 없을 것 같다. 제발, 본선만 진출할 수 있게 해 주세요. 우리 팀이 푼 문제는 C, D, G, K이다. 프리즈 시점 파란색 배경은 스코어보드 프리즈가 풀리지 않은 pending인데, 다섯 번을 박아넣었음에도 불구하고 정답을 따내지 못했다(:blobsob:). 나중에..

여러모로 의미가 있는 문제이다. 벼르고 있긴 했지만 그래도 루비라서 손 댈 생각이 없었는데, 정확하게 루비 한 문제로 내 solved.ac 티어를 다이아까지 올려 놓을 수 있는 상황이 되어 동기가 생겼다. 저녁부터 씨름하다 딴짓하다 씨름하다 딴짓하다를 반복한 끝에 오늘 새벽 3시 20분이 되어서야 마무리지을 수 있었다. 영 다른 함수를 적분하는 대참사가 벌어져서... 역시 영어로 된 문제다. 이제는 역사의 뒤안길로 사라진 Google Code Jam의 2016년 World Finals 문제란다. 명성에 걸맞게 끔찍하게 어려운 난이도를 자랑한다. 나는 PS하면서 변분법을 쓰게 될 줄은 몰랐다... 원문 뒤에 번역을 붙이는 방식으로 문제 소개를 하려고 했는데 풀이과정도 상당히 길어질 것 같고 그냥 100% ..