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

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

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