본문 바로가기

전체 글

(87)
Educational Codeforces Round 116 (Div. 2) Dashboard - Educational Codeforces Round 116 (Rated for Div. 2) - Codeforces codeforces.com 3주 만의 코포 복귀 & 3달 만의 퍼플 복귀 & 10달 만의 +100 이건 아니었다 시간이 맞지 않아 3주 동안이나 코포를 못하고 있었고 이날도 분명 힘들거라 생각했었다. 그런데 버스 기사님이 무리를 하셨는지, 도착 예정 시간이 아슬아슬하게 들어와서 지하철 안에서 노트북 세팅을 끝내 놓고 집으로 뛰어들어왔다. 이때가 대충 33분. 손만 대충 씻고 코포에 빠르게 접속하니 대회가 바로 시작... 그래서 외출 상태 그대로 코포를 쳤고, 결과는 성공적이었다. Prob. A ab, ba의 개수는 a, b 묶음이 몇 번 변하는지에 영향을 받는데, 대충..
[BOJ 1167] 트리의 지름 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 널리(?) 알려진 것과 달리 dfs 한 번으로 해결할 수 있다. 사실 그 방법을 몰라서 이렇게 풀었다. 풀이 임의의 루트를 하나 잡고 트리를 구축했다고 생각하자. 트리의 지름을 만드는 두 노드의 공통 조상은 트리 위의 노드 중 하나이기 때문에, 모든 노드에 대하여 그 노드를 공통 조상으로 하는 두 노드의 최대 거리를 시도해보면 된다. 이를 위해 필요한 정보는 각 서브 트리의 최대 깊이와 여러 서브 트리 중 첫 번째와 두 번째로 깊은 깊이이고, 이..
[BOJ 12784] 인하니카 공화국 12784번: 인하니카 공화국 인하니카 공화국은 1번~ N번까지 N개의 섬으로 이루어진 나라이다. 이 나라에서는 섬 간의 왕래가 매우 어려웠지만, 위대한 다리 설계자 ‘진’이 두 섬을 연결하는 다리를 최소한의 개수로 만들 www.acmicpc.net 이 문제와 정확히 일치하는 문제를 GCC 출제 큐에 push하고 나서 반나절 뒤에 트리 디피 문제를 찾아 풀다가 우연히 발견했다. AC를 받기 전까지 제발 내 착각이기를 빌었다.. 흔한 유형이라 비슷한 문제가 있을 거라고 생각하기는 했지만, 아쉬운 것은 어쩔 수가 없다. 풀이 루트와 리프를 연결하는 경로가 없도록 만들 때, 자르는 간선의 가중치의 합이 최소가 되게 하는 문제다. 이는 dfs를 돌면서 트리의 정점에 대한 dp를 해결하면 된다. $dp[u]=\s..
자작 문제 1. 영단어 외우기 문제 영어 단어 시험이 사흘 앞으로 다가왔다. 모두가 바쁘게 단어를 암기하고 있는 와중에 GCC 출제 아이디어를 고민하고 있는 희원이는 두 마리 토끼를 다 잡을 수 있는 묘안을 떠올렸는데, 그것은 바로 영단어를 숫자로 바꿔서 암기하는 것이었다..! a, b, c, ... , z 를 각각 0, 1, 2, ..., 25 에 대응시켜 26진법인 영단어를 10진법의 수로 변환하여 외우고 시험을 볼 때 10진법의 수를 영단어로 다시 변환할 수만 있다면, 수행평가 만점은 따놓은 당상이나 마찬가지다. 영단어 또는 변환된 수와 영단어의 길이가 주어질 때, 이를 변환하거나 다시 영단어로 만들어 희원이의 수행평가를 도와주자! 입력 첫째 줄에 길이가 23 이하이고 소문자 알파벳으로만 이루어진 영단어, 또..
[BOJ 16998] It’s a Mod, Mod, Mod, Mod World 16998번: It’s a Mod, Mod, Mod, Mod World You are given multiple problems with three integers p, q, and n. Find \(\displaystyle\sum_{i=1}^{n}{((p \cdot i) \text{ mod } q)}\). That is, the first n multiples of p, modulo q, summed. Note that the overall sum has no modulus. www.acmicpc.net 풀이가 적혀있던 노트를 겨우 찾아서 포스팅한다. ㅎㅎ ㅠ 풀이 $x\%m=x-(x/m)*m$ 임을 이용해 주어진 식을 변형하면 $ans=\frac{n(n+1)}{2}p-q\sum_{i=1}^{n}\le..