그래프에서 간선 가중치의 bitwise or이 최소가 되는 경로

E - Minimum OR Path E - Minimum OR PathAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 무방향 연결그래프에서 1번부터 N번까지 가는 단순 경로들의 모든 가중치들의 bitwise or의 최솟값을 구하는 문제 단순 경로는 어떤 정점을 두번이상 방문하지 않는 경로를 말한다. 1 > 2 > 3 > 4 > 5는 단순 경로 1 > 2 > 3 > 2 > 3 > 4 > 5는 2번 3번을 2번 방문했으므로 단순 경로가 아니다. ---------------------------------------------..

• format_list_bulleted 알고리즘/그래프 이론 정복기
• · 2025. 6. 2.
• textsms

합과 bitwise or연산이 같게되는 조건

1322번: X와 K  x+y = x | y를 만족하는 k번째로 작은 자연수 y를 구하는 문제 합과 or 연산이 서로 같게되는 조건을 먼저 생각해본다 or연산은 두 bit가 1이면 1이고 두 bit가 0이면 0이고 두 bit가 1,0으로 서로 다르면 1인 연산 두 수를 합하는 것은 어떤 의미인지 생각해본다 x,y를 2진수로 바꿔서 예를 들어 5 = 101이고 12 = 1100인데 이진수끼리 서로 덧셈은 어떻게 하는가? $101 = 0 * 2^{3} + 1 * 2^{2} + 0 * 2^{1} + 1 * 2^{0}$ $1100 = 1*2^{3} + 1 * 2^{2} + 0 * 2^{1} + 0 * 2^{0}$ 우측에 2의 거듭제곱으로 바꾼 것끼리 더한다고 생각해보면,  $(0 + 1)*2^{3} + (1+1..

• format_list_bulleted 알고리즘/비트마스킹
• · 2025. 1. 9.
• textsms