리유나의 항해일지

막판에 페이스 떨어져서 못할까 걱정했는데, 대회 두번 참여하고 이것저것 꿀문제 헌팅 하면서 겨우 2020년이 오기 전에 1000문제 찍었네요 이제 문제도 1000개 풀었으니까 숫자보다는 어려운 문제들 찾아서 풀어보는 쪽으로 해봐야 할 것 같아요 수고 많았어 나 자신아....

크리스마스인데 A형 독감에 걸려서 골골대고 있습니다. 그 와중에 PS는 하고 있는 게 참 웃겨요... 아무튼간에 오늘은 950솔브를 달성했습니다. 시험 끝나고 이것저것 바빠서 페이스를 많이 잃었는데, 덕분에 올해 안에 1000솔브 하려면 조금 열심히 달려야 할 것 같습니다. 오늘은 FFT를 공부했습니다. 그리고 활용 문제를 몇개 풀어서 950 솔브를 달성했습니다. FFT하면서 든 생각인데...진짜 파이썬은 ps 할만한 언어가 아닌 거 같아요... 파이썬으로 내면 거의 다 TLE고 Pypy로 내도 겨우겨우 커트 맞춰서 돌아가는데 이게 언어냐.......

870솔브 했습니다. 여전히 꿀문제 위주로 푼 것도 사실이긴 한데, 그래도 너무 그러는 것 같아서 1페이지에 있는 비교적 번호 빠른 문제들에 도전해봤습니다. 1014 컨닝: 사람을 그래프 정점으로, 컨닝할 수 있는/당할 수 있는 사람의 쌍을 그래프 간선으로 잇게 된다면 그래프에서 최대 얼마만큼의 independent set을 만들 수 있느냐는 문제가 됩니다. 처음에는 그래서 네트워크 플로우를 생각했는데 자기 양 옆 줄의 사람들만 컨닝할 수 있으니까, 결국 홀수번째 줄/짝수번째 줄로 각각 이분 그래프를 만들 수 있게 됩니다. 그래서 이건 Kőnig의 정리에 따라서 이분매칭 문제가 될 수 있고, 실제로 이분 그래프로 잘 만들어 주면 됩니다. 1017 소수 쌍: 자연수가 중복되지 않으니까, 1+1=2는 불가능..

850 솔브와 350등을 동시에 달성했습니다! 상당수의 문제는 solved 기준으로 브론즈4 돌면서 풀어서 사실 허수긴 한데, 그래도 세그먼트 트리나 레이지 프로퍼게이션, 2-SAT이랑 SCC등은 연습해서 의미가 있었다고 생각합니다. 앞으로 이정도 밸런스로 150개만 더 풀면 되겠네요 하루에 6문제만 풀면 된다(?)

오랜만입니다. 현재 810문제인데, 2019년 내로 1000솔브 하는 걸 목표로 해서 달려보기로 했습니다. 실패 시 무언가를 걸면 조금 더 좋을 거 같은데...이건 추천받아요! 아무튼간에 열심히 해볼게요!