vertex multiplexing을 이용한 가중치의 bitwise xor이 최소가 되는 경로

vertex multiplexing을 이용한 가중치의 bitwise xor이 최소가 되는 경로

https://atcoder.jp/contests/abc410/tasks/abc410_d D - XOR Shortest WalkAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 방향 그래프가 주어지는데, A에서 B로 가는 간선의 가중치가 W이다. 이때, 1번부터 N번 정점까지 경로의 가중치들의 bitwise xor이 최소가 되는 경로에 대해 그 최솟값을 구하면? 여기서 1번부터 N번 정점까지 경로는, 동일한 간선이나 동일한 정점을 여러번 방문하더라도, 처음 시작점이 1번이고 마지막 종점이 N번인 경로이다. ----------..

  • format_list_bulleted 알고리즘/그래프 이론 정복기
  • · 2025. 6. 18.
  • textsms
C++ 이항 연산자와 삼항 연산자

C++ 이항 연산자와 삼항 연산자

1. 이항 연산자 표현식 (피연산자) (연산자) (피연산자)처럼 연산에 참여하는 피연산자가 2개인 표현식 대부분의 산술 연산자와 관계 연산자가 여기에 속함  1) 산술연산자(수치 계산) 대입: a = 10 더하기: a + b 빼기: a - b 곱하기: a * b 나누기: a / b 나머지: a % b  2) 관계 연산자 (true/ false로 관계 평가) 같음 : a == b 같지 않음: a != b 초과: a > b 이상: a >= b 미만: a  이하: a   3) 논리 연산자 논리 AND(둘 다 true일때만 true) : a && b 논리 OR(둘 중 하나만 true여도 true이고 둘 다 false일때만 false) : a || b  4)비트 연산자 AND : a & b OR : a | b X..

  • format_list_bulleted 프로그래밍/C++
  • · 2025. 4. 11.
  • textsms
해밍거리 + BFS 경로 역추적하기

해밍거리 + BFS 경로 역추적하기

2479번: 경로 찾기 이진 코드들이 주어질때, A 이진코드에서 B 이진코드로 가는 경로를 찾을려고 한다 이때 경로를 구성한 노드간 서로 인접한 코드끼리의 해밍거리가 1이어야한다 해밍거리는 길이가 같은 두 이진코드들에서 왼쪽부터 오른쪽으로 차례로 비교할 때 서로 다른 값을 가진 비트의 수이다 예를 들어 010과 110은 서로 다른 비트가 0번째 비트로 1개이므로 해밍 거리가 1이다 코드 번호 A,B가 주어질때 가장 짧은 해밍 경로를 찾는다 -------------------------------------------------------------------------------------------------------------------------------------------------- 두 코..

  • format_list_bulleted 알고리즘/DFS BFS 정복기
  • · 2025. 2. 3.
  • textsms

XOR 문제에 접근하기 위해 반드시 필요한 스킬3 -모든 쌍의 XOR의 합(sum of all pair of xor)-

1. 모든 원소 쌍의 XOR 합 $A_{0}, A_{1}, ... , A_{n-1}$에 대하여 $\sum_{i=0}^{i=n-1} \sum_{j=i+1}^{j=n-1} A_{i} \oplus A_{j}$을 구하는 문제 단순하게 풀면 $O(N^{2})$이지만 조금 더 생각해본다면 $O(N)$에 가깝게 해결할 수 있다. 결국 구하고자 하는 값은 $V = A_{i} \oplus A_{j}$라고 할 때, 이 V들의 합이다. 그런데 V를 2진수로 나타낸다면.. $$V = a_{k}2^{k} + a_{k-1}2^{k-1} + ... + a_{1}*2 + a_{0}$$로 나타낼 수 있다. 여기서 $a_{i} = 0$이거나 $a_{i} = 1$이다. 만약 모든 $V = A_{i} \oplus A_{j}$에 대하여 최대..

  • format_list_bulleted 알고리즘/애드 혹 알고리즘
  • · 2024. 1. 27.
  • textsms
XOR 문제에 접근하기 위해 반드시 필요한 스킬2 - 연속하는 부분열의 XOR-

XOR 문제에 접근하기 위해 반드시 필요한 스킬2 - 연속하는 부분열의 XOR-

1. 연속하는 부분열에 대한 XOR n개의 음이 아닌 정수 $A_{1}, A_{2}, ... , A_{n}$에 대하여 L번부터 R번까지의 XOR $A_{L} \oplus A_{L+1} \oplus ... A_{R}$의 값은? 만약 $V_{0} = 0, V_{i} = A_{1} \oplus A_{2} \oplus ... \oplus A_{i}$라고 하자. $V_{L-1} = A_{1} \oplus A_{2} \oplus A_{3} .... \oplus A_{L-1}$이다. 그러면, $0 \oplus x = x, x \oplus x = 0$이므로.. 0을 xor해도 값이 달라지지 않는다. $$A_{L} \oplus A_{L+1} \oplus ... A_{R} = 0 \oplus (A_{L} \oplus A_..

  • format_list_bulleted 알고리즘/애드 혹 알고리즘
  • · 2024. 1. 25.
  • textsms

XOR 문제에 접근하기 위해 반드시 필요한 스킬1 - 기본 성질 -

1. 기본 성질 정수 x,y,z에 대하여... $$ x \oplus 0 = x $$ $$ x \oplus x = 0 $$ $$ x \oplus y = y \oplus x $$ $$ (x \oplus y) \oplus z = x \oplus (y \oplus z)$$ 사실 교환법칙, 결합법칙이 성립하고 0을 xor하면 그대로 나오고 자기자신을 xor하면 0이 나온다는거 아는데 만약 n개의 원소 a1,a2,a3,...,an에 대하여.. a1 ^ a2 ^ a3 ^ ... ^ an을 생각해보자. a2 ^ a3 ^ a4 ^ ... ^ an의 값을 알고 싶다면 어떻게 해야할까? a1+a2+a3+...+an을 알고있다면 그냥 a1을 뺀다면 되는데 xor에서는 이런 빼기 연산이 있는건가? 다시 a2,a3,..,an을 ..

  • format_list_bulleted 알고리즘/애드 혹 알고리즘
  • · 2024. 1. 23.
  • textsms