다이아 2 초반은 나름 순조로웠다. 하지만 뒤로 갈수록 남은 문제들이 심상치 않아졌다. 현재 다4-다2권에는 15문제가 남아 있다. 남은 문제: 50 → 46문제BOJ 27355. PathsTL이 0.3초라는 게 특이할 만한 문제이다. 문제 풀이 자체는 꽤나 자명한 편이다. 플로우 모델링 비슷한 걸 해 보면 결국 계속 등장하는 볼록성 있는 그리디라는 것을 알 수 있다. 그래서 루트가 고정되어 있다면 그리디하게 가장 긴 경로를 뽑는 것을 반복해 풀 수 있다. 여기까지만 알아도 마지막 섭테 제외하고 전부 어렵지 않게 풀 수 있다. 문제는 마지막 서브태스크이다. 일단 TL이 다른 문제처럼 정상적인 범주 (2초 정도) 에 있다고 가정하고 풀어 보자. 루트 하나에 대해서 dp의 형태로 답을 구하려면 가장 쉽게 생..
이제 55문제가 남았고, 다4/다3 문제는 9개가 남았다. 다4/다3권의 남은 문제들은 조금 짜기 귀찮거나 상수가 애매한 문제들이 많아서, 다2도 scope에 추가하기로 했다. 다4/다3/다2는 총 20문제가 남아 있는 상태다. 20문제 중에서는 그래도 쉽게 업솔빙할 수 있는 문제가 있었으면 좋겠다. 캡처를 할 당시 solved.ac가 먹통이라, 백준 스크린샷으로 대체한다. 다이아2 문제들은 이름이 기억나는 것들이 많다. 좋은 문제라고 기억하는 것들도 조금 있다. Star Trek 같은 문제는 좋긴 한데 ML이 256MB였던가 하는 문제로 업솔빙을 안 했던 것 같다. 구데기컵 문제도 보인다 (24906). OI 문제들이 많은 것 같은데, 대부분의 OI 문제들은 퀄리티 보장이 어느 정도 되기 때문에 다행..
KCPC가 모든 문제를 다 풀면 배경을 준다는 소식을 들어서, 실제로 해 보기로 했다.아마 이 시리즈 역사상 가장 많은 문제가 등장할 것 같다. 문제들은 푼 순서대로 작성했다.1A/2A. NEMODEMIC그냥 구현하면 된다.#include using namespace std;typedef long long ll;int n, m;char board[55][55];int main(){ #ifndef LOCAL ios::sync_with_stdio(false); cin.tie(NULL); #endif cin >> n >> m; for(int i=1; i> board[i]+1; int wall = 0; int one_virus = 0; int all_virus =..
슬슬 문제를 푸는 것이 귀찮아지고 있다. D4-D3권에서 남은 문제들을 푸는 것이 쉽지 않아 보인다. 그래도 아직 문제가 꽤 남았으니 이 부분에서 조금 더 풀어 볼 생각이다. 뭔가 문제를 푼 사람이 많을수록 더 풀기 쉬울 것 같으니, 이번에는 푼 사람 순서대로 정렬을 해 봤다. 남은 문제: 60 → 55문제BOJ 20558. 쿼리와 수열$K_i$의 합을 $K$라고 쓰자. 다음과 같이 상태가 $O(NK)$개인 DP를 만드는 것은 쉽다.$DP[i][j][v]$: 구간 $(i, j)$에서 최댓값이 $v$인 경우 답의 최댓값이때 $(i, v)$ 또는 $(j, v)$의 쌍이 $K$개 이하이므로 전체 $(i, j, k)$의 쌍이 $O(NK)$개 이하가 된다. 다만 저렇게 하면 transition의 가짓수가 $K$개..
이제 D4가 너무 적게 (3문제, 문제 오류 제외하면 2문제) 남은 관계로 D3도 scope에 포함시키기로 했다. 현재 D4+D3은 18문제가 남아 있다. 기술적인 문제로 인해 한 문제 (9467)는 캡처에서는 빠져 있다. 새로 추가된 다이아 3 문제에 대한 인상은 다음과 같다. 제목과 기억에만 의존한 내용이다.누가 봐도 Matkor 컵인 문제가 하나 보인다. 얘는 좀 미뤄두는 게 정신건강에 좋을 것 같다.구데기컵 문제도 하나 보이는데, 얘도 미뤄두는 게 정신건강에 좋을 것 같다.마지막 문제인 레이저는 매우 최근 대회에서 시간이 부족해 디버깅을 하지 못한 문제이다. 풀이를 알기 때문에 크게 어렵지 않게 풀 수 있을 거라고 기대한다.수쿼 문제 비슷한 게 보이는데, 얘도 수쿼과라면 빠르게 풀 수 있을 거라..
지난번에 이어 다이아 4를 계속 풀고 있다. 남은 문제들이 대부분 풀기 싫게 생겼지만, 이런 문제들을 푸는 연습도 중요한 것 같다. 남은 문제: 69 → 65문제BOJ 8310. Riddle간단한 2SAT 문제이지만 문제에 등장하는 그래프의 크기가 너무 크다는 게 문제다. atcoder의 SCC 라이브러리를 이용해 짜니 2초 정도에 통과했다.#include #include using namespace std;using namespace atcoder;typedef long long ll;int n, m, k;vector county[1'000'005];int where[1'000'005];int idx[1'000'005], ord[1'000'005];int sccNum[4'000'005];int ans[..
요즘 백준에서 과거에 틀린 문제를 다시 푸는 챌린지를 하고 있다. 시작했을 때는 약 180개 가량의 문제가 있었다. 이 글을 쓰기 시작하는 시점으로 74개의 문제가 남아 있고, 다이아 5 이하의 문제는 전부 업솔빙을 완료했다. (Unrated 제외) 다이아 4부터는 문제들이 쉽지 않은 관계로 블로그 글을 쓰면서 배운 점들을 정리해 볼 생각이다. 현재 수준에서는 글마다 3~6개 내외의 문제들이 올라갈 것 같은데, 나중에 문제들이 어려워진다면 이 수가 조정될 수 있다. 당분간의 목표는 아래 d4 문제들을 전부 푸는 것이다. 남은 문제: 74 → 69문제 문제 리스트만 놓고 봤을 때 최악은 아니었지만 (D5에서는 실수 오차 문제 등 풀기 싫은 문제들이 많았다), 34167의 정해가 잘못되었다는 걸 들은 기억이..
문제문제를 트리와 쿼리 형태로 생각하면 다음과 같다.초기에, 트리의 각 점에 $K_i$가 쓰여 있다.Relocation: 모든 depth $X_i$ 정점 $v$에 대해, 해당 정점의 $Y_i$ 깊이 조상이 $w$라면 $K_w$에 $K_v$를 더하고, $K_v$를 $0$으로 만든다.Immigration: $K_{A_j}$에 $L_j$를 더한다.Survey: $K_{B_j}$를 출력한다.풀이Subtask 1 (4점)트리가 스타 그래프 형태이므로, 문제가 매우 쉽다. Relocation은 그냥 모든 $K_i$를 루트로 모으는 것과 같고, Immigration과 Survey도 쉽다.Subtask 2 (12점)나이브 $O(NQ)$를 짜면 통과한다.Subtask 3 (25점)모든 정점의 깊이가 $20$ 이하라는 조..