$$\newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\N}{\mathbb{N}}\newcommand{\C}{\mathbb{C}} \newcommand{\oiv}[1]{\left] #1 \right[} \newcommand{\civ}[1]{\left[ #1 \right]} \newcommand{\ad}[1]{\text{ad}(#1)} \newcommand{\acc}[1]{\text{acc}(#1)} \newcommand{\Setcond}[2]{ \left\{\, #1 \mid #2 \, \right\}} \newcommand{\Set}[1]{ \left\{ #1 \right\}} \newcommand{\abs}[1]{ \left\lvert #1 \right\rvert}\newcommand{\norm}[1]{ \left\| #1 \right\|}\newcommand{\prt}{\mathcal{P}}\newcommand{\st}{\text{ such that }}\newcommand{\for}{\text{ for }} \newcommand{\cl}[1]{\text{cl}(#1)}\newcommand{\oiv}[1]{\left] #1 \right[}\newcommand{\interior}[1]{\text{int}(#1)}$$

본문 바로가기

전체 글

(113)
4월 1, 2주차 PS 정리 왤케 요새 안하지.... 딱히 할 시간이 없냐면 그건 또 아니다. (주로 롤토체스에 빠져 살고 있다) 5문제. 난이도 순 (아마도) 그나마 SNUPS Red Army를 시작해서 문제풀 동기가 조금 더 생겼다. Red Army는 작년에 TAMREF님이 개설한 스터디를 올해 내가 이어서 하고 있는데, Codeforces 기준 블루~오렌지 정도 실력을 가진 사람들이 조금 어려운 문제 (2000+) 를 일주일동안 몇개 풀고 디스커션을 하는, 스터디 그룹 같은 느낌이다. 다음주에는 Red Army 2주차를 최대한 풀고 풀이를 작성하는걸 목표로 하고 있다 (2주차부터는 이상한 사람들의 영향으로 2600, 2800 문제가 들어가 있기 때문에 다 풀긴 조금 무리가 있다) Codeforces Round 635 (Div1..
3월 3, 4주차 PS 정리 7문제, 난이도 순. 온라인 개강이라 시간이 널널할줄 알았는데 생각보다 과제가 많아서 PS를 못 돌고 있다. BOJ 11405 책 구매하기 난이도 : Platinum 4 MCMF가 무엇이고 어떻게 구하는지 공부할 때 푸는 기본 구현 문제. 플로우 같은 고급 알고리즘을 너무 모르는 것 같아서 MCMF를 공부하고 구현을 (적당히 팀노트를 베껴 가며) 해봤다. 아직 응용해서 MCMF 문제를 모델링해서 풀기에는 갈길이 먼것 같다. 팀노트에 넣어놓은 MCMF가 잘 도는지 확인하는 문제라고 할 수 있겠다. Atcoder Beginner Contest 160F, Distributing Integers Atcoder 난이도 1962 대략적으로 문제를 설명하자면, 정점 1부터 $N$까지로 구성된 트리에서, $x$ 번을 ..
BOJ 10847, APIO 2015 2 - Jakarta Skyscraper 출처 : 2015 Asia-Pacific Informatics Olympiad Problem 2 백준 번역명 "자카르타의 마천루" 난이도 : Diamond 3 1. 문제 설명 0번부터 $m-1$ 번까지의 번호를 가진 "도게" 가 있고, 이 도게들은 1 시간 만에 $+p$ 또는 $-p$ 만큼씩 점프할 수 있다. 도게끼리 만나면 소식을 전달할 수 있고, 소식을 이미 전달받은 도게만 움직일 수 있다. 1번 도게가 소식을 전달받는 최단 시간을 찾는 문제. 2. 풀이 설명 [36점, 57점 풀이 : Dijkstra] 최단 시간 (가중치가 주어질 때, 최단 경로)를 찾는 문제이고, 음수 간선이 없으며, $n \leq 30,000$개의 빌딩을 오가야 한다는 점에서 다익스트라 알고리즘을 이용해 보자는 생각을 할 수 있..
Codeforces Round #627 (Div. 3) 후기 + 풀이 Div3지만 코포에서 라운드 시간 중에 올솔브 성공한건 처음인것 같다. :dhk: A. Yet Another Tetris Problem $2 \times 1$ 블록을 아무리 세워도 각 열의 홀짝성을 바꿀 수 없다. 반대로, 홀짝성이 같다면 높이 쌓는것에는 문제가 없으므로 엄청 높이 쌓으면 전부 지울 수 있다. 따라서, 홀수와 짝수 중 한종류만 있으면 YES, 아니면 NO. B. Yet Another Palindrome Problem 길이가 3 이상인 Palindromic subsequence 가 있는지 확인하는 문제. Substring이 아닌 Subsequence이므로, - 어떤 수 $x$ 가 두번 이상 나오고, - 그 수가 나오는 최소 위치와 최대 위치가 두칸 이상 떨어져 있다면 (즉, $xx$가 아닌..
3월 2주차 PS 정리 7문제, 대략적인 난이도 순. solved ac에 등록된 백준 문제들은 그 티어 순이고, Codeforces 문제는 대충 체감 난이도대로 넣었다. 체감 난이도다 보니 내가 잘 못푸는 스타일의 문제 난이도가 높게 평가되는것 같다. BOJ 04225, ICPC World Final 2011 K - Trash Removal 백준 번역명 "쓰레기 슈트" 난이도 : Platinum 3 다각형이 통과할 수 있는 가장 좁은 폭을 구하는 문제. 기하적인 관찰을 통해, 두 점 $A_i$ 와 $A_j$ 를 잡고 그 둘을 잇는 직선에 평행하게 들어가는 경우가 최선임을 알 수 있다. 즉, 그 직선에 수직인 직선 $L$을 잡고, $L$에 다각형의 모든 점을 정사영했을 때 가장 멀어지는 길이를 찾으면 된다. 예를 들어 y축에 평..
3월 1주차 PS 정리 어쩌다 보니 개강이 미뤄져서(?) 더 생긴 방학 기간에는 아마 1주일에 한번, 학기중에는 2주? 시험기간에는 한달정도 간격으로 푼 문제들에 대한 정리를 업로드 해보려고 한다. 한문제씩 쓰기는 좀 작은 문제들도 적을 수 있고... 여전히 한문제 한문제가 어려운 경우에는 별도 포스팅하고 링크만 찍을 예정. 기본적으로 풀이를 서술할 거기 때문에, Spoiler Alert는 뭔가 풀이가 좀 김새는 경우(?) 거나, 그런 것만 추가로 달았다. 어차피 포스팅 전체가 문제 풀이의 스포일러기 때문에..ㅋㅋㅋ 10문제, 대충 SAC 난이도 순으로 정렬했다. BOJ 11620, CERC 2015 H Hovering Hornet 난이도 : Platinum 4 보이는 주사위 눈 수의 기댓값은, 눈이 $k$개인 면을 볼 수 있..
BOJ 15310 아티스트 출처 : 경기과학고 나는 코더다 2017 송년대회 F번 난이도 : Solved AC 기준 Diamond II 내가 왜 이걸 이렇게 풀었지... 이 모든게 해시코드 후유증이다. :blobcry: 1. 문제 설명 문제의 지문 자체는 별로 길지 않지만, 요약하면 다음과 같다. $(w_i, h_i)$ 의 정보를 갖는 '그림' 이 $n$ 개 주어진다. 이 '그림' 들 중 $k$ 개를 고를 것이다. 고른 그림들을 $1, 2, \dots k$ 번이라고 할 때, $$\left(\sum_{i = 1}^{k} w_i \right) \left(\sum_{i = 1}^{k} h_i \right)$$ 이 값을 최대한 Minimize하고 싶다. 2. 풀이 먼저, 생각해 보면 총 $\binom{n}{k}$ 개의 가능한 그림 조합들..
BOJ 13558 등차수열의 개수 난이도 : ??? 이 문제 같은 경우에는, 굉장히 어려운 (그리고 재밌는) 정해와, 그럼에도 불구하고 솔브드 난이도가 골드 3이 되어버린 이상한 스토리가 있다. 그래서 난이도는 ??? 인데, 정해를 기준으로 생각한다면 최소 다이아 급의 문제이고, 그냥 뚫을 생각이라면 골드5? 골드5정도면 충분한것 같다. 1. 문제 설명 길이가 $N$ 인 수열 $A_1, \dots A_n$ 에 대하여, $A_i, A_j, A_k$ 가 등차수열이 되는 $(i, j, k)$ (순서 지켜야 한다) 순서쌍의 개수를 찾는 문제이다. 수열의 길이는 10만, 각 수는 3만 이하. 2. 풀이 2-1. Multiset에 대해 생각하기 먼저, 이 문제가 왜 망했는지(...) 의 이야기를 하기 전에, 복잡도가 실제로 낮은 풀이에 대해 생각해..