전체 글
[ARC 149] 3솔
퍼포 1585(민트) '이게 왜 됨?'의 연속인 대회였지만 어째저째 잘 풀어서 3솔을 해냈다. 오늘 div2 #824도 있는데... 연달아는 못 치겠다 쉬어야지
[미분방정식] Wronskian
미분방정식및연습 시간에 2계동차선형미방의 해와 관련해서 어떤 해 여럿이 있으면 그 둘의 선형결합도 해가 된다는 것을 배웠다. 이걸 중첩 원리(Superposition Principle)랜다. 대충 $y$와 방정식 $y'' + p(t)y' + q(t)y = 0, t \in I$의 $y$랑 그 미분 항들을 매칭시키는 선형 연산자 $L$을 갖고 방정식의 두 해 $y_1, y_2$로 $L[c_1y_1+c_2y_2] = c_1L[y_1] + c_2L[y_2] = 0 + 0 = 0$해서 증명했다. 근데 심지어는 저 둘의 선형결합이 방정식의 모든 해를 표현할 수도 있댄다. 어떤 때에? Wronskian $W[y_1, y_2](t_0)$이 어떤 $t_0 \in I$에서 0이 아닐 때에! 론스키안은 $\displayst..
[Div2 EDU 136] 3솔
내 50분이 어디로 갔지? 내 50분이 어디로 갔지? 내 50분이 어디로 갔지? 내 50분이 어디로 갔지? 내 50분이 어디로 갔지? 내 50분이 어디로 갔지? 내 50분이 어디로 갔지? 내 50분이 어디로 갔지? 그래도 4솔이 눈앞에 보이긴 한다. 아이디어만 잘 잡으면 괜찮을듯. 4솔 퍼포가 1800대였으니까 나는 아마 1600~1700 어딘가에 있지 않을까 +[22/09/30 03:22] B 엄청 터진다! 데이터가 엄청 부실했던 모양이다.
[ABC 270] 4솔
퍼포 1316(민트) 아... 화난다 DP에서 거하게 말아먹고 G번 이산로그 bsgs 짜다가 시간 다 날림. 거의 다 짰는데... 구현 속도 느린 건 CP를 오랜만에 하니 그렇다 쳐도 DP 못 잡은 건 참 그렇다. 귀찮다고 다른거만 풀어댔더니 이 꼴이다. 솔직히 DP 재미없긴 한데, 기초를 단단하게 다져놔야 위에서 뭘 하든 말든 하지. 반성하는 시간을 갖게 된다. DP / 그리디 / 그래프 탐색 같은 기초 알고리즘 문제들 많이 풀고 그러면서 구현 속도도 늘리고 하자. 수학은 뭐 필수고...
[18806] 와일드 카드
부제: Wildcard string matching with Fast Fourier Transform 문제 분석 우선 지문을 읽어봅시다. 길이 25만의 알파벳 소문자 + '$?$' + '$*$'로 구성된 문자열이 두 개 들어옵니다. 문제에서 제시한 조작으로 두 문자열이 '같도록' 하면 됩니다. 문제에서 제시한 조작(연산)은 세 가지로, 문자 삽입, 문자 삭제, 문자 치환입니다. 그런데 사실 연산이 셋이나 있을 필요가 없습니다. 그 이유는 문자 '$*$'의 성질 때문인데, 이 녀석은 모든 문자이면서 모든 문자열로 취급될 수 있기 때문에 '치환'과 '삽입'의 역할을 대체할 수 있고, 길이가 0인 문자열로 취급될 수도 있기 때문에 '삭제'의 역할을 대체할 수 있습니다. 따라서 가용 연산을 다음과 같이 간단하게..