03.10 PS 일지

 

뿌듯하다!

 

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 같은 형태를 띠므로, 잘 정리한 뒤 sparse table로 k번째 조상을 잘 찾아주면 된다.