우선 자랑 하나 한다.플래티넘 스트릭을 올해 첫 날부터 아직까지 이었다.오늘로 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. 셋 내에서 삭제되어야 하는 원소들은 연속되어 있다.$[$기존 높이와 이루는 기울기, 새..

오늘은 좀 빡세게 풀었다. [P3] 2D 큐브(http:boj.kr/22974): 맨 왼쪽 열을 운반용 레일이라고 상상하자. 이제 행을 순서대로 올바르게 쌓아나가면 된다.[P4] 고용(http:boj.kr/5461): 적당히 간단한 그리디 문제였다. 비율을 기준으로 정렬한 배열에서 prefix를 pq로 관리하면서 비교해주면 된다.[P3] 강수량(http:boj.kr/2094): 쉬운 세그 문제다. 왜 P3인지 알 수 없다. 오랜만에 동적 세그로 구현해봤다.[P3] 길의 개수(http:boj.kr/1533) 추천 ♥️: 독특한 문제의 제한을 이용하면 창의적인 풀이를 낼 수 있다.[P2] Senior Postmen(http:boj.kr/10100): dfs 하나로 슥삭슥삭하는 그래프 능지 유형인데, 웬일로 ..

다시 좀 느슨하게 푼 것 같기도 하고..ㅠ [P2] 균형잡힌 직선형 정원(http:boj.kr/5470): 괄호 문자열 풀듯이 그래프를 그리면 할 만 하다. 세로 폭이 2 이하여야 해서 나올 수 있는 그래프의 형태가 한정되어 있는데 이 안에서 digit DP 감성의 무언가를 열심히 짜면 된다.[P5] 광부 호석(http:boj.kr/21279): 뭐.. 스트릭용 때우기이긴 하지만, 올림피아드를 대비하는 학생들은 이런 문제를 세그 없이 슥삭하는 관점이 박혀 있으면 좋다.[P5] 둘이 한 팀(http:boj.kr/33543): Goodbye, BOJ 2025! 현장에서 푼 문제인데, 이 문제 직전의 문제에서 상수 차이로 TLE를 받는 바람에, 이 문제는 선형 풀이를 찾아야 한다는 강박으로 풀다 보니 좀 고되..

오늘도 마음은 6문제를 풀려 그랬는데, 며칠간 항상 보면 아침에 랜디 3문제 돌리고서 오후~저녁 즈음에 밥 약속이 뒤늦게 성사된다. 랜디도 랜디지만 사람은 사회적 활동을 해야 하므로, 흘려보낸 3문제가 아깝진 않다. [P3] The Cow Run(http:boj.kr/5834): 대충 사수아탕이 생각나는 문제인데, 훨씬 쉽다. 그냥 아침 공복으로 먹기 든든한 DP다.[P3] 라운드 로빈 스케줄러(http:boj.kr/12016): NYPC 맛이 살짝 감도는 문제다. 혹은 코포맛? 훈련용으로 좋은 그런 건데 암튼 국밥.[P3] 흔한 수열 문제(http:boj.kr/2787) 추천 ♥️: 뭐.. 흔한 것 같지 않다. 대 한양 새내기 gubshig의 식견에 도움을 받아 해결했다. N이 작은건 알겠는데 그냥 뭘..

빡세게 푸려고 했는데자꾸 눈에 POI - Conspiracy가 밟혀서 고민하느라 시간을 많이 썼다. 걍 닥치고 플랜디가 실력향상에 무조건 이득 + 플3 주변에도 충분히 재미있고 흥미로운 문제가 많음의 이유로 랭작은 접고 플랜디를 하도록 하죠. [P5] 다리 보수 공사(http:boj.kr/33319) 추천 ♥️: 흥미로운 DP. 선발고사는 선발고사다. 플5인데도 고민할 여지가 많네..[P3] 공주 구하기(http:boj.kr/2507) 추천 ♥️: bitonic tour DP라고 한다. 이런 이름은 살면서 들어본 적이 아예 없었는데, 지난 서울과기대 대회가 끝나고 cologne님이랑 떠들다가 이런 유형도 있다는 걸 알게 되었다. 옆에 계시던 ivori2011?님이 대표 문제로 공주 구하기가 있죠.. 라고..