Eau de Cologne
흔히 등장하는 동적계획법 아이디어들을 정리하기 위해서 만들었습니다. 다뤄볼 주제는 다음과 같습니다. 아마 난이도 순으로 정리할 것 같습니다. 일단 생각나는것 부터 쓰겠습니다: 동적계획법이란 무엇인가 냅색 Floyd-Warshall 게임 이론과 동적계획법 자릿수 동적계획법 Deque 트릭과 동적계획법 서로 다른 부분수열의 개수 CYK 알고리즘 비트DP 트리DP 끼워넣는 DP 원형 구간 DP DP와 행렬 제곱 Bostan Mori / Kitamasa Connection Profile SoS DP (Zeta Transform) 동적계획법 최적화 아이디어들 CHT Monotone Queue Divide and Conquer Lagrange Method 쓸거 너무 많네...
https://atcoder.jp/contests/abc341/tasks/abc341_g G - Highest Ratio AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 풀이: 문제를 결국 어떤식으로 바꿀 수 있냐면 누적합을 $S$라고 하면, $\frac{S_j - S_i}{j-i}$가 최대가 되는 $j$를 모든 $i = 0, \cdots, N-1$에 대해서 구해야 한다. 생각하기 편하게 수열을 뒤집어서 생각하면, $i$번째 단계에서는 $(0, S_0); \cdots; (i-1, S_{i-1})$에 대해 선을 그었을 때 ..
취미용으로 블로그 글을 써보려고 합니다. 이 블로그는 좀 더 프로그래밍과 관련이 되어 있는거로 쓰지 않을까 싶습니다. 최근에 대회 준비 때문에 많이 바빠서 여기서 글을 못 썼는데, 여유가 생기면 많이 많이 써보도록 하겠습니다. https://maxflow.tistory.com/
https://www.acmicpc.net/contest/view/912 간략하게 씁니다. 디테일을 안 쓰는 이유는 기억이 안나서... A $7.5N-len$ 이 0 이상인지 이하인지를 가지고 판단했습니다. 더 짧게 짜라면 짤 수 있을듯 B 그냥 하면 됨 C O(N) 풀이가 있다고 합니다. https://www.acmicpc.net/problem/4354 랑 비슷하게 풀면 됨 D 현재 위치와 현재 시간의 차이가 같은 금고를 모두 털 수 있습니다 E 현재 위치와 현재 시간의 차이가 증가하도록 금고를 털 수 있습니다. 이후는 LIS 알고리즘 F 앞쪽 절반만 보면 수가 증가해야해서 중복순열을 쓰면 됩니다 G 이분탐색 + 슬라이딩 윈도우쓰는 재미있는 문제라고 생각함 H (수열의 길이, 수열에 올 수 있는 다음 ..
"마법소녀 마도카☆마기카"는 우로부치 겐이 각본을 쓰고 샤프트가 제작해 2011년에 방영된 애니메이션이다. 하교길에 쇼핑 중이던 주인공 카나메 마도카는 꿈에서 본 수수께끼의 소녀인 아케미 호무라에게 공격받는 생명체 큐베를 발견한다. 큐베를 구하던 중 정체불명의 결계에 휩쓸린 마도카는 마법소녀 토모에 마미의 도움으로 위기를 벗어난다. 큐베와 마미에 따르면, 마법소녀는 큐베가 소원을 이뤄주는 대가로 마녀와 싸우는 존재다. 이 애니메이션 이전에는 마법소녀가 비인간적인 적과 전투를 벌이는 일본 애니메이션들이 일반적인 패턴을 따랐다. 마법소녀 장르의 매력은 주로 화려한 연출과 캐릭터의 개성 정도에 의존했다. 처음에는 이 작품도 그저 캐릭터의 매력과 몽환적인 분위기, 그리고 독특한 포토데칼코마니 스타일의 마녀 연출..