트리 위의 모든 입자 이동시켜서 소멸시키기(트리에서의 다이나믹 프로그래밍)

https://atcoder.jp/contests/abc409/tasks/abc409_e E - Pair AnnihilationAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 트리 위에 정점 i에서 xi개의 양전자가 놓여있고, 혹은 -xi개의 전자가 놓여있다. 이때 모든 입자의 합은 0임이 보장된다. 따라서 입자들을 적절히 이동시키면 모든 입자를 소멸시킬 수 있다. 한 입자를 간선 j를 따라 이동시키면 에너지 wj가 소모된다. 양전자와 전자가 같은 정점에 속하면 입자가 소멸된다. 모든 입자를 완전히 소멸하는데 필요한 최소 ..

• format_list_bulleted 알고리즘/다이나믹 프로그래밍
• · 2025. 6. 14.
• textsms

0이나 1을 뒤집어서 1이 연속인 구간이 최대 1개로 만들기

D - Flip to Gather D - Flip to GatherAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 0과 1로 이루어진 문자열이 주어진다. i번째 문자를 0이면 1로, 1이면 0으로 뒤집는 연산을 0번 이상 한다. 이때, 주어진 문자열에서 1이 연속인 구간이 최대 1개가 되도록 만들려고 한다. 100111이면, 1이 연속인 구간이 1, 111로 2개이므로 1번째 1을 0으로 뒤집어서 000111로 하면 111인 구간 1개만 존재하여 조건을 만족한다. 조건을 만족하게 하는 연산 횟수의 최솟값은? -------..

• format_list_bulleted 알고리즘/애드 혹 알고리즘
• · 2025. 6. 5.
• textsms

그래프에서 간선 가중치의 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

올바른 괄호 문자열을 만드는 알고리즘

1. 올바른 괄호 문자열 1) 모든 k = 1,2,3,..,n에 대하여 $S_{1}, S_{2},...,S_{2k-1}$에 대하여 적어도 k개의 문자가 '('이다. 2) 모든 $S_{1}, S_{2},...,S_{2n}$에 대하여 정확히 n개의 문자가 '('이다. --------------------------------------------------------------------------------------------------------------------------- 단순히 개수만 맞아도 올바른 괄호 문자열이 된다? 예를 들어 S1S2S3S4로 생각해보면 S1 = '(' S1S2S3에서 적어도 2개의 문자가 '(' S1이 '('이어야하는데, 이때 S1S2S3S4는 정확히 2개의 문자가 '(..

• format_list_bulleted 알고리즘/그리디 알고리즘
• · 2025. 5. 26.
• textsms

AtCoder Beginner Contest 406 대충 복기(증가하다가 감소하는 수열의 개수)

1. D번 https://atcoder.jp/contests/abc406/tasks/abc406_d D - Garbage RemovalAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp H*W 배열에서 (x,y) 위치에 쓰레기가 N개 주어진다. Q개의 쿼리가 다음과 같이 주어진다. 1 x는 x행의 모든 쓰레기 수를 출력하고, x행의 쓰레기를 모두 제거 2 y는 y열의 모든 쓰레기 수를 출력하고, y열의 쓰레기를 모두 제거 먼저 x행, y열 별로 각각 쓰레기들을 모아둔다. 1 x가 주어지면 x행의 쓰레기들을 조회해서 제거하지..

• format_list_bulleted 경쟁 프로그래밍/Atcoder
• · 2025. 5. 18.
• textsms

AtCoder Beginner Contest 405 대충 복기(BFS, 최단경로, 경우의수, 팩토리얼 모듈로 역원)

1. D번 D - Escape Route D - Escape RouteAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 2차원 배열이 주어질때, 각 위치에서 탈출구 E번까지 가는 최단 경로를 표시해야하는 문제 #은 이동불가능 지역이므로 표시하지 않는다. ..E...이라고 한다면? >>E>>^ 이런식으로 될 것이다. 혹은 정답이 여러개일 수 있는데 >>E^>^도 정답이 될듯? 각각의 지점에서 E까지 가는 최단 경로를 어떻게 찾는다고 하더라도 표시를 어떻게 해야하지? 각각의 지점이 1000*1000개인데 이걸 언제 다하냐? 그..

• format_list_bulleted 경쟁 프로그래밍/Atcoder
• · 2025. 5. 11.
• textsms