4. 19-21

• 긴잠을 자면서 기분나쁜 꿈을 꿨다. 학기중으로 돌아간 나는 계속해서 열심히 뛰어다녔는데, 모든 일이 잘 풀리지 않았다. 꿈에서는 상황이 제대로 나오지 않지만, 느낌만큼은 생생하게 남는다. 정말로 불쾌한 늪에 한없이 빠져들어가고 있는 느낌? 그 느낌에 몸서리쳐지면서 다시는 분에 넘치는 것들을 떠맡지 않아야 겠다고 다짐한다. 여유롭게, 꾸준히, 하지만 깊이.
• Solve a lot of easy problems.라는 금언을 듣고 Codechef Easy를 풀기 시작했다. 이상하게 Codechef는 submisson이 적은 것부터 리스트가 출력되는데-_-; 그래서 풀게된 <Matrix>는 Easy답지 않은 trick이 있었다. 벽이 생성되기만 하고 없어지는 것은 없다. 그런데 union-find를 사용하면 결합은 쉬운데 분리는 어렵다. 그러면 offline algorithm으로 모든 query를 불러온 다음 거꾸로 처리하면 된다!는 게 풀이.. 
• <Count Substrings>는 Inchworm algorithm과 binary search의 결합으로 해결 가능한 재밌는 문제다. [L, R)이 조건을 만족한다면, 그것의 모든 substring도 조건을 만족한다. 즉 L부터 시작하는 경우를 셀 때, R을 처음 조건이 깨지는 순간까지 밀어놓으면, [L, L+1)부터 [L, R)까지 총 R-L개의 답을 카운트 할 수 있다. 이제 L+1부터 시작하는 경우를 센다면, [L, R)이 가능하므로 [L+1, R)도 가능하다는 걸 알 수 있다. 결국 R을 그대로 가져가고 L위치의 카운트를 뺀 상태에서 또 조건이 깨질때까지 밀어놓으면 된다. 전형적인 자벌레 알고리즘(inchworm algorithm)으로 O(N)에 모든 시작점의 한계점을 구할 수 있다.
• 이제 주어진 범위의 답안을 구할 차례다. 답안은 다음 식으로 나타낼 수 있다.
• 
• 앞에서 구한 한계점 배열을 limit이라 하면, 이 배열은 단조증가한다. 결국 이분검색으로 R+1을 찾으면, 거기서부터는 모두 R+1로 채워넣어 계산하면 된다는 것!! 나머지는 식만 제대로 써주면 된다. #
• <Count Sequences>는 내가 미처 모르고 있었던 사실을 알려준 문제! 중복조합으로 풀면 된다는 것은 도출해냈지만, 이 식을 위키피디아에서 얻어냈다.
• 
• 파스칼의 삼각형상에서 생각해보면 쉽다. 우하향 대각선으로 선을 그으면, 그 선에 해당하는 수열은 그 아랫 대각선의 차수가 된다. 알면 쉬운데 떠올리기가 쉽지 않았다-,- #
  
• <Bytelandian gold coins>은 관계식이 N/2, N/3, N/4꼴로 연결되어 그냥 단순 dp로 해결해도 될성 싶어 짰더니 충분히 빨랐다. 10^9까지 커버해야되니까 그냥 map<int,long long>으로 잡았는데, 다른 답안을 보면 좀더 효율적인 저장법이 있더라. 2,3,4니까 cache[i][j]를 2로 i번 나누고, 3으로 j번 나눈 결과를 저장해두는 것. #