3090. 차이를 최소로쉬운 문제. 풀고 P4를 매겼나 그랬다.값 증가도 가능한 줄 알고 잠시 동안 아무 접근을 못 하고 있었다. CERC 2019확실히 실력이 늘었다. 저번에 INC 2023 2인 팀연습에서 혼자 7문제 풀었는데, 이번에는 3인 팀연습에 준혁이가 껴있었는데 4문제를 풀었다. 패널티도 확실히 많이 줄었다. 맞힌 문제 중에 틀린 제출은 A에 한 번 밖에 없는데, 이건 영어 이슈였다.문제 번호가 없는 문제지를 뽑아서 소통에 어려움이 있었다.A. ABB앞뒤 중 하나를 골라 거기에 원하는 문자열을 삽입할 수 있을 때, 삽입해야 하는 문자열의 최소 길이를 구하는 문제였다.팀노트에 있는 나랑 base가 다른 해싱 코드를 따라 적다가.. "이건 뭐 0.5-base냐?? 왜 작동을 안 해 ㅋㅋ"를 시전..

우선 자랑 하나 한다.플래티넘 스트릭을 올해 첫 날부터 아직까지 이었다.오늘로 93일차라고 한다. blobnom.xyz에서 제공하는 땅따먹기 사이트가 꾸준히 플래2~3을 푸는 의욕을 유지시켜 준다.백준 연습과는 다르게 한 달간 푼 문제들의 티어가 한 눈에 보이고, 연습 기간을 2주 이상 지속시키는게 가능하기 때문에 너무 좋다. 2월 땅먹 랜디 아마 북마크에 들어있던 다양한 경로 속 문제들을 짜집어서 만들었던 것 같다.뽑힌 문제들 퀄리티가 다 좋았다. 좀 더 많이 채울 수 있었을텐데 아쉽다. 3월 땅먹 랜디 2월 땅먹은 평균 난이도가 P3이 되도록 뽑아뒀었다.3월 땅먹은 좀 더 난이도를 올린 P2로 해보기로 했다.그렇게 꾸준히 풀지는 못했다. 맨날 잘 시간 다 되어서 플래티넘 스트릭을 잇기 위해 아무 P5..

뿌듯하다! Mafia (BOJ  8161)maximum은 크기 $A$의 컴포넌트가 simple cycle이라면 $\max\{1,A-1\}$를, 그렇지 않다면 $A-(\mathrm{deg}^{-}(v)=0$인 정점 수$)$를 부여해서 싹 더하면 된다.minimum은 MIS 문제로 환원되므로 사이클만 떼어내고, 나머지 트리 부분들을 위상정렬과 함께 DP로 채워주고, 사이클들을 엮어서 DP를 한 번 더 돌리면 된다. Simple (BOJ 21958)홀/짝 반전과 값 변화를 동시에 레이지로 잘 관리하면 된다. 크레이피쉬 글쓰는 기계 (BOJ 5812)print를 제외한 명령어들에서 각각 '커서' 변수를 잘 관리하면 된다.사용하는 string은 어차피 prefix로 만든 trie 같은 형태를 띠므로, 잘 정리한 ..

문제 링크 일단 풀이 설명을 하기 전에 자랑을 하나 짚고 넘어가도록 한다. 문제의 지문이 굉장히 난잡하지만, 요약하면 간단하다. 지문 요약1번과 2번 정점이 문제의 중요한 정점이다. 무향, 무가중치 그래프를 다룬다.1번과 2번 정점을 잇는 경로가 존재함이 보장된다. (번역문에는 누락된 조건)1번과 2번 정점을 잇는 최단 경로는 5 이상이다.여전히 1번과 2번 정점을 잇는 최단 경로가 5 이상이도록 간선을 추가할 때, 추가할 수 있는 간선 개수의 최댓값을 구하여라.$2\le V\le 40\,000;$ $0\le E\le 1\,000\,000$. 풀이더보기생각1. 5는 작은 상수다. 조건에 맞게 모델링을 하자!주어진 그래프의 형태는 다음과 같다. a, b, c, d 영역은 주어진 그래프에서 우선적으로 고정 ..

문제 링크 관찰 1. 모든 기울기의 종류가 그렇게 많지 않다.모든 업데이트가 하나의 원소에 대한 것이므로 모든 순간에 대해 가능한 기울기는 최대 $O(n^2 + nq)$이다.따라서, 각 원소를 최대 한 번씩만 삭제하는 것이 가능하다면, 알고리즘은 시간 내에 동작할 것이다.생각 1. $i$번째 산이 볼 수 있는 산 $j$들을 자료구조로 관리하면서, 업데이트 이후 볼 수 없게 된 산들만 잘 골라내서 지우고 싶다.스택 또는 셋으로 관리하고 싶은데, 기울기가 단조 증가하도록 관리되는 것이 자연스럽다.그런데, 셋의 정의가 '볼 수 있는 산들'이기 때문에, 기울기가 증가하는 순서가 곧 인덱스가 증가하는 순서이기도 하다.관찰 2. 셋 내에서 삭제되어야 하는 원소들은 연속되어 있다.$[$기존 높이와 이루는 기울기, 새..