본문 바로가기

전체 글

The 2026 ICPC North America Championship (팀연습) 실버(E) 골드(I) 플4(H) 플2(A)를 풀었고, 플3 3문제(F,K,M)을 못 풀었다. 시간이 좀 지났고 버추얼때도 정신없었어서 선후관계가 잘 생각이 안 난다.처음에는 내가 ABCD, arpia형이 EFGH, alreadysolved형이 IJKL을 잡았다.arpia형이 E를 빠르게 밀었다.A는 잘 모르겠어서 넘겼고, B가 뭔가 만만한 관상이라고 생각해서 좀 생각했는데 아무 생각이 안 났다. I가 풀린다고 해서 문제를 받았는데 독해가 안 됐고, 해석을 들었는데도 아무 생각이 안 났다. 나는 F를 받아서 생각해보고 있었고, alreadysolved형이 I를 풀어왔다. 이때쯤 arpia형은 A와 D 정도를 보고 있었던 것 같고, 나는 J와 K와 M 등을 좀 봤다. K는 관상만 빡세고 그냥 적당히 슥슥 하.. 더보기
2026 SCSC Div.2 후기 SCSC Div.2에 "상등병의편지" 닉네임으로 참가했다. 후기를 미루고 있었는데 이벤트를 한다길래 겸사겸사 작성한다. 대회 전 대 - 철민이형이 알로하팟에게 맛있는 점심을 사주셨다. 서울대는 처음 가 봤는데, 건물도 다 이쁘고 교정이 시원시원해서 부러웠다.대회장에 와서야 필기구를 하나도 안 가져왔다는 걸 알았다. 다행히 제인스트리트 공책과 펜이 아주 편했다. A번이 가장 쉽다길래 먼저 읽었는데, 아무 생각도 안 들어서 잠깐 멍을 때렸다. 다시 읽어 보니 w=1 조건이 보여서 바로 짜서 맞았다. 풀린 문제가 없으니 일단 번호 순으로 문제를 읽었다. B는 아무 생각이 안 들어서 C로 넘어갔다. C는 prefix = suffix인 최대 길이를 찾으면 되는 문제였다. 빠르게 해싱을 짰고, 말도안되는구현실.. 더보기
ABC #448 (Virtual) 1800 후반대 퍼포가 나왔다. 요즘 웬만하면 블루 퍼포는 뜨는 것 같다. 오늘은 못 띄울 뻔 했는데 턱걸이로 F를 풀었다. A,B :브론즈구현C :무지성 multisetD :dfs하며 조상에 A 중복이 있는지 여부 관리E :M 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include bits/stdc++.h>using namespace std;using ll = long long; struct Mod { int m, tail_one, cycle_one, tail_ten, cycle_ten; ve.. 더보기
2024 ICPC Seoul Regional 풀어보기 https://www.acmicpc.net/category/detail/4348 260412 시작기한: 2주 (BOJ 연습최대기간)목표: 10솔 (1등팀 솔브수)서울 리저널에서는 24년부터 풀이 스케치를 제공한다. 참고할 예정http://static.icpckorea.net/2024/regional/writeups.pdf 최종결산 - 10솔 0412본 대회 때 풀었던 A, B, J, L을 밀었다. 별로 오래되지 않아서인지 대강 풀이의 결이 기억나서 편하게 밀었다. 다 미는 데 두 시간 안쪽으로 걸린 것 같다.A는 뻔한 걸그냥 하면 된다. 대회 때도 시작 어리버리만 좀 타다 풀었던 것 같다.B는 지금 보니 뻔한 그래프 모델링에 뻔한 유형이다. 각 간선이 양쪽 중 하나의 정점을 겹치지 않게 고르는 상황일 때.. 더보기
백준 13513 트리와 쿼리 4 문제: 트리에서 두 쿼리 해결하기- 1 i: i번 정점의 색을 바꾼다. (흰색 -> 검정색, 검정색 -> 흰색)- 2: 모든 흰색 정점 a와 b에 대해서, 가장 먼 거리를 출력한다. 이때, a와 b는 같아도 된다. 만약, 흰색 정점이 없다면 -1을 출력한다.정점 N BOJ는 사라져도 solved.ac는 당분간 있다고 하니 마지막 랭작을 위해 센트로이드 트리 문제를 풀었다.분할 정복과 세그먼트 트리의 관계처럼 센트로이드 트리는 센트로이드 분할 과정을 저장하는 구조라는 점을 생각하면서 풀자. 가장 먼 거리이기도 하고, 간선 가중치도 음수가 될 수 있다. 센트로이드 분할로 문제를 푼다면 해당 센트로이드를 지나는 모든 정점 쌍을 처리하기 위해 센트로이드로부터의 거리를 저장한 뒤 가장 큰 거 두 개 뽑는 식으로 .. 더보기
조명등(2020 KOI 1차 고등부 3) https://assets.koi.or.kr/koi/2020/1/problems/h2-problems.pdf CHT인 걸 알고 풀어서 풀이가 빨리 나왔다. 큐에 한참 담아두다 BOJ 문 닫기 전에 짰다. 먼가 dp[i] := 1..i까지 다 비추도록 설치하는 최소 비용같이 DP를 돌리고 싶다. 이렇게 정의된 dp[i]를 계산하려면 i와 함께 하나의 삼각형으로 덮을 범위 j를 모두 확인하면 된다. [j, i]까지 구간을 하나의 삼각형으로 덮는 비용은 [j,i] 구간에 있는 a,b에 대해 (max(x[a]+h[a]) - min(x[b]-h[b])) ^ 2 / 4이다. max / min이 들어가 식 정리가 안 되니 제거할 방법을 생각해 보자. x가 증가하는 순서대로 x+H, x-H가 모두 순증가하도록 원소를.. 더보기
3-cycle, 4-cycle k-cycle은 길이가 k인 단순 사이클을 의미한다. 무향 단순 그래프에서 3-cycle, 4-cycle의 개수를 $O(E \sqrt{E})$에 셀 수 있으며, 구현도 간단하다. 관련하여 공부한 내용을 정리한다. 다음 글을 많이 참고했다. https://infossm.github.io/blog/2025/07/28/subgraph-counting/위 글의 내용을 쉽게 다시 쓰는 글이 될 예정이다. 3-cycle, 4-cycle 모두 원래 그래프의 모든 간선에 방향을 부여하여 만든 방향 그래프를 활용한다. 원래 그래프를 G라고 할 때, G에 속한 각 간선 e = {u, v}에 대해 u, v 중 차수가 작은 정점에서 큰 정점 쪽으로 방향을 부여한다. 차수가 같다면 정점 번호를 기준으로 한다. 즉, G에서 .. 더보기
CF #1086 (Div.2, Virtual) https://codeforces.com/contest/2208 D2를 풀어야 퍼플렌지퍼포가 나오는데, 좀 어려웠다. A. Bingo Candies가장 많은 수의 개수가 N(N-1)개 이하면 대각선만 비우고 채우는 식으로 항상 가능하다. A라 엄밀하게는 생각 안 해봤는데 안 될 수가 없다. N(N-1)개 이상이면 자명히 불가능하다. 생각을 이상하게 해서 상한을 잘못 구한 덕에 3틀을 박았다. 이거아니면 퍼플퍼포먼스나왔을지도더보기1234567891011121314151617181920212223242526#include bits/stdc++.h>using namespace std;using ll = long long; void solve() { int N; cin >> N; mapint.. 더보기

티스토리툴바