전체 글
-
JOISC 2020 연습 (8/3~8/15)Problem Solving/Solution Sketch 2020. 8. 16. 01:48
IOI 국가대표 선발고사에서 폭사한 이후, 기말고사 기간 동안 PS를 전혀 잡지 않았다. APIO 준비를 위해 재활훈련을 필요로 했기에, 기말이 끝난 이후인 8/3부터 BOJ에 1인그룹을 만들어 JOISC 2020의 여섯 문제를 따와 연습을 했다. 그룹 이름과는 달리, 막 열심히는 하지 말고, 그냥 시간 나는대로 몇문제 풀려고 풀었다. 처음에 6문제를 연습에 넣었고, 2주간 위의 4문제와 추가적으로 IOI19의 Rectangles를 풀었다. (솔직히 Ruins 3에 시간을 좀 많이 갈았는데, 좀 아깝다는 생각도 든다) 시간투자도 많이 안하고, 중간에 1달 정도의 공백기가 있던 것을 감안하면 어느정도 감을 되찾았다고 생각한다. JOISC 2020 Day 4 Capital City 더보기 최종적으로 도시들을..
-
BOJ 18622 DedenneProblem Solving/Solution Sketch 2020. 5. 8. 20:22
BOJ 18622 Dedenne (GP of Warsaw, Petrozavodsk Programming Camp Summer 2019 Day 5 #D) 3일 정도에 걸쳐 5시간정도 고민했고, 찾아낸 풀이가 매우 인상적인 문제였다. 우와 정말 데덴네~ 문제 설명 쿼리 $T$개가 주어진다. ($1 \leq T \leq 50000$) 각 쿼리마다 정수 $N$이 하나씩 주어지는데, 문제에서 주어진 Cost가 최소가 되도록 조건에 맞게 $N$개의 Binary String을 선택해야 한다. ($2 \leq N \leq {10}^{15}$) 조건은 1. 선택한 모든 Binary String에서 연속한 두 자리에 모두 0이 올 수 없다. 2. 선택한 한 Binary String이 다른 Binary String의 Pre..
-
BOJ 18254 쿼리와 쿼리Problem Solving/Solution Sketch 2020. 3. 11. 23:28
http://noj.am/18254 20.03.11 기준 solved.ac R5 ----------------------------------------스포방지선---------------------------------------- M개의 선행 쿼리를 쿼리1, Q개의 후행 쿼리를 쿼리2라고 부르겠다. 전처리로 쿼리1이 ${A}_{i}$를 변화시키는 것을 처리해야한다. Lazy Propagation을 이용한 세그먼트 트리로도 가능하지만, 이후에 쿼리2를 처리할 때도 비슷한 구간 xor 쿼리를 처리해야 하기 때문에, 상수의 이득을 위해서 펜윅 트리를 사용하는 것이 좋다. 기우성에 따라 잘 나누어서 펜윅 트리로 처리하면 펜윅 트리 2개만을 이용해서 구간 xor 쿼리를 처리할 수 있다. 아래의 코드를 참고하는..