1. Redistributing Gifts굉장히 까다로운 Bitmask DP 문제라고 생각한다. 핵심은 이 문제를 사이클 만들기 문제로 생각하는 것이다. $1$부터 $n$까지 번호가 매겨진 정점이 있는 그래프 $G$에서 $i$번 선물을 $j$번 소에게 줘도 문제없다면 간선 $i \to j$가 있다고 생각하자. 이때 이 문제는 각 연결성분들을 사이클로 구성하는 방법의 수를 묻는 것과 같다. 단, G와 H로 이루어진 종 문자열이 주어지는데, 이는 한 사이클에 종 G와 종 H의 소가 모두 있을 수 없음을 나타낸다. 정의상 모든 $i$에 대해 $i \to i$ 간선이 있음에 유의하자. 사이클을 이루는 방법의 경우의 수를 세는 것이 목표인데, 두 가지 주의할 점이 있다. 첫 번째는 사이클의 시작점에 따라 여러 개..
1. Uddered but not Herd서브태스크의 제한을 잘 읽어 보면, 사실 문자 $26$가지 중 최대 $20$가지만 입력에 들어옴을 알 수 있다. (이런 식으로 세팅하는 것은 가독성을 흐려 굉장히 안 좋다고 생각한다.) 따라서 Bitmask DP를 생각해 보자. 알파벳이 총 $k$종류가 등장할 때, 최종적으로 정한 알파벳의 순서를 $s_1 s_2 \dots s_k$라 하자. 이때 이 문자열을 반복하는 최소 횟수는 입력 문자열 중 인접한 두 문자를 보았을 때, $s_1 s_2 \dots s_k$에서와 순서가 반대인 경우이다. $DP[t]$를 비트마스크 집합 $t$에 해당하는 문자들의 순서를 첫 $popcount(t)$개 위치에 고정했을 때 (즉 $s_1 s_2 \dots s_{popcount(t)}..
1. Bessie's Function문제의 조건을 Functional Graph로 생각하자. 이때 각 정점은 다음 둘 중 하나여야 한다:i번 정점은 self loop를 가진다 (즉, a_i = i여서 i \to i의 간선이 있다.)a_i번 정점은 self loop를 가진다. (즉, a_{a_i} = a_i이다.)조건에 따라, 어떤 점 i에 대해 a_i를 바꾼다면 그 값을 i로 바꾸는 게 최적임을 알 수 있다. 모든 간선 i \to a_i에 대해, i 또는 a_i에 대해 위 조건이 만족해야 한다. 이미 a_i = i인 정점의 경우 위 연산을 할 필요가 없으므로 c_i = 0으로 생각해도 좋다. 모든 (i, a_i) 쌍에 대해 저 조건이 둘 중 하나에 대해 성립해야 하므로, Functional Graph에서..
QOJ 탐방을 하던 중 처음 보는 셋이 꽤나 많다는 것을 알게 되었다. 처음 보는 셋들을 풀어 보고 더 풀어볼 가치가 있는 좋은 셋들을 찾아보기로 했다. 첫 번째로 시도해본 것은 PAIO 2025 Day 1이다. (Pan African Informatics Olympiad) solved.ac 티어 같은 게 없으므로, 아무런 사전 정보 없이 셋을 보게 되었다. 난이도순인지 아닌지도 모른다.A. Cards문제를 보자마자 케이스워크가 심한 문제임을 알 수 있었다. 여러 극단 케이스들을 시도해 본 후 규칙을 찍어서 맞았다. 예상 난이도는 S2 정도.#include "cards.h"#include using namespace std;typedef long long ll;ll maximum_score(int _X,..
현재 33문제가 남아 있다. 남아 있는 문제들의 난이도 분포는 다음과 같다.언레(UR) 5문제다이아 8문제: 다4 2문제 / 다3 3문제 / 다2 1문제 / 다1 2문제루비 20문제: 루5 8문제 / 루4 5문제 / 루3 4문제 / 루2 1문제 / 루1 2문제남은 문제: 33 → 30문제 참고로 이 글이 BOJ 서비스 종료 전에 문제를 푼 마지막 과거 청산 챌린지 글이다.BOJ 22491. Repairing풀이 자체는 굉장히 자명한 편에 속한다. 주어진 점들과 파이프의 교점들로 그래프를 따고, 망가진 점에서 시작해 dfs를 돌리며 가장 가까운 밸브들을 잠근 뒤, source에서 시작해 물이 얼마나 차는지를 보면 된다. 다만 구현이 상당히 귀찮고, 실수 오차/오버플로우 문제도 있어 __int128을 이용한..
현재 38문제가 남아 있다. 남아 있는 문제들의 난이도 분포는 다음과 같다.언레(UR) 9문제다이아 9문제: 다4 2문제 / 다3 3문제 / 다2 2문제 / 다1 2문제루비 20문제: 루5 8문제 / 루4 5문제 / 루3 4문제 / 루2 1문제 / 루1 2문제이제부터는 그냥 풀고 싶은 문제를 아무거나 잡아서 풀려고 한다. 남은 문제: 38 → 33문제BOJ 21227. Minimizing Edges처음에는 굉장히 막막해 보였는데 몇 가지 관찰을 하고 나니 할 만해 보였다. 일단 각 정점별로 중요한 건 짝수 최단 거리 $e_i$와 음수 최단 거리 $o_i$ 두 개만을 맞추면 된다. 어차피 거리를 $2$씩 늘리는 건 간선 하나를 양방향으로 왔다갔다 하면 되기 때문이다. 따라서 $G$와 $e_i, o_i$ 값..
이제 남은 문제는 42문제이다. 다2 문제도 두 개만 남은 상황이다. 다4-다2 구간 문제는 7개가 남아 있으므로, 이쯤에서 다1도 scope에 넣기로 했다. 다1 문제는 총 5개가 있어서, 다4-다1 구간의 남은 문제는 12개이다. 이 시점에서 남은 문제들에 대해 간단히 아는 대로 써 보면,34167: 정해 오류가 있다는 소문을 들은 matkor 문제이다. 문제 오류가 있는 만큼 우선순위가 밀렸고, 앞으로도 꽤나 밀릴 것 같다.34211: IOI practice에 나온 constructive 문제다. 관련 논문을 찾아보고 열심히 규칙을 찾아 $L = 83$인 해까지는 찾았으나 $L = 84$인 해를 찾는 방법을 전혀 모르겠다.8242: 지능이 필요한 문제 같은데 잘 모르겠다. 에디토리얼도 없다.3337..
solved.ac 여덟 개의 문 이벤트를 진행하다가 풀게 된 문제이다. 이 문제는 8가지 기본 태그 중 수학/구현/DP/자료구조/그래프/문자의 6가지 태그가 달린 문제로, 6개 이상의 기본 태그가 달린 문제는 이 문제가 유일하다. (python으로 API를 이용해 확인했는데, 구현이 틀렸을 수도 있다.)접근 방식5개의 문제가 있으며, 4개의 서브태스크가 있다. 각 서브태스크는 각 문제에서 해당 서브태스크를 맞으면 된다. 아무래도 한 부분에서 틀리면 어디서 틀린지 알 수 없으니 굉장히 귀찮다고 할 수 있다. 어떤 전략을 택하기 위해서는 일단 문제를 모두 읽을 필요가 있었다. 일단 풀이를 내는 게 별로 어렵지 않으면 먼저 풀이를 생각해 보기로 했는데, 이렇게 해야 더 좋은 접근 방식을 찾을 수 있을 것 같았..