공부 기록

버츄얼 돌다 만난 문제. 투포인터랑 부분합을 더 많이 풀어봐야겠다는 생각이 들었다. 일단 버츄얼 중에는 B를 만나고 멘탈에 많은 타격이 들어와 슼보를 왔다갔다 하며 C를 풀까말까 했다. 결국 B와 C 모두 풀지 못했다. 문제 핵심 아이디어$pfx$ 배열의 단조성을 이용하여 이분탐색 or 투포인터를 사용해야한다. 일단 m개의 creature에게 분배될 수 있는지부터 확인해야 하기 때문에 이를 관리해주어야 한다. $pfx[i]$를 앞에서부터 $i$ 까지 봤을 때 분배해줄 수 있는 creature 수라고 하고 $sfx[i]$를 뒤에서부터 $i$ 까지 봤을 때 분배해줄 수 있는 creature 수라고 하자.  이는 투포인터로 연속된 구간의 합을 합/차 해가며 그리디하게 $pfx$ 배열에 기록해주면 된다. 포인터..

codeforces 2024. 11. 22. 11:03

버츄얼을 돌던 중 만난 문제이다. 발상이 조금 특이해 블로그에 기록한다. 1. permutation 만드는 것이 가능한 경우 일단 permutation을 만들 수 있는 경우만 생각해 보면 $b$가 0 이상이면 다 된다. 모든 원소가 unique하기 때문에 $[0,n-1]$을 만들 수 있다. 이때 원소 중 $0\leq x$0\leq x 2. 불가능한 경우버츄얼 때에는 $b=0\;and\;c=0$으로 잡아서 틀렸다. (\앞으로 더 신중하게 반례를 생각해볼 필요가 있을 것 같다.\) 불가능한 경우는 $b=0$일 때를 주목하면 된다. $b=0$일 때 모든 원소는 $c$로 구성되어있다. 이들에 대해 연산을 진행하다보면 순환을 만나게 되는데 바로 $c+1\rightarrow c+2\;\;c+2\rightarrow..

codeforces 2024. 11. 11. 23:09