3584. 가장 가까운 공통 조상 문제 : http://icpc.me/3584 옛날 ICPC문제여서 그런지 진짜 LCA를 대놓고 묻는 문제. 이 때는 아직 LCA가 고ㅡ급 알고리즘이었나보다. 테스트 케이스마다 배열 초기화에 주의하도록 하자. LCA에 대해서는 더 잘 설명해놓은 글들이 천지빽가리.http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220820773477 Time Complexity : O(Tn)O(Tn)O(Tn) 8984. 막대기 (KOI '13)문제 : http://icpc.me/8984http://oj.uz/problem/view/KOI13_game BOJ AC 기준으로 게시.문제 조건을 잘못 이해해서 이거 완전 NP 아니냐? 하고 풀이를 깠다. 이해..

2969. 메뚜기 (COCI 08/09 Contest #1 5번) 문제 : http://icpc.me/2969 오래전에 친구가 교내 대회에 냈던 문제인데, 그때 아무생각없이 O(n4)O(n^4)O(n4)이랑 O(n3)O(n^3)O(n3) 생각하고 끝냈던 문제. 일단 dp[i][j]dp[i][j]dp[i][j]를 (i,j)(i,j)(i,j)에서의 최장 경로라고 하자. 이제 각각 nnn개씩의 행/열에 대해서 dpdpdp값과 좌표를 저장해두는 자료구조를 만든다. 높이가 낮아지는 순서대로 탐색하면서, i+1열, i-1열, j-1열, j+1열에 저장된 dp값들 중 조건을 만족하면서 가장 큰 dp값을 DDD라고 하면, dp[i][j]=D+1dp[i][j]=D+1dp[i][j]=D+1이 된다. 자료구조를 맨 처음에는 set으로 했는데, set을 허투루 썼더니 메모리 초과가 났다(...) 여윽시 s..

어제 올리려고 하다가 9시에 자버렸다 ㅁㄴㅇㄹ... 이번에는 MWT 특집.2011. 암호코드문제 : icpc.me/2011 간단한 dp인데, 0인 경우를 생각해주지 않으면 가버릴 수 있다. 입력 문자열을 SSS라고 하고, D[i]D[i]D[i]를 S1⋯Si−1S_1 \cdots S_{i-1} S1​⋯Si−1​를 해석할 수 있는 경우의 수라고 두자. 입력이 0으로 시작하지 않는다는 것이 보장되어 있으므로 D[2]=1D[2]=1D[2]=1이다. 이제 dp를 앞에서 뒤로 뿌려주자.Si≠0S_i \neq 0Si​=0인 경우, SiS_iSi​를 하나의 암호문으로 해석할 수 있으므로 D[i+1]+=D[i]D[i+1]+=D[i]D[i+1]+=D[i].Si≠0∧10Si+Si+1<27S_i \neq 0 \wedge 10S_i + S_{i+1} < 27Si​=0∧10Si​+Si+1​<27인 경우, SiSi+1S_iS_{i+1}Si​Si+1​를 하나의 암호문으로 해석할 수 있으므로 ..

#1. 중량제한 문제 : icpc.me/1939 굉장히 다양한 풀이가 가능한 문제인데, description을 잘못 이해해서 ㅂㄷㅂㄷ하다가 결국 풀이를 까봤다. 1. BFS 물건을 보내는 공장을 sss, 받는 공장을 ttt라고 하자.또 각각의 정점까지 수송할 수 있는 최대의 비용을 F[v]F[v]F[v]라고 하자.(정점 vvv, c=sss에서 vvv까지 옮길 수 있는 최대 비용)의 순서쌍을 저장할 수 있는 큐 QQQ를 잡고, QQQ에 (s,F[s]←∞)(s,F[s]\leftarrow \infty)(s,F[s]←∞)를 넣으면서 BFS 개시. QQQ가 빌 때까지, QQQ의 front kkk에 대해서 k.vk.vk.v에 연결되어 있는 점 uuu들을 보는데, \(min(k.c,bridge\_capacity[v\..

1. 이상한 수열 (OJUZ #10) http://icpc.me/11917 http://oj.uz/problem/view/OJUZ10_bizarre 풀이 : oj.uz에서 처음 봤을 때 아무 생각 없이 62점을 받고 넘겼던 문제다. 100점 풀이 생각 못한 뚝배기를 매우 쳐라 MMM이 비상식적으로 크므로, BiB_iBi​의 값을 거의 닫힌 꼴로 구할 수 있을 것이라는 생각을 해야 한다. SSS를 오름차순으로 정렬한 뒤, Bn+1B_{n+1}Bn+1​의 값 (S1,S2,⋯SnS_1, S_2, \cdots S_nS1​,S2​,⋯Sn​ 중 서로 다른 수의 개수)이 어떤 (Si,Si+1](S_i,S_{i+1}](Si​,Si+1​]에 있게 되면 이 값은 Si+1S_{i+1}Si+1​로 수렴하고(편의상 Sn+1=∞S_{n+1} = \inftySn+1​=∞라 두자), 그 전까지는 값이 1씩 증가하게 됨..

*이 문제 set은 백준 온라인 저지에서 랜덤을 돌려서 푼 문제들입니다. 풀이를 좀 포멀하게 적고 싶어서 쉬운 문제라도 모두 풀이를 상세하게 기록할 예정이니, 그게 마음에 들지 않으신 갓갓분들은 살포시 뒤로가기를 눌러 주세요. 1. 수열 축소 문제 : http://icpc.me/2237 풀이 : 얘는 고1때 정올을 딱 시작할 때쯤 풀지 못하고 넘겨버린 문제. 사실 CON이란 연산이 전혀 대단하지 않다는 것만 알면 된다. CON연산을 수행한 결과는 수열의 인접한 원소 사이에 + 또는 -의 부호를 적절히 삽입하여 계산한 식이다. (단, a2a_2a2​앞에는 반드시 -가 붙는다) 그래서 n×(2∑ai+1)n \times (2\sum{a_{i}}+1)n×(2∑ai​+1) dp table을 잡고,dp(i,j):a1 aidp(i,j) : a_{1}~a_{i}dp(i,j):a1​ ai​까지..