codeforce3 cf 626 div2 D - present (수론, 이분탐색) https://codeforces.com/contest/1323/problem/D 어렵지만 여기저기서 출제된 적이 있는 문제. 핵심 아이디어는 가져가자 최대 4e5개의 원소 n개를 갖는 배열이 있다. 원소는 1e7이하의 자연수를 갖는다. n개 중 2개 원소의 가능한 모든 쌍에 대해 합을 구해 모두 xor한 값을 구해라 (a1+a2)⊕(a1+a3)⊕ … ⊕(a1+an)⊕(a2+a3)⊕ … ⊕(a2+an)…⊕(an−1+an) 한 쌍의 합의 최댓값은 2e7이므로 답을 ans라 했을때 ans는 24개 비트로 표현 가능하다. ans의 k번째 비트가 켜져있는지 nlogn에 알 수 있다. a의 원소들은 k+1번 이후의 비트는 k번째 비트에 영향을 주지 않는다. b 2020. 3. 15. Educational round #72 div2 D - Coloring Edges (방향그래프 사이클) https://codeforces.com/contest/1217/problem/D (editorial 풀이) 방향그래프가 주어진다. 정점(n)과 간선(m)의 최대는 각각 5000이다. 각 간선에 최소한의 색(k)을 칠해서 같은 색의 간선끼리 cycle이 생기지 않도록 하는 k와 그때 간선의 색을 모두 출력하는 문제다. editorial의 설명 -> 간선 (u,v)가 back edge : if there is a path from v to u by edges from dfs tree 문제 풀땐 if there is a 'edge' from v to u by edges from dfs tree 로 생각하도록 하겠다. dfs tree를 그리고 back edge를 추가한 그래프를 떠올려보자. 다음은 1, 2 /.. 2019. 12. 5. codeforces #591 div2 C - Save the Nature (이분탐색) 모든 변수를 long long으로 바꿔주니 ac받았다. 배열크기n과 배열을 입력받고, a번째 요소마다 x퍼센트의 기부금을 주는 것에 대한 입력 a,x,b,y를 입력받고, 기부금의 최소금액인 k를 입력받는다. 위와 같이 입력받은 후, k이상의 기부금을 받을 수 있는 최소한의 티켓수를 구하는 문제이다. 문제에서 배열의 순서를 자유롭게 할 수 있다고 한 것에 속아넘어가지 않고, 수학적으로 생각하면 된다. 조건에 맞는 티켓의 최소값을 찾는 이분탐색에 isPossible함수를 O(n)으로 구현해서 전체 O(logn)이다. isPossible함수는 다음과 같이 구현했다. 팔리는 티켓수를 m이라고 할 떄, 1) (x+y)%가 붙는 경우는 t = m/lcm(a,b) 2) x%가 붙는 경우는 r = m/a-t 3) y%.. 2019. 11. 1. 이전 1 다음
