16661번 문제를 풀던 11달 전부터 풀이는 대강 알고 있었는데, 구현을 할 자신이 없어서 묵혀 두고 있었다. 하지만 이제는 더 미루기 싫어서 이 문제를 잡아야겠다고 마음을 먹었다. 구현에 필요한 알고리즘을 공부하고, 알고 있는 풀이를 집어넣었더니 다행히 금방 풀렸다. 구현미스가 전부 예제나 손으로 생성한 테스트케이스에서 걸린 게 참 다행이 아닐 수 없다.그러면 본격적으로 풀이에 돌입해 보자.문제당신은 \(n\times m\) 크기의 직사각형 격자판을 가지고 있다. 모든 단위격자는 '*', '+', '.' 셋 중 하나는 포함하고 있다. 트로미노는 중심을 이루는 단위격자의 네 변 중 두 변에 각각 하나의 단위격자가 붙은 것을 일컫는다. 중심이 아닌 두 단위격자가 꼭지점을 공유하고 있을 때 이를 L 모양이..

어려운 난이도로 올라갈수록 PS 범위라고 생각하지도 않았던 발상을 사용해야 한다. 대표적인 예시로 현대대수를 쓰는 3904번 문제가 있고, 그리고 이 문제가 있다. 정말 상상도 못 하는 발상으로 문제가 풀리는데, 그 발상 난이도가 문제 난이도의 9할 정도를 차지하고 있다.더 놀라운 점은 이 문제가 셋에서 중간 정도의 난이도를 가지고 있다는 것이다. Petrozavodsk Programming Camp의 문제들 난이도가 높은 것은 알고 있었지만, 플래티넘조차 없는 셋은 정말 처음 본다. 그럼 본격적으로 풀이에 돌입해 보자. 문제의 본문은 내가 임의로 번역을 좀 했다.문제위키피디아를 검색해서 무작위 참고 문헌을 읽는 것은 문제를 만드는 가장 좋은 방법이다.\(N\)이 주어지면, 다음 조건을 만족하는 \(S\..

상위 100문제에서 Platinum II를 없애려고 오늘 티어작을 좀 했다. 완전히 새로운 개념인 일반 그래프 매칭(의 매우 한정적인 사용법인 최대 매칭의 수)을 배운 다음에 매우 기초적인 응용 문제인, 그래도 Diamond II 정도 되는 문제를 두 개 풀고 나서 그 다음으로 많이 풀린 이 문제를 살펴보았다. 중간에 포기할까 하고 다른 거 잡아먹으러 갔다 돌아오는 시간까지 합치면 총 두 시간 정도 쓴 것 같다.Ruby IV나 되는 문제다. ICPC의 2차 예선 격인 Northern Eurasia Finals에 출제된 문제인데, 보스격 문제... 같다. 왜 자신이 없냐면, 저 셋의 13문제 중 이 문제가 난이도가 가장 높지만 Ruby V가 세 문제나 있기 때문이다. 이 정도면 도대체 누구를 통과시키려고 ..

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

인생 두 번째 루비 문제다. 제2회 초콜릿컵 🍫번 문제인데, 대회 중에는 이게 내가 아는 그 개념을 쓰는 건 맞지만 어떻게 해야 할지 감을 못 잡아서 내버려 뒀었다. 에디토리얼을 보니 난이도가 Impossible이라고 매겨져 있더라. 그런데 148분만에 문제를 푼 사람이 나왔고. 어떻게 풀었는지 그 분의 코드를 까 봤지만 힌트를 얻을 수 있는 게 없었다. 에디토리얼에는 논문 하나가 나와 있었고, 그것대로 대충 구성했더니 답을 루비 치고는 간단하게 얻을 수 있었다. 다만 이 풀이가 시간 단위가 아닌, 1초 안에 답을 뱉는 풀이는 아니었다. 그렇게 되도록 최적화하는 것은 분명히 루비 난이도가 맞았다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 초콜릿과 숫자놀이를 좋아하는 코코는 "초콜릿 수"를 다음과 같이 ..

내가 이 블로그를 개설할 때만 해도, Ruby 카테고리는 구색맞추기용이었다. 내가 내 실력으로 Ruby 난이도의 문제를 하나라도 풀 수 있을 것이라는 생각을 한 적은 없었다.작년 말에 상황이 달라졌다. 적당한 알고리즘을 검색했고, 이렇게 하면 풀 수 있을지도 모르겠다는 생각이 들었다. 길이 희미하게 보이기 시작했다.1월에 제대로 코드를 짜고 도전해 보기 시작했다. 계속되는 시간초과에 발이 묶여 여기저기 도움을 요청해 봤지만, 이렇다 할 답은 나오지 않았다. 현 시점에서 푼 사람이 69명뿐인 문제이니 그럴 만도 하지.그리고 오늘. 6월 6일 새벽 1시쯤에 번쩍 하고 스쳐지나가는 아이디어가 있었고, 그걸 구현하려다가 빼먹은 게 좀 있어서 몇 번 틀려 준 다음 올라가는 퍼센테이지를 보고 정말 울 뻔 했다. 이..