목록오늘의 코딩 (386)
one day left
domination에 관련한 굉장히 깔끔하게 정리된 사이트를 발견했다. wow..예전 KTU camp Day5의 문제는 결국 Biclique를 구하는 문제였는데, 이건 결국 complement graph상에서의 maximum independent set을 구하는 문제로 변환이 가능하다! 이건 König's Theorem에 따라 bipartite graph가 perfect하고, perfect한 그래프는 그것의 complement도 perfect하기 때문에 maximum clique를 쉽게 구할 수 있는 것.minimum vertex cover를 구하는 알고리즘 = 반전시키면 maximum independent set을 구하는 알고리즘도 새롭게 알았다. 엣지들에 방향성을 부여해서, 매칭에 포함된 간선은 오른..
SRM 338 Hard의 editorial에서 가져옴.. "winning position"이라는 것이 정말 광역으로 쓰일 수 있구나.. 와.. 문제상에서 어떤 한 특성을 잡고 그것의 여집합과의 관계를 생각해서 winning position을 창조해 낼 수도 있다니 정말 신박하다.. algorithmic game에 정말 자신이 없었는데, matrix game과 저 CakeParty를 풀고 나니 조금 이해가 되는 느낌이다.
KTU Programming Camp Day 5를 돌았다. 맞는 해법을 썼던 E를 틀린 게 아쉽고, 자원을 까다롭게 써야 해서 recursion으로 segment tree를 짰더니 계속 TLE가 났던 G가 아쉽다.
코포 NEERC subregional셋을 돌았는데, 좋은 측면도 있고 나쁜 측면도 있었다.좋은 점은 내가 persistent segment tree를 어느정도 써먹게 되었다는 점으로, G를 괜찮은 시간안에 풀어낼 수 있었다는 점이 고무적이었고, H도 도움을 받아 구현해낼 수 있었다는 점..나쁜 점은 대전 리저널에 참가하는 최소 2팀이 우리보다 성적이 우월했다는 점. 특히 인터넷 예선 1등팀이 이번에도 역시나 2문제를 더풀면서 두 단계 앞서나갔다.
제일 우울우울해서 좋아했던 prelude..
이놈의 시험기간은 인생에서 수십번을 넘게 겪어도 당췌 적응이 되지 않는다그래도 요 며칠간 리저널 걱정때문에 찾아온 불면증이 도움이 된다. 어제는 정말 고통스러웠는데, 침대에 누워있으면 자꾸만 내가 풀지 못한 문제들이 머릿속에 떠오르고 아직 다루지 못한 테크닉이 머릿속을 채우고, 아직 구현이 익숙하지 않은 자료구조 문제가 나오면 빠른 시간 내에 AC를 받을 수 있을까하는 걱정이 뒤를 이었다. 결국 폰으로 persistent segment tree를 검색해서 다시 tutorial을 읽고 나서야 잠에 들었는데, 그게 새벽 5시쯤.. 생활패턴이 완전히 망가진 탓인지 오늘은 지금도 잠이 오지 않는다.Chopin Competition이나 들으면서 멘탈을 정화해야지..
수업때문에 못돌았던 CF #325를 돌았는데 ABC를 풀어서 행복했다. 특히 C는 예전에 풀었던 문제의 연장선상에 있는 문제라서 학습에 도움이 많이 됐다. 물론 저 코드는 삽질하는 코드지만 java도 조금씩 익숙해지고 있당..
이번 Codeforces #326의 E. Gaussian Elimination + segment tree인데, 0과 관련한 작은 glitch가 있어서 디버깅에 두시간 넘게 걸렸다... 이것이 자료구조의 고통...
는 어느 작년 월파 9등한 중국 팀의 연습기록.. 폴더를 열어보면 한 셋이 거의 전부 풀려있음... 우리보다 이미 훨씬 잘하는데, 훨씬 연습량이 많아 이길 자신이 없다...월파 나가고 싶다. 그 자리에 서 있고 싶고 티셔츠도 입고 싶고 데스크에 놓인 팀이름 명찰도 간직하고 싶고 사진 한 번 남겨 평생 들여보고 싶다. 이게 내 인생에서 가장 중요한 일이고 모든 걸 쏟아부어야 할 일인 것 같다. 그 어떤 것도 희생할 준비가 되어 있는데, 이게 억지로 시간을 쏟아부어 되는 일이 아니라는 걸 내가 더 잘 안다. 답답함에 한숨만..그래서 초조하다. 이젠 해법이 잘 안떠오르는 내가, 해법을 이해하지 못하는 내가, 해법을 제대로 구현하지 못하는 내가 화가 날 때도 있다. 원래는 단계별로, 차근차근이 내 기조였는데, ..
CF #326은 아쉬움이 많이 남는 셋이다. ABC를 풀었으면 yellow까지 노려볼만 하지 않았을까 싶은데, B의 문제를 잘못 이해하는 바람에(contiguous하다는 중요한 조건을 빼먹음) 결국에 풀지 못했다. C는 그냥 HLD를 빡세게 구현하는 문제라, 풀었어도 보람이 남진 않았다.. D는 문제조차 이해하지 못했고, E,F는 뭐....
오랜 숙원 중 하나였던, CERC14의 을 무려 14108ms의 수행시간으로(..) AC를 받았다. 기본 원리는 APIO13의 과 유사하게, 동적 MST에 관한 것이다. 엣지를 추가하다가 cycle이 발견되면, 해당 cycle의 최대요소를 제외한다는 것이 idea이다. 이문제에서는 이런 서로 대체관계에 있는 엣지들의 pair를 묶어버리고, 여기에서 range sum query를 수행해야 했다. 즉 range에 두 엣지가 모두 들어갈 수 있으면, 작은 weight의 엣지로 대체하는 방식이다. 이는 배열을 저장하는 segment tree로 \( O( \lg^2{N} ) \)의 단위쿼리 수행시간을 맞출 수 있다.해당 코드는 내 것이 아니고 solution에 나온 것인데, vft는 vector로 된 fenwic..
오늘 공강시간에 친구와 같이 공부하고 있던 중이었다. 나는 를 읽으면서 이 책을 찬양하고 있었고, 친구는 LaTeX로 문서편집을 하면서 그 위대함을 찬양했다. 슬슬 수업시간이 다가올 즈음.. 내가 책의 뒷면을 보고 어? 이 책 공저자 Knuth가 TeX를 만들었다는데?했고 그건 사실이었다. 우리는 서로 다른 방향으로 Knuth를 찬양하고 있었던 것이었다.. Knuth는 의 1~3권을 저술하여 CS를 집대성한 공로로 Turing Award를 수상했고 그 과정에서 엄청난 양의 원고를 예쁘게 만들기 위해 TeX가 창안되었다고 한다.. 오늘은 Knuth뽕에 취해야겠다.. 크...누스...
오랜만에 팀연습으로 SEERC 2013을 돌았다. 꿀잼셋이었음! 원래 E번 를 풀어보려고 제안한 셋이었는데, 결국 E를 못풀었다.ㅠㅠ 끙 정수론.. 정수론! 위의 코드는 B인 를 해결하는 부분인데, BFS를 "완전그래프 상에서 주어진 엣지만 제외한 나머지 경로를 탐색"하는 걸 고안해야 했다-_- 한 두어시간 고민하다가 결국 저런 O(ElogV) 해법을 찾아냄.. 뿌듯뿌듯
2위 기념 스크린샷 한장.. 쉬운 문제들을 풀고 올라간거라 별로 뿌듯하진 않고 몇 문제에서 많은 걸 배웠다. 는 union of circles의 계산방법을 친절하게 설명해준 문제였는데, 결국 원주를 따라서 선적분을 수행하는 방식이었다. Green's Theorem을 조금 배우고 multivariable calculus를 그만 듣는 바람에(..) 아직도 정확한 이해는 부족하다. 어떻게 선적분을 수행하면서 각 원에 독립적으로 적분부분을 더할 수 있는거지?은 nim-sum에 대한 심화이해를 돕는 문제였다. 내 지식 밖의 문제라 열심히 검색을 하던 중(..) 난데없이 xkcd포럼에서 똑같은 문제를 퀴즈로 낸 사람을 발견했고, 원리를 대충 감잡을 수 있었다. 결국 금지된 nim-sum move를 제외한 0부터 센..