yunny.world

https://www.acmicpc.net/problem/24532 24532번: 트리와 XOR 쿼리 1번 노드를 루트로 하며 간선에 가중치가 있는 트리가 주어진다. 모든 노드의 번호는 $1, 2, \cdots{} , N$ 으로 이루어져 있다. 두 노드 $x$, $y$ 에 대하여, $x$에서 $y$로 가는 단순 경로 상의 모든 가 www.acmicpc.net 문제 요약 길지 않으니 직접 문제를 읽어보자. 풀이 하루정도 고민하다가 답 보고 해결했다. 에디토리얼이 정말 잘 되어있다. 생각의 흐름을 요약해보자. 트리에서 어떤 두 정점 u, v의 단순 경로 상의 모든 가중치를 xor한 값을 d(u, v)라 하자. 어떻게 d(u, v)를 빠르게 구할까? 더보기 d(u, v) = d(1, u) ^ d(1, v)를 ..

https://atcoder.jp/contests/abc336/tasks/abc336_e E - Digit Sum Divisible AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 문제 요약 $N$보다 작거나 같은 수 중 Digit Sum으로 나누어 떨어지는 수의 개수를 구하라. 풀이 가능한 모든 Digit Sum에 대한 Digit DP 값들을 모두 더해주자. Digit DP를 할 것이기 때문에, 주어진 수를 문자열로 바꾸어주자. ex) 2024 → 00000000002024 dp[i][j][k][s][f]를 다음과 같이..

https://www.acmicpc.net/problem/25057 25057번: Evolution of Weasels A wild basilisk just appeared at your doorstep. You are not entirely sure what a basilisk is and you wonder whether it evolved from your favorite animal, the weasel. How can you find out whether basilisks evolved from weasels? Certainly, a good first step www.acmicpc.net 문제 요약 문자열에 AA, BB, CC, ABAB, BCBC를 추가하거나 삭제하여 변형할 수 있다. 두 문..

https://www.acmicpc.net/problem/8240 8240번: Take-out In the first line of the standard input there are two integers, n and k (2 ≤ n ≤ 1,000,000, 1 ≤ k ≤ n-1), separated by a single space, that denote the total number of blocks used in the game, and the number of white blocks per black node (to be rem www.acmicpc.net 오늘 이 문제를 풀고 언제 스택을 떠올려야 하는지에 대해 한 번 생각해 보게 되었다. 위가 아래보다 더 자주 보이는 상황인데, 위 상황은 처리하..

쌍블루를 찍었다. 본계 yunny_world는 코포 시작하고 65라운드 쳐서 블루 갔었는데, 부계 yunny는 7라운드만에 간 거 보면 가짜 블루는 아니었나 보다. 이제 부계를 블루에 주차시켜놓고 본계로 계속 칠 예정이다. 이제 뭐 민트가도 상관없으니.. 개인적으로 본계 그래프가 맘에 들고, 그래프 계속 만드는 게 재밌기도 하고 뿌듯해서 웬만하면 퍼플 주차하기 전까진 본계로 칠 거 같다. 예전에 호영님이 내 본계 그래프 보고 되게 힘들게 갔다고 말해주셨는데, 개인적으로 뿌듯했다 ㅋㅋ 쨋든 이제 걱정 없이 코포 칠 수 있다는 게 맘에 든다. 요즘 백준 너무 안 풀어서 강박이 조금 있었는데, 이거라도 해서 다행이다. 이걸 해서 실력이 늘진 않았지만 심신의 안정을 얻었으니 만족한다. 스트릭의 족쇄에서 해방되었..

https://www.acmicpc.net/problem/27652 27652번: AB 집합 $A, B$와 문자열 $S$에 대하여, 다음 쿼리를 수행하는 프로그램을 작성하시오. add A $S$: $A$에 $S$를 추가한다. delete A $S$: $A$에서 $S$를 제거한다. add B $S$: $B$에 $S$를 추가한다. delete B $S$: $B$에서 $ www.acmicpc.net 2023 성균관대학교 프로그래밍 경진대회를 미는 중에 만난 문제이다. 풀이 그냥 하면 될 거라 생각해서 풀었다. 쿼리 들어올 때마다 접미사, 접두사를 관리하는 map을 관리하면 해결할 수 있다. 이렇게 짜면, $O(Q|S|log(Q|S|))$ 정도의 시간이 걸린다. 최악 $1000*1000*20$ 정도의 시간이 걸..

최근에 업다운랜디의 존재를 알게 되어서 재밌어 보이길래 시작하게 되었다. IBory님 블로그 보다가 알게 된 듯? 링크는 양해가 될 수 있으니 달지 말자.. 내가 한 방식은 solved.ac에서 *g5 -@$me s#100.. 걸고 검색한 다음, 시프트 마음대로 누르고 가장 위에 나오는 문제를 풀었다. 타이머를 키는 시점은 문제 지문을 열어본 순간부터고, T분 안에 문제를 풀면 윗 티어로 넘어가고 못 풀면 아래 티어로 내려간다. T = (티어 - G5)*5분 + 30분이다. 예를 들어 P5 문제를 풀어야 하면, T = 5*5분 + 30 = 55분 안에 풀어야 한다. 나는 G2정도부터 시작했다. 2632 피자판매(G2) 누적합 관리하는 문제였던 걸로 기억한다. 4198 열차정렬(G1) 조금의 관찰을 하면,..

https://codeforces.com/contest/1796/problem/C Problem - C - Codeforces codeforces.com 이 문제를 풀면서 본 조건이 자주 나오는 것 같아 정리해 두려고 한다. 물론 웰노운이다. 그냥 자동적으로 떠올릴 수 있도록 하기 위해서 글을 쓴다. A set of positive integers S is called beautiful if, for every two integers x and y from this set, either x divides y or y divides x (or both). 위 조건이 주어졌을 때 가장 먼저 떠올려야 하는 것은 제곱수이다. 즉, 위 조건을 만족하는 집합은 \( a^x (x >= 0) \) 이다. 증명은 귀류법..

https://codeforces.com/contest/1792/problem/D Problem - D - Codeforces codeforces.com 이 문제를 풀다가 이 성질을 알아내서 정리해 두려 한다. 고수들은 이미 다 알고 있었겠지? 여기서 순열의 정의는 다음과 같다. a permutation of length m is a sequence of m distinct integers from 1 to m. 결론부터 말하자면, 순열 A의 인덱스 배열을 B라 하면, B도 순열이고, 순열 B의 인덱스 배열은 A이다. 예시를 살펴보면 쉽게 감을 잡을 수 있다. A: 3 4 5 2 1 → B: 5 4 1 2 3 B: 5 4 1 2 3 → A: 3 4 5 2 1 증명은 아직 잘 모르겠다. 생각나면 추가하도록..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 풀이 일단, 문제를 다음과 같이 해석할 수 있다. (인덱스 → 선택된 학생의 번호) 의 간선들로 이루어진 그래프에서 사이클을 구성하지 않는 정점의 개수를 구하라. https://yunny-world.tistory.com/56 [BOJ] 11581번 : 구호물자 https://www.acmicpc.net/problem/11581 11581번: 구호물자 서기 2050년 엄청나게 강력한 폭풍이 인천을 강타했..