Problem Solving/Topcoder11 TopCoder Marathon Match 100 후기 이번 마라톤 매치에는 50등 이내의 참가자들에게 티셔츠를 주는 이벤트가 있었습니다.문제는 상당히 단순합니다. H*W 크기의 격자 판이 있습니다. 각 격자 칸에는 0 ~ C-1의 숫자가 있습니다. 여러분은 숫자가 같은 두 격자 칸을 선택해서 없앨 수 있는데, 추가적인 조건으로 두 격자 칸을 대각 꼭짓점으로 하는 직사각형 내에 다른 숫자의 격자칸이 있으면 안됩니다. 삭제된 칸은 숫자가 쓰여 있지 않다고 가정합니다. 가능하면 많은 수의 격자 칸을 없애야하는 것이 본 문제의 목표입니다.문제 본문은 다음 링크( MM 100 Problem Statement )에서 보실 수 있습니다. 대회 결과는 다음 링크( MM 100 Standings )에서 보실 수 있습니다. 아래 영상은 제가 작성한 코드가 격자 칸을 없애는 .. 2018. 4. 26. TopCoder Marathon Match 99 후기 거의 7년 만에 탑코더 마라톤 매치(Marathon Match, MM)를 해 보았습니다. MM은 Single Round Match(SRM)와 달리 정해진 정답을 빠르고 정확하게 계산하는 대회가 아니라, 문제에서 요구하는 최적해를 30초 ~ 1분 정도의 다소 넉넉한 수행시간을 가지고 계산할 수 있는 알고리즘을 고안하는 대회입니다. 대회를 치르는 시간도 SRM은 1시간 15분인 것에 비해 MM은 최소 1주 ~ 2주의 긴 시간 동안 이루어집니다.이번 MM 문제 내용을 한 문구로 요약하면 '슬롯 머신을 이용한 도박'이라고 할 수 있습니다. 문제 본문은 다음 링크( MM 99 Problem Statement )에서 보실 수 있습니다. 대회 결과는 다음 링크 ( MM 99 Standings )에서 보실 수 있습니다.. 2018. 3. 25. SRM 707 Div.1 Kriii형이 또 다시 스름 윈을 했다ㅋㅋ 나는 오랜만에 해보았는데 0점 받지 않아서 다행이라 생각한다. 몇 가지 고려 안해서 미디움을 놓친 건 정말 아쉽다.250pts(Passed System Test) ㄹ자로 만드는 전략을 통해 맵을 만들어나가면 된다. 단, ㄹ자로 만드는 과정에서 경로가 2씩 증가됨에 주의한다.class MazeConstruct { public: vector solve(vector ans, int k) { int s = ans.size(); for (int i = 1; i 2017. 1. 31. SRM 675 Div.1 LimitedMemorySeries1 문제 링크 : http://community.topcoder.com/stat?c=problem_statement&pm=14088 문제 내용 : 5,000,000만 개의 수 X(i)가 있을 때에, Q 개의 쿼리 query(i)에 대해서 전체 X를 오름차순 정렬하였을 때에 query(i)번째 원소를 출력하는 문제이다. 하지만 메모리 제한이 2MB라서 X를 전부 저장해 둘 수 없다. X에 대한 일차 함수식은 (X(i-1)*A + B) % 10억7 이다. 쿼리 개수는 100개 이하이다. 풀이 1 : 버킷, 평방분할 수의 범위가 0~10억6인데, 이 범위를 크기가 D인 루트개의 구간으로 평방분할한다. X(i) / D의 구간에 X가 몇 개인지 누적해둔다. 그럼 각 쿼리에 대해서 O(D)에 query(i)번째 원소가.. 2016. 6. 21. SRM 380 Div.2 250 : 쉬운 구현 문제 class LuckyTicketSubstring { public: int maxLength(string s) { int res = 0; int n = s.size(); for (int i = 0; i < n; i++) { int L = 1; for (int j = i + 1; j < n; j += 2) { int s1 = 0, s2 = 0; int i2 = i + L; for (int k = 0; k < L; k++) { s1 += s[i + k] - '0'; s2 += s[i2 + k] - '0'; } if (s1 == s2) res = max(res, L * 2); L++; } } return res; } }; 500 : 오른쪽으로만 이동할 수 있는 연산의 특성을 고려해 케.. 2016. 4. 22. 이전 1 2 3 다음
