티스토리

레프네 약방

검색하기

블로그 홈

레프네 약방

tamref.com/m

졸업하고 싶다

구독자: 11

방명록 방문하기

주요 글 목록

BOJ 18763 Knowledge oriented problem Problem statement정점 $n$개인 무방향 그래프 $G$가 주어진다. 정점이 $k$개인 path $P_k$와의 cartesian product $G \square P_{k}$의 cartesian product의 스패닝 트리의 개수를 구하여라. $n \le 500$, $k \le 10^{18}$.Matrix-tree theorem그래프 $G$의 Laplacian 을 $L_{G} := D_{G} - A_{G}$로 쓰자. $L_{G}$는 real symmetric matrix이고, positive semidefinite이므로 양의 실수 고윳값을 갖는다. Connected graph $G$에 대해 $L_{G}$는 rank $n-1$이 되는데, non-zero eigenvalue를 $\lambda_{1.. 공감수 0 댓글수 0 2025. 4. 17.
BOJ 21268 Do Use FFT https://www.acmicpc.net/problem/21268솔루션에서 Tellegen's Principle을 인용하고 있어서 지난 포스트와 연관해 작성해본다. 머리 좋은 사람들은 아마 생각하지 않고도 풀 수 있을 것 같다.Without Tellegen's principle$E_{k} = \sum_{i = 1}^{n} C_{i} \prod_{j = 1}^{k} (A_{i} + B_{j})$를 답이라고 하자.$i$와 관련한 항들을 사부작거리다보면, $P_{j} = \sum_{i = 1}^{n} C_{i}A_{i}^{j}$를 미리 계산해두면 편할 것 같다.$\sum_{j} F_{k, j}x^{j} = (x+B_1)(x+B_2)\cdots (x+B_{k})$라고 두면, $E_{k} = \sum_{j} P.. 공감수 1 댓글수 0 2025. 1. 31.
BOI 2016 Swap BOI 2016 Swap순열 $x_1, \cdots, x_n$ 이 주어질 때, $i = 2, \cdots, n$ 에 대해 (순서대로) $x _ {[i/2]}$와 $x _ i$ 를 스왑할 수 있는 기회가 한 번씩 주어진다. 이를 적절히 사용하여 만들 수 있는 사전 순 최소 순열을 구하여라.풀이$x_i$의 후보는 $x_i, x_{2i}, x_{2i+1}$ 셋 뿐이고, 사전 순 최소를 생각하면 이 중 최소인 값이 $i$번 자리에 들어가는 것이 당연하다.(자명한 경우) $i$번 자리에 $x_i$ 또는 $x_{2i}$가 들어가는 경우, $(2i, 2i+1)$번 자리가 각각 $(x_{2i}, x_{2i+1}), (x_{i}, x_{2i+1})$로 강제된다.(비자명한 경우) 하지만 $x_{2i+1}$이 들어가는 경우.. 공감수 0 댓글수 0 2025. 1. 22.
2021 Jan-Feb Problem Solving 글 쓰는 법을 까먹을 것 같으니, 몇 개 되지 않는 문제들을 줏어담아보자. BOJ 20556. 둥둥섬 다리 재정비하기 20556번: 둥둥섬 다리 재정비하기 첫 줄에 섬의 수 $N$과 쿼리의 수 $Q$가 주어진다. $(1 \leq N,Q \leq 300\,000)$ 이후 $N-1$개의 줄에 걸쳐 다리들이 연결하는 두 섬 $u$와 $v$가 공백으로 구분되어 주어진다. $(1 \leq u,v \leq N)$ 이후 $Q$개의 줄 www.acmicpc.net 루트가 \(r\)로 고정되어 있다고 할 때, \(a\)개의 다리를 재정비해서 얻을 수 있는 최적의 결과는 가장 큰 \(a\)개 서브트리의 크기 합이라는 사실을 간단하게 알 수 있다. 따라서 "가장 큰 \(k\)개의 합"이 지원되는 자료구조에 서브트리들의 크기.. 공감수 2 댓글수 0 2021. 3. 4.
BOJ 10129 작은 새 https://www.acmicpc.net/problem/10129 10129번: 작은 새 문제 경기과학고의 뒤뜰에는 일렬로 된 n개의 나무로 이루어진 숲이 있다. 그 중 첫 번째 나무 위에는 마지막 나무의 위로 올라가고 싶어하는 작은 새가 한 마리 있다. 그 새는 몸집이 매우 작기 때문에 한 번의 비행으로 날아갈 수 있는 거리에 한계가 있다. 만약 새가 i번째 나무 위에 있다면, 이 새는 한 번의 비행으로 i+1, i+2, …, i+k번째 나무 중 하나로 갈 수 있으며 그보다 멀리 떨어진 나무로는 가지 못한다. 또한, 작은 새에게 지금 있는 www.acmicpc.net 더보기 가장 먼저 드는 생각은 \(dp[i]\)를 "\(i\)번 나무에 도달하기 위해 느끼는 피로감의 횟수"로 정의하는 것이다. 점화식.. 공감수 0 댓글수 0 2020. 2. 10.
BOJ 17962 Game on a Tree + BOJ 3419 Racing Car Trail 이 문제에서는 SEERC '19 Game on a Tree와 CERC '11 Racing Car Trail의 풀이를 다룬다. 풀이의 첫 단어부터 강력한 스포일러가 될 수 있으니 충분한 고민을 해보고 오는 것을 권한다. 풀이 설명 또한 두 문제의 context에 의존하는 경향이 강하니 지문을 숙지하고 오자. https://www.acmicpc.net/problem/17962 17962번: Game on a Tree In a single line, print “Alice” (without quotes), if Alice wins. Otherwise, print “Bob”. www.acmicpc.net https://www.acmicpc.net/problem/3419 3419번: Racing Car Trail.. 공감수 0 댓글수 0 2020. 1. 28.
BOJ 13318 위험한 해싱 https://www.acmicpc.net/problem/13318 13318번: 위험한 해싱 string matching 알고리즘에는 여러 가지가 있다. KMP 알고리즘이나 BoyerMoore 알고리즘이 그 예시이다. 하지만 지구이는 KMP를 이해할 수 없었고, BoyerMoore는 시간복잡도가 너무 컸다. 결국 지구이는 틀릴 확률이 있지만, 간단한 방법인 해싱을 즐겨 사용하게 되었다. 해싱은 문자열을 숫자 하나로 바꾸는 해시 함수를 하나 정의한 후, 이 값이 같은지 다른지를 통해 문자열이 같은지 판별하는 방법이다. 지구이는 해시 함수를 다음 www.acmicpc.net 풀이 두 해시값을 뺀 다항식을 생각하면, 그 다항식은 아래와 같은 조건을 만족해야 한다. \(\deg f < 300000\) \(.. 공감수 2 댓글수 0 2020. 1. 19.
solved.ac 티어 매긴 문제들 - Gold 편 Baekjoon Online Judge에는 유용한 문제 난이도 기능 solved.ac 가 있다. 내가 기여한 문제들의 풀이를 간략하게 써보려고 한다. 아마 Gold, Platinum이 주류가 될 것 같고, Diamond 이상은 개별 풀이 포스팅을 할 것 같다. 형식은 문제 번호 (내가 준 티어) 순이다. Gold / Platinum / Diamond 수준의 구분은 신경을 쓰지만, Gold I ~ V의 세부적인 분류는 문제를 푼 직후에 즉흥적으로 내린 경우가 더 많다. 참고 정도만 하자! BOJ 1762. 평면그래프와 삼각형 (Gold II) 불러오는 중입니다... BOJ 2026. 소풍 (Gold III) Last update 19.12.16. 더보기 Maximal clique problem의 결정 문제.. 공감수 0 댓글수 0 2019. 12. 8.
BOJ 14859 세 쌍 서로수 문제 링크 14859번: 세 쌍 서로소 크기가 n인 수열 a1, a2, ..., an이 주어졌을 때, 1 ≤ i < j < k ≤ n 이면서, GCD(ai, aj, ak) = 1인 세 쌍 (i, j, k)의 개수를 구하는 프로그램을 작성하시오. 여기서 GCD는 최대공약수를 의미한다. www.acmicpc.net \(\text{MAX} = 10^6\) 범위의 수가 \(n\) 개 주어져 있고, 이 중에서 \(\gcd\)가 1인 triplet의 개수를 구하는 문제이다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 .. 공감수 2 댓글수 0 2019. 8. 17.
BOJ 16143 선형대수와 응용 HOLICS 18 문제로 출제된 문제다. 진짜 선형대수 문제인 줄 알고 처박아놨다가 쉬운 문제인 걸 알았다... 문제 링크 스포방지선 썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방.. 공감수 0 댓글수 0 2019. 3. 15.
HYEA cup H - Too Many Traps 풀이 문제 링크 공식 에디토리얼 1년 가까이 틀려 있었던 문제다. 에디토리얼을 읽고도 이해를 못해서... 내가 이해한 대로 다시 써보려고 한다. 문제 요약 수직선상에 \(M\)개의 이불이 있고, 혜아는 원점 \(0\)에 서 있다.혜아는 \(N\)개의 신발을 가지고 있는데, \(i\)번째 신발을 사용하면 \(A_{i}\)만큼 +방향으로 갈 수 있다.\(M < N\)이 성립할 때, 모든 신발을 한 번씩만 사용하여 이불에 닿지 않고 \(A_{1} + A_{2} + \cdots A_{N}\)으로 갈 수 있겠는가? 있다면 순열을 construct하고, 아니면 -1. 제한 :\(1 \le M < N \le 10^{5}\), \(1 \le A_{i} \le 10^{9}\), 이불의 위치 \(X_{j} \le 10^{14}.. 공감수 1 댓글수 0 2019. 3. 11.
190101 재활 프로젝트 : shake! 2018 후기 문제 링크 (BOJ) 풀이 슬라이드 (slideshare) 이제는 습관처럼 집을 나가는 PS 실력을 되살리기 위해 쉬운 대회를 풀어보기로 했다. 6시간 (밥 1시간) 을 세팅했고 결과는 7 / 8. B는 디스크립션을 오독해서 전혀 다른 문제를 풀어버렸다😡 A B C D E F G H A < C = F = H < B < E < G < D 난이도는 평이한 수준. 괜찮은 문제들 + 좋은 문제 (D) 로 구성되어 있어서 퀄리티도 나쁘지 않다. 다만 돚거해온 훔친 문제 (E, H)가 2개나 들어와 있다는 게 흠이라면 흠. 문제 푸는 감을 다시 살리기에 굉장히 좋은 셋이다. 빡센 자료구조 문제 / 케이스 분석을 해보고 싶었는데 그런 문제는 안 나왔더라... 일단 B를 제외하고 모든 문제를 큰 무리 없이 푼 건 좋았.. 공감수 0 댓글수 0 2019. 1. 1.
BOJ 2593/15994 엘리베이터 문제 링크 내가 만든 엘리베이터 2 (더 강한 문제) This section is intentionally left blank. 이런 문제는 왜 중등부 지역본선에 나오는 걸까? 그 당시 중학생들은 뭐하는 사람이었던 거지 ㄷㄷ 1. Naive\(O(M^2 N)\) 두 엘리베이터가 이어져 있다면 cost 1의 간선을 연결해주고 BFS를 돌리면 된다.엘리베이터 \(i\), \(j\)의 연결을 판별하기 위해 1층부터 \(N\)층까지 돌면서 이 층이 두 엘리베이터가 공유하는 층인지 단순 나머지 연산으로 확인해주면 다음의 복잡도를 얻는다.안타깝게도 이 방식으로는 TLE를 피할 수 없다. 2. Clever\(O(MN)\) imeimi2000의 풀이 방식이다.그래프의 정점을 에지로 보지 않고 \(N\)개의 층으로 두자.. 공감수 0 댓글수 5 2018. 8. 18.
[MWT@SSHS] 모의고사 #5 풀이 안녕하세요 탐렢입니다!5번째 모의고사에는 std::set, std::map 등의 자료구조를 익히기 좋은 문제들을 모아놓았습니다.맞은 뒤에도 적극적으로 저나 다른 멘토들의 코드를 보면서 STL 활용법을 얻어가세요! A. 숫자 카드 2 map을 이용해서 해결할 수 있는 간단한 문제입니다. 좌표압축을 해도 되지만 map이 훨씬 간단하죠! map M;X가 적힌 숫자 카드 저장 : ++M[x]; X가 적힌 숫자 카드의 개수 출력 : cout S; 사원 넣기//마지막 글자가 'r'인지만 체크하면 된다.if(X.back() == 'r') S.insert( X.substr(0, X.size() - 6) ); // " enter"를 제외한 사원명을 X에 삽입else S.erase( X.substr(0, X.size() .. 공감수 0 댓글수 1 2018. 7. 19.
[MWT@SSHS] 모의고사 #4 풀이 안녕하세요~ 저는 모의고사 #4 풀이를 작성하게 된 신동원입니다. 백준 아이디 messi가 저예요!레프가 출제한 이번 모의고사 #4 9문제는 전부 Segment Tree를 이용해서 풀 수 있었습니다. A. 구간 합 구하기 수열 $A_1, ...., A_n$가 주어졌을 때, 원소 하나에 주어진 수를 더하는 쿼리와 $A_l, ...., A_r (1 \leq l \leq r \leq n)$의 합을 구하는 쿼리를 그 때 그 때 해결하는 문제입니다.세그먼트 트리를 이용해서, 세그먼트 트리의 각 노드가 관리하는 구간의 합을 저장해주면 쿼리당 $O(log(n))$만에 해결할 수 있습니다. B. 구간 합 구하기 2 수열 $A_1, ...., A_n$가 주어졌을 때, 주어진 구간의 모든 원소에 주어진 수를 더하는 쿼리와.. 공감수 0 댓글수 0 2018. 7. 19.
[MWT@SSHS] 모의고사 #3 풀이 3회 모의고사는 DP-like 문제 8개로 만들었습니다.코드는 조금만 기다려주세요! A. 기차 여행 솔직히 이거 분류가 왜 DP인지 모르겠습니다. 그래도 좋은 문제라서 넣었어요. 문제의 핵심은 i번 열차를 몇 번 타게 되는지 카운트해주는 것입니다. Range-Update Fenwick / Segment Tree를 이용하면 간단히 \(O(n\lg n)\)에 해결할 수 있습니다. 다만 이 경우에는 쿼리(i번 열차를 몇 번 타는가?)에 대한 답을 online으로 구할 필요가 없고, 맨 마지막에 한 번만 구하면 된다는 특성을 이용하면 \(O(n)\) 복잡도에 해결할 수 있습니다. 배열 F[1..n]을 잡고,구간 [s,e)에 1을 더해주는 업데이트가 있다면F[s] += 1;F[e] -= 1;을 실행한 뒤맨 마지막.. 공감수 0 댓글수 0 2018. 7. 18.
[MWT@SSHS] 모의고사 #2 풀이 코드는 잠시만 기다려주세요ㅠ A. 리조트 DP[i][j] 를 i일차를 살아내야 하는데 쿠폰이 j개인 상황에서의 최소 비용이라고 합시다.하루에 아무리 쿠폰을 득달같이 모아도 2개씩 모을 수 있으므로 j (i+1,j). 추가비용 0 i일에 수영이사 여행을 갈 수 있는 경우 : (i,j) -> (i+1,j). 추가비용 10000(i,j) -> (i+3,j+1) 추가비용 25000(i,j) -> (i+5,j+2) 추가비용 37000 (i,j) -> (i+1,j-3) 추가비용 0 (j >= 3) 단, 답은 DP[n+1][0] ~ DP[n+5][2*(n+5)] 중 최솟값임에 주의합시다. B. 카드 합체 놀이 허프만 알고리즘의 간단한 응용입니다. priority_queue를 이용해서 값이 가장 작은 두 카드 x, y.. 공감수 0 댓글수 0 2018. 7. 17.
[MWT@SSHS] 모의고사 #1 풀이 코드는 Team github에서 압축파일로 받을 수 있습니다.압축 해제 비밀번호는 imeimi2000입니다. A. 소가 길을 건너간 이유 5 b[i]를 i번 신호등이 망가졌는가? 를 묻는 boolean 변수,S[i]를 ([i-K+1, i]의 신호등 중 망가진 것의 개수) = (b[i-K+1] + ... + b[i]) 라고 하면,문제는 min(S[K-1], ... , S[N-1]) 을 구하는 문제로 바뀝니다. S[i+1] = S[i] + b[i] - b[i-K]임을 이용하면 O(N)만에 문제를 해결할 수 있습니다. B. Binary Roads BFS를 정직하게 개조하면 해결할 수 있는 문제입니다. 정점 v를 (v,0)과 (v,1)의 독립된 2개의 정점으로 보고, 에지 u-v의 값이 0이면 (u,0) -> .. 공감수 2 댓글수 0 2018. 7. 15.
8/3~8/6 연습 그 동안 쉬운 문제만 푸느라 문제 정리를 올리고 싶은 의욕이 없었다. 앞으로는 그냥 의식의 흐름대로 풀리는 문제는 적당히 필터링하겠다. 1052. 물병http://icpc.me/1052 일단 물병을 무한정으로 사올 수 있기 때문에, 항상 답을 찾을 수 있다. 그냥 입력의 \(N\)보다 큰 최소의 \(2^p\)꼴의 숫자를 찾으면 물병을 1개로 만들 수 있기 때문에, 답은 항상 \(2N\)보다 작다는 것도 알 수 있다.그런데 그대로 내면 당연히 4%대에서 틀리게 된다. 아이디어를 조금만 발전시키자. \(X\)개의 물병을 압축할 수 있는 최소 개수는 \(X\)를 이진수로 나타냈을 때 각 자리수의 합, 즉 \(s_2 (X)\)가 됨을 알 수 있다. 즉 물병을 더해 가면서 \(s_2 (X) \le K\)가 성립하.. 공감수 0 댓글수 0 2017. 8. 6.
8/2 연습 5485. 평균값 수열 (IOI '05) http://icpc.me/5485 이 문제에서 가장 중요한 아이디어는 \(s_1\)과 \(m_1 \cdots m_{n-1}\)만으로 \(s_2 \cdots s_n\)을 결정할 수 있다는 것이고, 따라서 가능한 수열의 개수는 가능한 \(s_1\)의 개수와 같다는 것이다.수열의 단조 증가 조건으로부터,\(s_2 = 2m_1 - s_1 \ge s_1 \Rightarrow s_1 \le m_1\)\(s_3 = 2m_2 - s_2 \ge s_2 \Rightarrow s_1 \ge 2m_1 - m_2\)\(s_1 \le 2m_1 - 2m_2 + m_3\)\(\vdots\)와 같이 \(s_1\)에 관한 총 \(n-1\)개의 부등식을 얻을 수 있고, 이를 통해 \(s_1\)의.. 공감수 0 댓글수 1 2017. 8. 3.
8/1 연습 2820. 자동차 공장 문제 : http://icpc.me/2820 세그먼트 트리의 클래식한 활용 문제. 사실 suhgyuho가 준 문제집에 있던 건데 이제서야 풀었다(...) 이 문제의 아이디어는 트리를 Segment Tree나 Fenwick Tree같은 구간 자료구조와 엮을 때 자주 쓰는 트릭 중 하나인데, 어떤 노드 \(v\)의 서브트리 (\(v\) 포함) 를 DFS-numbering에서 붙은 번호 \([d[v], f[v]]\)의 구간으로 처리하는 것이다. 이 트릭을 적용하고 나면 문제의 쿼리는 이렇게 바뀐다 : p 쿼리 : 구간 \((d[a],f[a])\)의 원소에 \(x\)를 더한다. (range update)u 쿼리 : 구간의 \(d[a]\)번째 원소의 값을 구한다. (point query) .. 공감수 0 댓글수 0 2017. 8. 2.
7/30 ~ 7/31 연습 3584. 가장 가까운 공통 조상 문제 : http://icpc.me/3584 옛날 ICPC문제여서 그런지 진짜 LCA를 대놓고 묻는 문제. 이 때는 아직 LCA가 고ㅡ급 알고리즘이었나보다. 테스트 케이스마다 배열 초기화에 주의하도록 하자. LCA에 대해서는 더 잘 설명해놓은 글들이 천지빽가리.http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220820773477 Time Complexity : \(O(Tn)\) 8984. 막대기 (KOI '13)문제 : http://icpc.me/8984http://oj.uz/problem/view/KOI13_game BOJ AC 기준으로 게시.문제 조건을 잘못 이해해서 이거 완전 NP 아니냐? 하고 풀이를 깠다. 이해.. 공감수 0 댓글수 0 2017. 8. 1.
7/29 연습 2969. 메뚜기 (COCI 08/09 Contest #1 5번) 문제 : http://icpc.me/2969 오래전에 친구가 교내 대회에 냈던 문제인데, 그때 아무생각없이 \(O(n^4)\)이랑 \(O(n^3)\) 생각하고 끝냈던 문제. 일단 \(dp[i][j]\)를 \((i,j)\)에서의 최장 경로라고 하자. 이제 각각 \(n\)개씩의 행/열에 대해서 \(dp\)값과 좌표를 저장해두는 자료구조를 만든다. 높이가 낮아지는 순서대로 탐색하면서, i+1열, i-1열, j-1열, j+1열에 저장된 dp값들 중 조건을 만족하면서 가장 큰 dp값을 \(D\)라고 하면, \(dp[i][j]=D+1\)이 된다. 자료구조를 맨 처음에는 set으로 했는데, set을 허투루 썼더니 메모리 초과가 났다(...) 여윽시 s.. 공감수 0 댓글수 0 2017. 7. 30.
7/27~7/28 연습 어제 올리려고 하다가 9시에 자버렸다 ㅁㄴㅇㄹ... 이번에는 MWT 특집.2011. 암호코드문제 : icpc.me/2011 간단한 dp인데, 0인 경우를 생각해주지 않으면 가버릴 수 있다. 입력 문자열을 \(S\)라고 하고, \(D[i]\)를 \(S_1 \cdots S_{i-1} \)를 해석할 수 있는 경우의 수라고 두자. 입력이 0으로 시작하지 않는다는 것이 보장되어 있으므로 \(D[2]=1\)이다. 이제 dp를 앞에서 뒤로 뿌려주자.\(S_i \neq 0\)인 경우, \(S_i\)를 하나의 암호문으로 해석할 수 있으므로 \(D[i+1]+=D[i]\).\(S_i \neq 0 \wedge 10S_i + S_{i+1} < 27\)인 경우, \(S_iS_{i+1}\)를 하나의 암호문으로 해석할 수 있으므로 .. 공감수 0 댓글수 0 2017. 7. 29.
7/26 연습 #1. 중량제한 문제 : icpc.me/1939 굉장히 다양한 풀이가 가능한 문제인데, description을 잘못 이해해서 ㅂㄷㅂㄷ하다가 결국 풀이를 까봤다. 1. BFS 물건을 보내는 공장을 \(s\), 받는 공장을 \(t\)라고 하자.또 각각의 정점까지 수송할 수 있는 최대의 비용을 \(F[v]\)라고 하자.(정점 \(v\), c=\(s\)에서 \(v\)까지 옮길 수 있는 최대 비용)의 순서쌍을 저장할 수 있는 큐 \(Q\)를 잡고, \(Q\)에 \((s,F[s]\leftarrow \infty)\)를 넣으면서 BFS 개시. \(Q\)가 빌 때까지, \(Q\)의 front \(k\)에 대해서 \(k.v\)에 연결되어 있는 점 \(u\)들을 보는데, \(min(k.c,bridge\_capacity[v\.. 공감수 0 댓글수 0 2017. 7. 27.
7/25 연습 1. 이상한 수열 (OJUZ #10) http://icpc.me/11917 http://oj.uz/problem/view/OJUZ10_bizarre 풀이 : oj.uz에서 처음 봤을 때 아무 생각 없이 62점을 받고 넘겼던 문제다. 100점 풀이 생각 못한 뚝배기를 매우 쳐라 \(M\)이 비상식적으로 크므로, \(B_i\)의 값을 거의 닫힌 꼴로 구할 수 있을 것이라는 생각을 해야 한다. \(S\)를 오름차순으로 정렬한 뒤, \(B_{n+1}\)의 값 (\(S_1, S_2, \cdots S_n\) 중 서로 다른 수의 개수)이 어떤 \((S_i,S_{i+1}]\)에 있게 되면 이 값은 \(S_{i+1}\)로 수렴하고(편의상 \(S_{n+1} = \infty\)라 두자), 그 전까지는 값이 1씩 증가하게 됨.. 공감수 0 댓글수 0 2017. 7. 26.
7/24 연습 *이 문제 set은 백준 온라인 저지에서 랜덤을 돌려서 푼 문제들입니다. 풀이를 좀 포멀하게 적고 싶어서 쉬운 문제라도 모두 풀이를 상세하게 기록할 예정이니, 그게 마음에 들지 않으신 갓갓분들은 살포시 뒤로가기를 눌러 주세요. 1. 수열 축소 문제 : http://icpc.me/2237 풀이 : 얘는 고1때 정올을 딱 시작할 때쯤 풀지 못하고 넘겨버린 문제. 사실 CON이란 연산이 전혀 대단하지 않다는 것만 알면 된다. CON연산을 수행한 결과는 수열의 인접한 원소 사이에 + 또는 -의 부호를 적절히 삽입하여 계산한 식이다. (단, \(a_2\)앞에는 반드시 -가 붙는다) 그래서 \(n \times (2\sum{a_{i}}+1)\) dp table을 잡고,\(dp(i,j) : a_{1}~a_{i}\)까지.. 공감수 0 댓글수 0 2017. 7. 25.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.