분류 전체보기 (7) 썸네일형 리스트형 중앙대 합격했습니다 [12937] 좋아하는 배열 2 개인적으로는 자력으로 푼 dp 문제중에서는 가장 어려웠지 않나... 싶습니다.태그에는 berlekamp-massey 알고리즘이 있지만 여기서는 이걸 사용하지 않고 해설하겠습니다. 풀이 전반적으로 선형대수학이 많이 사용됩니다. 기본적인 행렬연산 정도를 사전지식으로 요구합니다. 풀이문제의 3번째 조건배열에서 연속한 수가 $A$와 $B$일 때, $A \leq B$ 또는 $A % B \neq 0$ 을 만족해야 한다. 는 다르게 말하면 $A$는 $B$ 이하거나 2 이상의 정수 $n$에 대해서 $nA \neq B$여야 한다는 뜻이 됩니다. 따라서 원래 문제 그대로 가기보다는 배열을 거꾸로 구성한다고 생각하면 좀 더 접근이 편해집니다. 위의 조건을 이용하면 행렬 점화식 역시 간단하게 얻어낼 수 있습니다. $V_{i.. [1150] MCMF 없이 백업 증명하기 https://www.acmicpc.net/problem/1150 굉장히 재밌었던 문제기도 했고 널리 알려진 MCMF 증명말고도 다른 방법으로도 증명할 수 있는거 같아서 글을 남깁니다. 틀린 부분 있으면 지적해주시면 감사하겠습니다! 문제요약 및 풀이$N$개의 회사들의 위치가 주어졌을때 $K$개의 케이블을 이용해서 $2K$개의 회사를 한 쌍으로 매칭시키는 문제입니다. 이 과정에서 케이블의 길이는 최소화되어야합니다. 풀이는 다음과 같은 작업 중 비용이 최소인 경우를 하나 선택하는걸 $K$번 반복해주면 됩니다. 아직 케이블로 연결된 적이 없는 인접한 두 회사를 케이블로 연결한다. 이때, 비용이 가장 작은 경우를 택한다.$p$개의 인접한 회사들이 전부 연결되어 있다고 가정하고 여기서 가장 왼쪽에 있는 회사를 .. 2024 SW-IT Contest 문제 풀이 요약 에디토리얼이 빠르게 만들어질거 같지는 않아서 약간 시간 할애해서 문제 풀이를 할까합니다. 제가 만든 문제에 한해서는 TMI도 살짝 들어가 있습니다. (A) 햄버거 정렬경우의 수가 6개 있으므로 6개에 대해서 케이스워크를 하면 됩니다. 관찰을 했다면 (1) 일때는 0번, )1(일때는 2번, 그외의 나머지 경우는 1번이라는 것을 알 수 있으므로 케이스워크를 3개로 줄일 수 있습니다. (B) 다트판 20이랑 인접한 두개의 수를 a, b라고 하면 $\frac{(a+b+20)}{3}$ 이 Alice의 점수입니다. 이 값과 Bob의 점수$(=10.5)$와 비교해서 더 큰 쪽을 출력하시면 됩니다. (C) ANA는 회문이야가장 앞에있는 A를 찾고 그 다음에 위치한 A를 찾은 다음에 그 사이에 N이 있는지를 확인해보는 .. [19060] Secret Permutation https://www.acmicpc.net/problem/19060 19060번: Secret Permutation You can ask zero or more questions and make exactly one guess in the end. Print each query on a separate line and do not forget to flush the output buffer. The maximum allowed number of queries, including the final guess, is $12\,512$. www.acmicpc.net $a_i,b_i,c_i$를 쿼리로 넣으면 $p^{-1} (p (a_i) \cdot p (b_i) + p (c_i))$의 값을 출력해준다고 했을 때.. [17969] Gene Tree https://www.acmicpc.net/problem/17969 17969번: Gene Tree A gene tree is a tree showing the evolution of various genes or biological species. A gene tree represents the relatedness of specific genes stored at the leaf nodes without assumption about their ancestry. Leaf nodes represent genes, called taxa, and inte www.acmicpc.net Tree DP로 풀 수 있는 문제입니다. 편의상 자식노드에 포함된 모든 리프 노드들과 현재 부모노드와의 거리 제곱의 합을 $.. 충남대학교 SW-IT Contest에 대한 TMI들 약 두달간 준비해왔던 SW-IT Constest 대회가 끝났습니다. 저는 이번 대회에 8문제를 출제했었는데 문제들이 만들어진 계기와 tmi 몇개 끄적여보려 합니다. 약간의 문제 풀이 스포가 있으니 참고해주세요. 타슈 문제를 만들때 실버~골드까진 있었는데 브론즈가 적어서 추가했던 문제입니다. 원래 이름은 최애의 아이였고 범위를 크게 잡아서 반복문을 사용하는 풀이가 불가능했지만 나중에 지문도 싹다 고치고 범위도 엄청나게 줄어들었습니다. 최애의 아이였을 때 지문은 그렇게 좋지 않았기 때문에 대전시와도 관련있는 지금의 지문이 훨 나은 것 같습니다. 강의실 예약 시스템 원래 만들어놨던 문제 중 관람차라는 문제가 있었는데, 지문이 정말 난해했었기에 그냥 문제를 살짝 너프시키고 지금과 같은 문제로 바꾸었습니다. 원본.. 이전 1 다음
