one day left
혼자 꽤나 박진감 넘쳤던(?) 경기였다. 결국 round 2에 안착함 밖에 나갔다가 30분넘겨 경기를 시작한 상황-_- 근데 어이없게도 A, B가 어렵지 않아 B-large를 냈을 때 1700명가량이 A, B를 풀었더라. C를 안풀면 안되겠다 하고 C를 들여다보고 여러 접근을 시도했다.우선 문제는 N개의 vertex와 N개의 edge로 이루어진 그래프가 주어진다. 여기에서 원형으로 vertex들을 배치해야 하는데, 각 vertex는 양옆 중 하나와 연결되어 있어야 배치할 수 있다. 이 조건을 만족시킬 때 가능한 최대 size를 구하는 것.2SAT이 되나?싶어서 boolean식을 써보니까 3SAT이 나오더라ㅋㅋㅋ 최적화 문제가 되나 싶어서 시작/끝번호를 정한 dp를 생각해봐도 포함시키는 순서를 정할 수가 ..
그래 퀄이라도 올솔브 해야지ㅋㅋ... 중간중간 밖에 나갔다와서 페널티가 많이 붙음.A : operation을 직접 구현해서 돌려보면 되는 문젠데, operation수가 돌려볼만한 각이 나오는지 약간 생각이 필요하다. 상한은 100정도 될 것 같은데, \(N\)이 \(K\)자릿수라고 하면 \(c*N\)에 대해서 \(K+1\)자릿수는 \(1, 2, 3, \cdots, 9\)를 순차적으로 거쳐갈 수밖에 없기때문. 따라서 확실히 \(K+2\)자릿수가 생기는 100 이전에는 모든 숫자가 한번씩 나오게 될 것이라 예상할 수 있다.B : 역시 구현문제.. flip operation은 같은 위치에 여러번 할 필요 없이, 0-1로 수행하는 게 최적이다. 그리디로 맨 뒤에서부터 -가 있으면 range flip을 해주면서 ..
ㅋㅋ이번학기에 처음으로 제대로 리버싱을 해보는 것 같아 재밌다. 어셈블리 명령어의 진입장벽만 넘으면 꽤나 재미있게 할 수 있는 것 같다. 리눅스 터미널에서 복사는 대체 어떻게 하는걸까ㅋㅋㅋㅋㅋ gdb의 결과를 vim으로 에딧하면서 하고싶은데 그게 안됐다.PS는 이번학기엔 현상유지만을 목표로 해야겠다..ㅠ.ㅠ일단 codejam은 지원해놓긴 했는데.
A푼김에 나머지도 풀어봐야지~하고 건들었는데 B의 미궁 속에 빠져 헤어나오지 못했음ㅋㅋㅋA : \( dp[i] = \max_{j
virtual participation.. 어렵지 않은 구현문제들이었다. A : \(O(n^2)\)B : \(O((M+N)^2)\). 중복쿼리를 합치고 직접 칠하면 된다.C : 문제를 개념화하면서 range sort라고 이해했고 이러면서 range query도 힘든데 소트를 하라니 멘붕이 오면서 시작점이 zero로 고정되어 있다는 사실을 까먹었다-_- 그래서 D로 일단 넘어간 다음 다시 돌아와서 풀었음. 중요한 observation은, 쿼리당 이후에 자기보다 긴 쿼리가 나오면 쓸모가 없어진다는 것.. 일단 이렇게 내림차순의 쿼리꼴을 만들어 준 후에, deque로 element를 빼주면서 답을 만든다. 그렇게 어렵지 않은 문제였는데 역시 제약을 파악하는 것은 중요함-_-D : KMP를 써서 풀었다. 패턴을..