$$\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)}$$

본문 바로가기

전체 글

(110)
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에 대해 생각하기 먼저, 이 문제가 왜 망했는지(...) 의 이야기를 하기 전에, 복잡도가 실제로 낮은 풀이에 대해 생각해..
FFT (Fast Fourier Transform) 와 실수오차 FFT (Fast Fourier Transform) 은 기본적으로, 다항식의 계수 표현 (Coefficient form. 정식 용어는 아닌거 같지만 어디선가 본 말이다) 과 점 표현 (Point-value form) 을 오가는 알고리즘이다. FFT를 이용하면, 두 다항식의 곱을 $O(n \log n)$ 에 계산하는 등 일반적으로는 할 수 없는 연산들을 빠르게 수행할 수 있기 때문에 다양한 용도로 사용할 수 있고, PS에서는 나름 고인물 알고리즘의 시작(?) 같은 느낌으로 생각되는 것 같다. ICPC Regional에도 가끔 나오는 것 같고...물론 요즘같이 다들 고여버린 때는 별로 의미가 없지만 ㅋㅋㅋ FFT가 왜 작동하는지, 어떻게 작동하는지, 어떤 일들을 할 수 있는지는 다양한 자료를 통해 공부할 수..
Google Hash Code 2020 후기 Google Hash Code 2020 (https://codingcompetitions.withgoogle.com/hashcode) 후기. ICPC 같이 뛰었던 팀 Little-Piplup에 현재 병특 중인 dlwocks31을 영입(?) 해서 4인팀인데, Dlwocks31이 3명보다 구현이 훨씬 좋아서 확실히 팀 전력이 보강된 느낌이 들었다. 4인 팀으로 ICPC 같은걸 뛰었으면 더 잘 했을것 같기도... Team Little Piplup : Coffeetea Diordhd Dlwocks31 Gratus907 Hash code는 일반적인 ICPC / OI 류 대회와는 다르게, NP 문제 같은 뭔가를 가지고 최대한 많은 점수를 긁는 방식으로 치뤄지는 대회이다. 유사한 걸로는 Marathon Match 같..
Codeforces Round #620 (Div. 2) 후기 + 풀이 오렌지 찍었다 :dhk: 한국인 세터 라운드라서 시간도 좋은 것 같아서, 오렌지까지 1점 남았지만 그냥 Div2 뛰기로 했다. A. Two rabbits 두 토끼 사이의 거리 $d$가 $a+b$ 로 나누어 떨어지는지 확인하고, 되면 몫을 출력, 아니면 -1. 더보기 #include #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #define ll long long #define eps 1e-7 #define all(x) ((x).begin()),((x).end()) #define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); usin..