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

본문 바로가기

전체 글

(112)
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..
Codeforces Round #618 (Div. 1) 후기 + 풀이 Predictor에 +116이라고 뜨는 것과는 달리, 실제로는 +115를 받아서 2099점이 되었다. 오렌지 갔나 했는데, :blobsad: ㅠㅠ 라운드는 굉장히 재밌게 했던것 같다. A. Anu has a function 수열 $a_1, a_2, a_3 \dots a_n$ 과 함수 $f(x, y) = (x | y) - y$ 이 주어질 때, 이들을 적당히 재배열해서 $$f(f(\dots f(f(a_1, a_2), a_3), \dots a_{n-1}), a_n)$$ 의 값을 최대화하는 문제. 잘 생각해 보면, $f(x, y)$ 는 $x$의 On bit 들을 모은 집합에서 $y$의 On bit 들을 모은 집합의 차집합을 반환한다는 사실을 알 수 있다. 즉, 최대한 '가치' 가 높은 비트(큰 비트) 들을 살리..
Codeforces Round 601 + 616 (Practice) dlwocks31 이랑 코드포스 Division 1 라운드 두개를 붙여서 같이 연습을 돌았다. Division 2는 A/B를 푸는게 실제로는 별로 의미가 없고, Div2 F는 못 풀 가능성이 높으니 실제로는 풀 만한 문제가 3개밖에 없어서 2시간 반을 잡고 Div1 두 라운드의 ABC 세문제씩만 뽑았다. Round 616 Problem A. Mind Control 사람들이 줄을 서 있고, 어떤 배열의 맨 앞과 맨 뒤 중 하나를 골라서 뽑아 올 수 있다. 이때 $m$ 번째에 서서 최대한 큰 수를 가져가고 싶은데, 앞에 있는 $m-1$ 명 중 $k$ 명의 선택을 강제할 수 있다. 나머지 $m-k-1$ 명은 어떤 선택을 할 지 알 수 없지만 내가 최대한 손해를 보는 상황이 되었을 때 얻는 값을 찾는 문제. 생..
BOJ 14347 / 14346 Radioactive Islands 난이도 : Solved AC 기준 루비 3 (Large), 루비 5 (Small) 출처 : Google CodeJam World Final 2016 내가 백준에 제출한 문제중에 가장 어려웠던 것 같다. 미적분학 II 책을 끼고 열심히 띵킹해서 풀었는데, 푸는 과정에서 잠시 백준 채점 서버가 멈추고 (내 코드가 5분 동안 돌아서 그런게 아닐까 싶은 정황이 있고, 완전히 그것때문은 아니라도 상당부분 기여한건 맞는거 같다. :cry:) 여러 일이 있었지만 아무튼 252초의 시간을 쓰면서 맞았다. 우웩;;; 먼저 14346 Small을 기준으로 풀이를 작성하고, 14347을 위해 필요한 관찰만 더 소개하는 것으로 하자. 1. 문제 설명 $(-10, a)$ 에서 보트가 출발하고, 목적지 $(10, b)$ 로 가려..
BOJ 16709 Congruence Equation 난이도 : Solved.ac 기준 다이아 3 출처 : 경기과학고 2018 송년대회 C번 1. 문제 설명 $10^{15}$ 정도의 큰 소수 $p$ 가 주어지고, $a^b \equiv b^a (\mod p)$ 를 만족하는 자연수 $1 \leq a, b \leq p(p-1)$ 순서쌍 $(a, b)$ 의 개수를 구하는 문제. 2. 풀이 풀이의 수식 전개 과정이 상당히 복잡하고 요구하는 지식의 허들이 높은 대신, 코딩이 상대적으로 쉽다. 종이에 엄청 써 보고 나면 컴퓨터 잡고 나서는 금방 풀 수 있는 문제. 먼저, $a$ 와 $b$ 가 모두 $p$ 의 배수인 경우에는, $a^b$ 와 $b^a$ 가 모두 $\mod p$ 에 대해서 0이 되므로 주어진 조건을 만족한다. 이러한 경우는 주어진 범위 안에 $(p-1)^2..
BOJ 12728 n제곱 계산 / 12925 Numbers 난이도 : Solved ac 기준 다이아 5 (개인적으로는 플 1 정도라고 생각한다.) 출처 : Google Code Jam 2008 Round 1A, C번 두 문제는 완전히 같은 문제로, 잘 모르지만 과거 번역 과정에서 문제가 중복된 것 같은데 어째서인지 사라지지 않았다. 세부 조건 등에서도 아무런 차이가 없다. 이 문제에서 제한이 작은 small 버전은 BOJ 12727번이다. 1. 문제 설명 $(3 + \sqrt{5})^n$ 의 소수점 앞 세 자리를 계산해야 한다. 예를 들어, $(3 + \sqrt{5})^10$ 의 값은 대략 $15490047.9323...$ 이므로 047을 출력하면 된다. $n$이 작을 때는 직접 계산할 수 있지만, 수십억 정도의 $n$에 대한 답을 빠르고 정확하게 제시해야 한다..
해석개론 - 연습문제 1.6.7 [출처] : 김김계 해석개론 연습문제 1.6.7 문제 임의의 자연수 $n = 1, 2, \dots$ 에 대하여, $\sqrt{n-1} + \sqrt{n+1}$ 은 무리수임을 보여라. 먼저, 주어진 수 $x = \sqrt{n-1} + \sqrt{n+1}$ 에 대해, $x^2 = 2n + 2 \sqrt{n^2-1}$ 이다. 따라서, $\sqrt{n^2-1}$이 모든 자연수에 대하여 무리수임을 보이는 것으로 충분하다. (만약 $x$가 유리수라면 $x^2$ 도 유리수이고, 이때 $\sqrt{n^2-1}$ 이 무리수일 수 없으므로) 어떤 수 제곱수 $a^2$ 과 $b^2$ 에 대해 $a^2+1 = b^2$ 이면, $(b-a)(b+a) = 1$ 이어야 하고 $b>a, a, b \in \N$ 이어야 하는데 이러한 두..