목록전체 글 (51)
PS 부수기
문제 링크 atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_c C - Cell Inversion AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 관찰 1) (a, b) (c, d)와 (a, d) (b, c)의 효과는 같다. 관찰 2) S가 주어진다면, 그 S에서 화살표의 왼 부분이 될 문자들과, 오른 부분들이 될 문자들은 이미 정해져있다. index가 짝수번째이면서 B이거나, 홀수번째이면서 W이면 언제나 화살표의 왼쪽이 배정되고 (괄호문자열의 "(") 반대 경우는 언제나 화살표..
문제 링크 : www.acmicpc.net/problem/18535 사용 알고리즘 : DSU, 구현 관찰) G 위치 두 곳에 가고일이 있다고 해보자. 두 가고일은 서로 거울에 의해 보일 수 있는 위치에 놓여있다. 이 떄, 한 가고일을 특정 방향으로 고정시키면, 다른 가고일의 방향도 무조건 고정되는 것을 알 수 있다. (그렇지 않으면 한 가고일이 다른 가고일의 옆면을 보게 된다.) 이는 가고일이 두마리가 아니라 여러마리여도 확장할 수 있는 개념이다. 서로 거울로, 혹은 그냥 공기로 연결된 가고일들끼리는, 한 가고일의 방향만 결정해주면 나머지 가고일의 방향은 자동으로 결정된다는 것이다. 따라서 연결된 가고일끼리 DSU로 부모를 같게 해준 뒤, 원래 orientation에서 바뀌는 정도의 cost를 계산해 주..
문제 링크 : atcoder.jp/contests/abc050/tasks/arc066_b D - Xor Sum AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 관찰) A + B = A ^ B + 2 ( A & B ) A | B + A & B = A + B -> A | B = (u + v) / 2, A & B = (u - v) / 2 이다. -> A | B + A & B x + y > digit) & 1; if(digit == 62) { if(flowBit == 0 && under == true) return ret = 1..
step 1. 빨갛게 두른곳 합 구하기 각 노드마다 자기를 포함한 자기 아래의 자식들 노드의 합을 전처리로 sum 배열에 저장해두자. L, R을 2씩 나눠가며 점점 트리 위로 올라갈 것이다. L은 짝수일 경우, sum[L-1]을 빼주면 되고(파란 삼각형들) R은 홀수일 경우 sum[R+1]을 빼주면 된다.(보라 삼각형들) 쭉 L, R을 2로 나누다가 L R이 같아질떄(LCA에 도달했을 때) sum[L]을 더해주면 된다. 2) 문제 풀기 우선, dfs 한번으로 각 노드마다 리프노드까지 도달하는 직선경로의 합 중 최댓값을 val 배열에 전처리해두자. 파란 동그라미 옆의 값은 이 노드의 val 값이다. 여기에서의 답은 저 빨간 거대노드의 합(1에서 구한거) + 100 + 50 -> 첫번째 + 두번째로 큰 다리..
세번째로 푼 다이아문제! 우선 문제에서 주어진 그래프는 완전그래프! 라는 사실이 중요하다. 이 그래프의 특성은, 방향이 주어진다면 모든 정점에서 나가는 화살표의 갯수의 합 = 모든 그래프에서 들어오는 화살표의 갯수의 합 = 상수 라는 것이다. 이 때문에 비둘기집의 원리 사용이 가능해진다. N=75 최대일 때를 생각해보자. 우리는 일단 최대한 한번에 많이 색칠을 하고싶다. 그렇기 때문에 나가는 방향의 간선이 최대인 정점을 골라서 칠해줄 것이다. 비둘기 집의 원리에 의해 최소한 하나의 정점은 37개의 다른 정점으로 뻗어나갈것이다. -> 이게 최소가 되는 경우는 모든 정점이 37개의 간선을 받고, 모든 정점이 37개의 간선을 내보내는 균형을 이루고 있는 케이스일 것이다. 여기에서 만약 36개 정점으로 뻗게 만..
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 vector isPrime(1000001); bool solve(int n) { set a; int digit = 0; int temp = n; while (temp > 0) { digit++; temp /= 10; } int pow = 1; for (int i = 1; i
12345678910111213141516171819202122232425VI fact; bool solve(int n) { int sum = 0; int temp = n; while (n > 0) { sum += fact[n % 10]; n /= 10; } return temp == sum;} int main() { fact.push_back(1); int mul = 1; for (int i = 1; i