이번엔 전반적으로 난이도 있는 셋이었습니다 (도대체 출제자가 누구인건지 ㅠ_ㅠ)

• 코딩 div2 같은 경우는 easy, mid 적절한 난이도(너무 쉽지 않게)...라고 생각했으나 hard 문제는 이해할수록 심히 두려워져버렸습니다. 쉽게 생각하고 시작했으나 예외가 많이 나와서 예외를 고려한 코딩은 지저분 했던 데다가 테스트셋으로 검증되지 않는 예외가 존재해서 마지막까지 수정하다가 결국 뒤죽박죽이 되어버렸죠. 테스트 케이스 통과하고 서밋 눌렀으나 시간 초과로 서밋도 실패... 망연자실한 쉬는 시간에 슬쩍 랭킹을 보니 120위권...
• 챌 간단한 하드용 테스트 셋({'b??', 'b?b', 'bc?'}, 2)을 만들고 나니 시작하는 챌타임 원래 챌 시간에는 잡담이나 컴터 끄고 자는데, 1000을 못 푼게 너무 억울해서 분노의 챌(?)이 시작되었습니다. 속으로 계속 '이런 문제를 푸는 놈들이 있다니 ㅠ_ㅠ 여긴 2부리그야'라고 외치며 1000을 푼 2명에게 챌... 모두 성공했습니다. 좀 황당하더군요 방에 더 이상 챌 할 사람이 없음에 아쉬움을 느끼면서 500 문제를 챌해서 3번 성공하고 3번 실패했습니다. 250은 펴보기도 싫어서 그냥 가만히 랭킹을 보니 30위권에서 떠돌고 있더군요!! 많이 올랐습니다. 기분이 좀 풀리더군요. 여전히 건재한 1000점들이 30명은 있었습니다. 저 중에 한 반정도만 시스템 테스트에서 통과 못하기를 바랬습니다 ㅜ.ㅜ
• 시스템 테스트 이후 시스템 테스트가 시작되고 갱신되면서 랭킹이 하나씩 오르기 시작했습니다. ㅎㅎㅎ 좀 이상한 게 좀 시간이 지나면서도 1000 pass는 안 나오고 랭킹은 계속 올랐습니다. 제현님하고 메신저로 농담으로 이러다 top 5 되는 거 아냐? 라고 했는데 정말 되더군요 -_-;; 결국 hard를 pass한 사람은 1명, 이고 변태1등은 챌 점수가 325점 이더군요 전 난데없이 3등이 됐습니다. [-- ][ --] 으응? 간만에 보는 챌과 시스템테스트 실패가 난무하는 SRM이었습니다. 개인적으로는 120위권에서 3위까지 오르니까 짜릿하더군요 ㅋ <이지 문제> 손가락으로 숫자 세는 문제입니다. 저는 약간 다르게 패턴을 이용해서 풀었습니다. [code c++] int maxNumber(int weakFinger, int maxCount) { int rr(0); vector fcount(6,0); int finger(0); int ff[8] = {1,2,3,4,5,4,3,2}; while(true) { finger = ff[rr%8]; ++fcount[finger]; if(fcount[weakFinger] > maxCount) break; ++rr; } return rr; } [/code] <미디엄 문제> 큰 숫자를 나눌 수 있을 때까지 키우는 문제였습니다. d1-easy랑 같은 문젠데, 나머지를 이용해서 계속 숫자를 줄여가면서 계산하면 됩니다. <하드 문제> 소문자와 ?로 이루어진 문자열이 있습니다. a?b 는 26가지 문자열을 표현할 수 있고, ??는 26^2의 문자열을 표현가능하죠. {'b??', 'b?b', 'bc?'}, 2 라면 앞의 집합에서 2개의 조건을 만족하기만 하면 됩니다. 조건에 맞는 문자열의 갯수는? 척보면 간단하고, 그냥 문자열 생성해서 풀어도 될 꺼 같습니다. 그래서 전 '문자'와 '?'로 나눠서 집합으로 풀었더니 교집합을 빼주는 부분이 죽도록 어렵더군요 ㅠ_ㅠ (각각의 조합은 and 조건이니까 쉬웠는데 전체로 구할 때는 겹치는 부분은 빼줘야 하니까요;;;) 아무튼 기본적으로는 26^50(문자갯수^문자열길이)의 문자열을 만들어서 각 patterns에 매칭해서 매칭되는 횟수를 세서 k개만큼 매칭되면 더해주면 됩니다. 문제는 26^50 이란 숫자가 너무 크죠. 10^50만 해도 0이 50개니까...ㄷㄷㄷ;;; 그럼 이제 어떻게 저 26^50을 줄일 수 있느냐 하는 문제에 도달합니다. 여기서 힌트는
• 최후에 물어보는 건 "갯수"만 맞추면 된다(쉽게 말해서 최종 결과값만 숫자로 구성)
• 문자열 길이가 한개씩 더 늘어난다고 해도 다시 앞에서부터 계산하지 않아도 됩니다(F(i)->F(i+1)이 된다는 소리므로 DP로 품) 하지만, 여전히 구체적으로 어떻게 푸는 지는 감이 안옵니다. 대략 감을 잡아보기 위해서 문제를 변형합니다. k는 항상 1이라고 생각해 봅니다. 즉 1개씩만 만족하도록 하고, DP를 적용해 봅니다. 예를 들어 {"ab", "cd"}라는 문자열이 들어왔을 때 "ab"를 0번, "cd"를 1번으로 놓고, 첫번째 줄부터 시작해보면
• 'a'통과(0번) : 1개
• 'c'통과(1번) : 1개
• 'a','c'동시 통과(0번,1번) : 0개 이고, 두번 째 줄만 계산할 때는
• 'b'통과(0번) : 1개
• 'd'통과(1번) : 1개
• 'b','d'동시 통과(0번,1번) : 0개 그럼 "ab"라는 문자열을 통과한 것의 갯수는 "첫번째와 두번째 줄에서 동시에 0번을 통과한 애들"이 됩니다. 그러면 [동시에 통과한 자리] += 첫번재 줄의 수 이런 공식을 만들어서 풀 수 있을 듯 합니다. 1<<15는 각 조합을 일일히 나눠준다고 생각하셔도 될 거 같습니다. 00001, 00100, 00011 이런 것들을 하나하나씩 구분해 주는 것이죠. 즉 0번과1번 통과한 것, 0번만 통과한 것, 1번만 통과한 것...등을 일일히 분류해주는 겁니다. 사실은 뭔가 참 쉬운 설명을 찾아볼려고 했는데, 아직은 내공이 부족해서 쉽게 설명이 안됩니다. ㅠ_ㅠ 그래서 그냥 GG 치고, 코드나 붙여봅니다 ㅠ_ㅠ 그냥 제 조합한 코드를 보시면 이해가 더 빠르실 지도 모르겠습니다. 코드 길이가 길지 않은데, 참 설명하기가 캐어렵군요. 아마 다음에 비슷한 문제가 나오면 전 틀릴 듯 -_-;; [code c++] template inline int countbit(T n){return (n==0)?0:(1+countbit(n&(n-1)));} class SetOfPatterns { public: int howMany(vector patterns, int k) { int N = patterns.size(), M = patterns[0].size(); int maxbin = (1< result1(maxbin, 0), result2(maxbin, 0); int rr(0); result1[maxbin-1] = 1; // 제일 처음에는 모든 문자열이 통과된 상태임 // 제일 앞의 문자열부터 for(int m=0; m0) { result2[(bin&filter)] += result1[bin]; result2[(bin&filter)] %= 1000003; } } } result1 = result2; } for(int bin=0; bin[이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]