rkm0959

2019/12/13 ~ 2020/03/01

• 정보처리기능사 필기 따기 (2월 중)
• Project Euler 400 문제 찍기
• 정보 겨울학교 조교 (1/6 ~ 1/17 예정)
• 블로그 관리: BOJ 문제 풀이, PE 문제 풀이
• 김동률님의 선형대수학 책 읽기 (정확하게 Exercise 4문제 못 풀었다. 이건 천천히 봐야할 듯)
• 과외 및 돈벌이 (방학 중에 계속 할 듯)
• 대장금 봉사 시간 채우기 
• Sage 간단하게 입문하기 (필요한 것 찾아서 적당히 짤 수 있을 정도로 연습 완료)

From 'Hard Normal Daddy', Warp Records (WARP50, 1997)

이게 1997년 작품이라는 게 믿기지가 않는다.

문제

스포 방지선

___________________________________________________________________________________________________________

___________________________________________________________________________________________________________

풀이

Euclidean Algorithm의 느낌으로 생각하면, \(ax+by=s\)를 만족하는 음이 아니고 서로소인 두 정수 \(x, y\)를 찾으면 된다.

(UPD: 사실 이 점을 증명하는 것도 trivial 한 것은 아니다. 머리를 좀 쓰긴 해야함) 

일반적으로 \(ax+by=s\)를 푸는 것은 Extended Euclidean Algorithm을 알면 쉽게 구현 가능하다. 

\(\text{gcd}(a, b)=1\)이 되도록 식을 reduce 시키고, 얻은 새로운 식을 \(ax+by=s\)라고 재정의하자. 

이제 \(ax+by=1\)을 만족하는 정수 \(x, y\)를 Extended Euclidean Algorithm (Modular Inverse)으로 구할 수 있다. 

위 식을 단순하게 \(s\)배 하기만 하면, \(ax+by=s\)인 정수 \(x, y\)를 하나 찾을 수 있다. 이를 \(x_0, y_0\)라 하자.

우리는 \(ax + by=s\)가 성립하면, 정수 \(k\)에 대해 \(x = x_0 + bk\), \(y = y_0 - ak\)라고 쓸 수 있음을 안다. 

이제 \(x_0, y_0\)를 적당히 이 방식대로 바꿔서, \(x_0 < b\)가 성립하도록 할 수 있다. 

다시 \(x = x_0 + bk\), \(y= y_0-ak\)로 solution set을 parametrize하자.

\(x, y \ge 0\)이어야 하니, \(k \ge 0\)인 경우만 보면 된다는 것을 알 수 있다. 

이제 목표는 \(k \ge 0\), \(x_0+bk \ge 0\), \(y_0-ak \ge 0\), \(\text{gcd}(x_0+bk, y_0-ak)=1\)인 정수 \(k\)가 존재하는지 여부다. 

꽤 어려운 문제처럼 보이지만, 알고리즘 문제를 푸는 입장에서 solution은 간단하다. 

단순히 \(k\)에 대해서 iterate 하면서, 조건을 만족하는 \(k\)가 나오면 YES를 찍고, 아니면 NO를 찍으면 된다. 

\(k \ge 0\), \(x_0+bk \ge 0\), \(y_0-ak \ge 0\)를 만족하는 정수 \(k\)의 개수는 \(10^{18}\)-scale까지 커질 수 있다는 것을 생각하자.

이 알고리즘이 시간 안에 답을 낸다는 사실은 (구현하면 0ms 뜬다) 수학적으로 전혀 자명하지 않다.

1년 반 전에 이 문제를 풀었을 때 이 점은 개인적으로 숙제로 남아 있었다.

오늘 이 풀이가 시간 안에 도는 이유를 아는 분에게 질문 받아서, 고민을 하는 시간을 가져 해답을 찾았다.

사실 이 블로그를 쓰는 이유도 풀이를 쓰는 것보단 이 해답을 기록하기 위한 것이다. 

Claim: 문제 조건에서 \(\text{gcd}(x_0+bk, y_0-ak)=1\)을 만족하는 최소의 음이 아닌 정수 \(k\)는 최대 \(2^{15}\)이다. 

이 Claim이 증명되면, 풀이가 시간 안에 도는 이유는 자명하다. 

\(k\)에 대한 iteration이 최대 \(2^{15}\)번 돌기 때문에, 코드의 시간복잡도는 대강 \(\mathcal{O}(2^{15} \log s)\) 정도가 된다.

이 정도의 시간복잡도/상수면, 코드가 0ms 안에 도는 것도 충분히 설명된다. 

Claim 증명

자연수 \(D\)가 있어, 각 \(k=0, 1, \cdots D-1\)에 대해 \(\text{gcd}(x_0+bk, y_0-ak) \neq 1\)이라 하자.

최대공약수가 \(1\)이 아니라는 것은 공통 소인수가 있다는 것이다. 

그러니 각 \(k=0, 1, \cdots , D-1\)에 대해 \(x_0+bk\)와 \(y_0-ak\)의 공통 소인수를 아무거나 하나 잡아서 이를 \(p_k\)라 하자.  

우선 \(s \equiv ax_0 + by_0 \equiv a(x_0+bk)+b(y_0-ak) \equiv 0 \pmod{p_k}\)이므로, \(p_k|s\)를 얻는다.

즉, \(p_k\)로 가능한 소수의 개수는 유한하다. (특히, \(s \le 10^{18}\)이므로, 최대 15개가 존재한다)

\(P = p_i = p_j\)인 두 정수 \(0 \le i, j < D\)가 있다고 가정하자.

그러면 \(x_0 + bi \equiv x_0 + bj \equiv y_0 - ai \equiv y_0 - aj \equiv 0 \pmod{P}\)가 성립한다.

이를 정리하면, \(P|b(i-j)\), \(P|a(i-j)\)가 성립한다. \(\text{gcd}(a,b)=1\)이므로, \(i \equiv j \pmod{P}\)를 얻는다. 

이 시점에서 상황을 정리해보자. 

• \(s\)의 소인수는 최대 15개가 있다. 
• 각 \(k=0, 1, \cdots D-1\)에 대해, 소수 \(p_k\)는 \(s\)의 소인수다.
• \(s\)의 각 소인수 \(P\)에 대해서, \(P = p_k\)인 index \(k\)의 수열은 공차가 \(P\)인 등차수열에 완전히 포함된다. 

이 상황을 약간 다르게 해석해보자.

• \(s\)의 각 소인수 \(P\)에 대해서, \(P = p_k\)인 index \(k\)의 수열은 공차가 \(P\)인 등차수열에 완전히 포함된다. 
• \(s\)의 각 소인수 \(P\)에 대해서, \(P = p_k\)인 index \(k\)의 수열을 포함하는 등차수열 \(\{v_P + Pn\}_{n \in \mathbb{Z}}\)를 생각하자.
• 각 소인수에 대해서 얻은 등차수열의 합집합을 생각하면, \(0, 1, \cdots , D-1\)을 전부 cover 한다.
• 즉, \(\{0, 1, 2, \cdots , D-1\} \subseteq \cup_{P|s, P \text{      is prime}} \{v_P + Pn\}_{n \in \mathbb{Z}} \)이다.

그런데, 중국인의 나머지 정리의 느낌으로 생각하면, \(\cup_{P|s, P \text{      is prime}} \{v_P + Pn\}_{n \in \mathbb{Z}} \)는 절대로 정수 집합 전체가 될 수 없다. 

이제 문제를 다음과 같은 느낌으로 바꾸어서 생각할 수 있다. 

• 정수 전체를 cover 하지는 않는 등차수열이 \(k\)개가 있다. 
• 이 등차수열들은 최대 몇 개의 연속한 자연수를 cover 할 수 있을까?

이 문제는 어느 정도 유명한 문제다. 개인적으로 아주 좋아하는 정리 중 하나를 소개한다.

Theorem: (Erdős, Crittenden, Vanden Eynden)

\(F\)는 \(k\)개의 등차수열 \(a_i + d_i \mathbb{Z}\)의 집합으로, (\(1 \le i \le k\)) \(1 < d_1 < d_2 \cdots < d_k\)다. 

만약 \(F\)가 연속한 \(2^k\)개의 정수를 cover 한다면, \(F\)는 정수 전체를 cover 하는 집합이다. 

Theorem 증명 (Taken From "Problems From The Book" pp. 152-153)

정수 \(x, x+1, \cdots x+2^k-1\)이 모두 \(F\)에 의해 cover 된다고 가정하자.

각 \(0 \le t <2^k\)에 대해서, 적당한 \(1 \le j \le k\)가 있어 \(x+t \equiv a_j \pmod{d_j}\)다. 

이를 다르게 해석하면, 각 \(0 \le t < 2^k\)에 대해서 \(\displaystyle \prod_{j=1}^k \left(1 - e^{\frac{2\pi i}{d_j} ( x+t-a_j)} \right) = 0\)라는 것이다. (동치조건이다)

이 식을 전개하면, \(\sum_{I \subset S} \alpha_I \cdot e^{(x+t) \beta_I} = 0\) 형태로 쓸 수 있음을 알 수 있다.

단, \(S = \{1, 2, \cdots k\}\)이며, \(\alpha_I\)와 \(\beta_I\)는 \(I, a_i, d_i\)에만 영향을 받는 값이다. 정확하게 말하자면, $$ \prod_{j=1}^k \left(1- e^{\frac{2\pi i}{d_j}(x+t-a_j)} \right) = \sum_{I \subset S} (-1)^{|I|} \cdot e^{-2\pi i \sum_{j \in I} a_j/d_j} \cdot e^{2\pi i (x+t) \sum_{j \in I} 1/d_j} $$이 성립한다. 이제 \(z_I = e^{\beta_I}\)라고 두면, 각 \(0 \le t < 2^k\)에 대해서 \(\sum_{I \subset S} \alpha_I z^{x+t}_I = 0\)이다. 

이제 \(u_n = \sum_{I \subset S} \alpha_I z^n_I\)라고 하자. \(u_n = 0\)인 것은, \(n\)이 \(F\)에 의해 cover 되는 것과 동치임을 정의상 알 수 있다.

식의 형태를 보면서 linear recurrence의 characteristic polynomial이 생각이 날 것이다. 

다항식 \(\displaystyle \prod_{I \subset S} (X-z_I) = X^{2^k} + A_{2^k-1} X^{2^k-1} + \cdots + A_1 X^1 + A_0\)를 생각하자.

그러면 각 \(I \subset S\)에 대해 \(z^{n+2^k}_I + A_{2^k-1} z^{n+2^k-1}_I + \cdots + A_1 z^{n+1}_I + A_0 z^n_I = 0\)이다.

이 식들을 적당히 선형결합하면, \(u_{n+2^k} + A_{2^k-1} u_{n+2^k-1} + \cdots + A_1 u_{n+1} + A_0 u_n = 0\)이다. 

한편, 이미 \(u_x = u_{x+1} = \cdots = u_{x+2^k-1} = 0\)을 알고 있으니, 모든 \(n\)에 대해서 \(u_n = 0\)임이 자명하다. 

증명 과정에서는 \(A_0 \neq 0\)이라는 (자명한) 사실이 사용된다. 나머지는 전형적인 귀납법. 증명 끝. 

이제 끝났다. 지금까지의 관찰을 합쳐서, \(D \le 2^{15}\)임을 알 수 있다. 증명 끝.

Note. 관련된 문제인 RMM 2010 Problem 1을 참고하면 도움이 될 것 같다. 출제자는 Dan Schwarz.

최근에 쉬운 문제 몇 개를 더 풀어서 300문제를 찍었다. 어려운 문제 몇 개는 종강하면 포스팅을 할 듯.

비행기를 안 놓쳤으면 2019/11/15 ~ 2019/11/17인데 비행기를 놓쳐버렸다 ㅋㅋ

현재 204코인 (146 -> 204니까 이번 여행에서 총 58코인 사용), 레이팅 14.15

MASTER 난이도 기준, 이전에 한 기록까지 포함 (OLD/NEW로 구분)

12

ガヴリールドロップキック - S - 997,966 (OLD)

アスノヨゾラ哨戒班 - SS - 1,005,260 (NEW)

回レ！雪月花 - S - 987,223 (981,556 -> 987,223)

Aventyr - S - 991,171 (OLD)

Black Lair - S - 975,595 (OLD)

ERIS -Legend of Gaidelia- - S - 993,615 (NEW)

Eternal Drain - S - 989,338 (OLD)

Flower - SS - 1,004,889 (986,762 -> 1,004,889)

Her Majesty - S - 994,161 (OLD)

Kronos - S - 986,668 (NEW)

L9 - S - 993,871 (OLD)

Lapis - S - 977,773 (NEW)

Palette - S - 997,422 (NEW)

Sakura Fubiki - S - 982,429 (OLD)

STAGER - S - 981,372 (NEW)

12+

四次元跳躍機関 - S - 987,302 (NEW)

ゴーストルール - S - 986,533 (NEW)

Altale - S - 987,540 (OLD)

Axium Crisis - SS - 1,000,515 (OLD)

Savior of Song - AAA - 951,391 (NEW)

Say A Vengeance - SS - 1,000,788 (990,312 -> 1,000,788)

The Formula - S - 994,168 (OLD)

13

極圏 - S - 980,015 (OLD)

管弦楽組曲 第3番 ニ長調「第2曲（G線上のアリア）」BWV.1068-2 - S - 976,071 (958,135 -> 976,071)

初音ミクの消失 - S - 990,298 (NEW)

ぶいえす!!らいばる!! - S - 985,145 (NEW)

インビジブル - S - 990,327 (NEW)

拝啓ドッペルゲンガー - S - 978,073 (NEW)

星の器～STAR OF ANDROMEDA - S - 985,935 (NEW)

幻想のサテライト - AAA - 960,718 (NEW)

ゴールドビジョン - S - 980,874 (NEW)

最終鬼畜妹フランドール・S - S - 981,716 (NEW)

ギガンティックO.T.N - S - 977,313 (NEW)

Air - S - 984,789 (983,001 -> 984,789)

Aragami - S - 991,230 (983,175 -> 991,230)

Avalon - S - 978,190 (OLD)

BlazinG AIR - S - 988,511 (NEW)

Blythe - S - 995,422 (985,965 -> 995,422)

Brain Power - S - 982,305 (OLD)

conflict - S - 985,404 (OLD)

CO5M1C R4ILR0AD - S - 996,427 (992,789 -> 996,427)

DataErr0r - S - 984,538 (OLD)

Destr0yer - S - 990,486 (NEW)

Dragonlady - S - 990,737 (OLD)

Dreadnought - S - 987,118 (977,304 -> 987,118)

Elemental Creation - S - 980,222 (OLD)

Evans - S - 980,512 (976,841 -> 980,512)

Gengaozo - S - 979,679 (966,676 -> 979,679)

Gerbera - S - 997,885 (996,115 -> 997,885)

Goodtek - S - 986,899 (OLD)

Halcyon - S - 990,454 (987,541 -> 990,454)

Imperishable Night 2006 (2016 Refine) - S - 987,361 (978,105 -> 987,361)

Jack-the-Ripper - S - 980,495 (977,385 -> 980,495)

Name of oath - S - 986,907 (NEW)

Nhelv - S - 985,944 (OLD)

Oshama Scramble (Cranky Remix) - SS - 1,000,130 (980,633 -> 1,000,130)

Parousia - S - 993,067 (983,099 -> 993,067)

Phantasm Brigade - S - 993,054 (985,444 -> 993,054)

PUPA - S - 975,762 (963,139 -> 975,762)

Pure Ruby - S - 989,407 (NEW)

R.I.P. - S - 975,293 (NEW)

Scarlet Lance - S - 980,718 (958,279 -> 980,718)

Strahv - S - 978,116 (OLD)

Vallista - S - 982,058 (OLD)

volcanic - S - 988,328 (985,541 -> 988,328)

13+

エンドマークに希望と涙を添えて - S - 976,741 (957,553 -> 976,741)

水晶世界 ～Fracture～ - S - 986,380 (NEW)

神威 - AAA - 968,817 (964,115 -> 968,817)

Amazing Mighty - AAA - 954,229 (OLD)

Angel Dust - S - (970,498 -> 975,735)

Calamity Fortune - S - 986,327 (979,243 -> 986,327)

Dengeki Tube - S - 978,334 (OLD)

Doppelganger - S - 980,989 (OLD)

End time - S - 985,425 (OLD)

Finite - S - 979,803 (OLD)

Fracture Ray - SS - 1,000,626 (999,853 -> 1,000,626)

Freedom Dive - S - 981,809 (975,414 -> 981,809)

Garakuta Doll Play - AAA - 952,388 (900,277 -> 952,388)

Glorious Crown (tpz Remix) - S - 983,003 (OLD)

Grievous Lady - S - 983,661 (952,718 -> 983,661)

Haelequin - S - 979,200 (964,920 -> 979,200)

Larva - S - 988,651 (979,746 -> 988,651)

LittlE HearTs - S - 983,885 (975,747 -> 983,885)

otorii INNOVATED -[i]3- - AAA - 974,414 (NEW)

Ouroboros - S - 976,769 (972,072 -> 976,769)

Schrecklicher Aufstand - AAA - 950,277 (OLD)

Vertex - AAA - 966,630 (OLD)

Xevel - S - 977,675 (952,077 -> 977,675)

14

ikazuchi 14 - AAA - 971,963 (956,090 -> 971,963)

TiamaT: F minor - AAA - 971,521 (NEW)

World Vanquisher - AAA - 969,963 (NEW)

정말 간단하게, 의식의 흐름대로 쓰려고 한다. 종이 안 쓰고 글 쓰면서 푼 거라 깔끔하지는 않다.

이번에 29, 30이 진짜 쉽긴 한 것 같다 ㅋㅋ; 번호는 짝수 기준. 

20번.

• 앞면이 5번 이상 나오면 무조건 연속해서 나오는 경우가 있다.
• 여기서 \(\binom{7}{5}+\binom{7}{6}+\binom{7}{7} = 29\)개.
  
• 앞면이 4번 나오면, 한 경우를 제외하면 연속해서 나오는 경우가 있다.
• 여기서 \(\binom{7}{4}-1 = 34\)개.
• 앞면이 3번 나오는 경우를 보자. 전체 \(35\)개 중, 연속해서 나오지 않는 경우는 몇 개?
• \(1 \le x_1 < x_2 - 1 < x_3 - 2 \le 5\)로 생각하면 \(\binom{5}{3} = 10\)개.
• 그러니 총 \(29+34+35-10 = 88\)개. 답은 \(\frac{88}{2^7} = \frac{11}{16}\)이니 1번.

21번. 

• 절댓값과 미분 가능성에 관한 문제는 정말 많이 나오는 것 같다.
  
• 핵심은 절댓값 안에 있는 값이 0인 경우에, 도함수가 0이어야 한다는 것이다.
• 일단 \(f(x) = e^t(x-t)+e^t\)라는 것은 쉽게 알 수 있다.
• 그러니 우리는 \(|e^t(x-t)+e^t + k - \ln x|\)에 대하여 고민해야 한다.
• 일단 \(h(x) = e^t(x-t) + e^t + k - \ln x\)를 보자.
• \(h'(x) = e^t - \frac{1}{x}\)이니, \(h\)는 감소 후 증가한다.
• \(h\)의 최솟값이 \(0\) 이상이면, 문제 없다.
• \(h\)의 최솟값이 음수면, \(h(x)=0\)인 지점에서 \(h'(x)=0\)이어야 한다.
• 그런데 이러면 결국에는 \(h(x)=0\)인 지점이 그래프 개형상 극점이어야 한다.
• 결론: \(h\)의 최솟값이 \(0\) 이상이어야 한다.
• \(h\)의 최솟값은 \(x = e^{-t}\)에서 얻어진다. 
• 즉, \(h(e^{-t}) = 0\)이 되도록 하는 \(k\)의 값이 \(g(t)\)다.
• 정리하면 \(g(t) = (t-1)e^t - (t+1)\)을 얻는다.
• 이제 \(g\)의 그래프 개형을 그리면, (ㄱ)이 참임을 확인할 수 있다. 
• \(g\)가 연속이며, \(g\)의 최솟값이 음수이니까 (ㄱ)이 참임은 자명하다.
• (ㄴ)도 쉽게 확인할 수 있다. \((c-1)e^c = (c+1)\)이면, \((-c-1)e^{-c} = (-c+1)\)이다. 간단 식 조작.
• 마지막으로 (ㄷ)을 보자. \(g(x)\)의 개형을 다시 생각해보자.
• \(m\)이 최소라는 것은 \(g(\alpha) = g(\beta) = 0\)이라는 것이다.
• 이제 \(g'(x) = xe^x - 1\)임을 생각하면, \(\displaystyle \frac{1+g'(\beta)}{1+g'(\alpha)} = \frac{\beta e^{\beta}}{\alpha e^{\alpha}}\)다.
• 그런데 우리는 (ㄴ)에서 \(\alpha = -\beta\)임을 얻었다. 
• 그러니 이 식은 다시 \(-e^{2\beta}\)로 바뀐다. 이제 확인해야 하는 것은 \(\beta > 1\)인지 여부다.
• 이것은 매우 쉬운 일이다. \(\beta > 1\)임을 쉽게 확인할 수 있고, 결론적으로 (ㄷ)도 참이다. 답은 5번.

29번.

• 구면 위의 점 \((a,b,c)\)에서 그은 접평면의 방정식은 \(ax+by+cz=1\)이다.
• 그러니 접점을 찾으려면, \(a^2+b^2+c^2=3a-3b+3c=-2a+7b-2c=1\)인 \((a,b,c)\)를 찾으면 된다.
• \(b, c\)를 \(a\)에 대하여 표현한 뒤, \(a\)에 대한 이차방정식을 풀면 된다.
• 실제로 접점이 될 수 있는 두 점을 계산할 수 있다.
• 이제 사면체의 부피를 계산하면 되는데 고등학교 과정 내에서 쓰는 방법으로 적당히 계산하면 된다.
• 나는 귀찮아서 wolframalpha + determinant 썼다. 아마 \(\frac{20}{9} \sqrt{3}\)이 나와서 답이 \(29\).  

30번.

• 직관적으로, 한 점에서 만나려면, 그 점에서 두 함수의 값과 도함수가 모두 같아야 한다.
• 직관을 엄밀하게 설명하고 싶다면, 볼록/오목성을 조금만 생각해보면 알 수 있다.
• \(t^3\ln(x-t) = 2e^{x-a}\), \(\frac{t^3}{x-t} = 2e^{x-a}\)인 \(x\)가 있다.
• \((x-t)\ln(x-t) =1\)을 여기서 얻는다. 
• 그런데 \(h(x) = x\ln x\)의 개형을 생각해보면, \(x \ln x =1\)을 만족하는 실수 \(x\)는 유일하다.
• 이 값을 \(u\)라 설정하면, \(x-t=u\)가 강제된다. 
• 다시 대입하면, \(\frac{t^3}{u}  = 2e^{t+u-a}\)를 얻고, 정리하면 \( f(t)=a = t+u - \ln \frac{t^3}{2u}\)다.
• 이를 \(t\)에 대해서 미분하면, \(f'(t) = 1 - \frac{3}{t}\)를 얻는다. 이제 계산하면 답은 \(64\).

스코어보드

우여곡절 끝에 5등으로 첫 ICPC를 마무리했다. A Bus With No Drivers 팀으로 bjwj5505, junie, rkm0959가 한 팀이다.

예상보다는 훨씬 좋은 성적으로 대회를 끝냈지만, 여러 아쉬움도 남는 대회였다.

서울대학교가 top 6팀 중에 5개라는 것도 참 신기하다.

대회에서 우리 팀이 문제를 푼 과정을 대략 복기를 해보면,

• 시작하자마자 bjwj5505가 J를 잡고, K를 나한테 넘겼다. 
• J에 대한 추측을 기반으로 답안 제출 + WA
• junie가 A가 쉽다고 해서 A를 짜서, 맞았다. 8분. 
• junie B 읽기 시작.
• 나는 EFG를 읽었는데 하나 같이 어려워보였다. H를 읽었는데 금광 문제와 똑같았다. 
• 반복되는 J 뇌절
• 그런데 알고보니 뒤에 있는 I, L번이 많이 풀려있었다. 
• bjwj5505 L로 이동, junie B 놓고 I로 이동
• I, L 풀이는 금방 나왔다
• H, I, L 코딩을 동시다발적으로 해서 각각 41, 57, 51분에 맞았다. I는 1틀.
• junie는 다시 B로, 나는 아까 읽은 K로, bjwj5505는 뇌절했던 J로 이동.
• bjwj5505가 J에 대한 추측을 수정하면서 73분에 해결했다. bjwj5505는 D로 이동.
• 나는 K에 대한 내 추측에 확신이 있었고, bjwj5505도 동의했다. 바로 짜서 90분에 해결했다.
• bjwj5505가 D에 대한 추측과 알고리즘을 완성했다. 하지만 WA.
• junie는 B 식을 짰지만 답이 잘 나오지 않았고, 내가 B로 가서 같이 DP 식과 코드를 고쳤다.
• B를 int/ll 문제로 한 번 WA를 받고, 127분에 맞았다. 
• D 코드를 같이 봤지만 문제가 없어보였다. 3번 WA를 받고 잠시 D에서 손을 놓기로 했다.
• G를 같이 읽었는데, bjwj5505가 그냥 풀어버렸다. 코드 디버깅은 같이 했다. 
• 1 WA를 받은 뒤 193분에 AC를 받았다.
• D에 대한 확신을 많이 잃은 뒤라, F를 읽자는 의견이 나왔다.
• 기하가 너무 빡세보여서 나는 D를 어떻게든 잡고 싶었다. stress를 돌리자는 의견이 나왔다.
• 내가 전탐색으로 최소 막대기 개수를 구하는 코드를 짰다. (Dnaive.cpp)
• 내가 우리 코드가 정당한 답을 내는지 확인하는 코드를 D.cpp에 추가했다.
• junie가 테스트 제너레이터를 짰다. (Dgen.cpp)
• junie가 stress test 코드를 짰다. (Dstress.cpp)
• 돌렸더니 금방 반례가 나왔다. 로직의 문제도 곧 나왔다. 
• 로직의 문제를 해결하는 코드를 냈는데, TLE를 예상했지만 바로 AC. 263분에 D를 맞았다.
• 남은 문제는 너무 어려워보여서 던졌다. C, F가 할 만한 문제인줄은 몰랐지 ㅋㅋ
• 끝나고 Ternion 팀하고 같이 술과 고기를 먹었다.

개인적으로 아쉬운 점: 후반부에 루즈해지는 것은 여전한 것 같다. bjwj5505가 G를 짤 때 C나 F를 제대로 봤어야 했다.

개인적으로 잘한 점: 푼 문제는 둘 다 원샷으로 끝냈고, K를 빠르게 풀어낸 것도 잘한 것 같다. 뇌절은 안 한듯.

풀이는 추후에 추가.

• 알고리즘: FFT 공부, 문자열 공부 (Aho-Corasick, Suffix Array, Trie 등), Mo's Algorithm on Trees
  
• 알고리즘 대회: ACM-ICPC 예선 7솔로 통과. 만족스럽지 못한 결과지만 일단 통과는 했고 대회 환경도 그닥이었어서 뭐...
• Project Euler: 9월 말에만 24문제 풀어서 284 문제까지 올렸다. 지금은 안함. 
• 수학: SMMC 2019를 쳤는데 아쉬움이 많음. 뇌절도 많이하고 팀 대회의 이점을 잘 살리지 못한듯.
• 학교 공부 1: 고속 프로그래밍 방법 및 실습이 꽤 재밌다. 최근에 나온 과제는 미분방정식 및 편미분방정식을 일종의 finite element method로 해결하는 방법을 python list, python numpy와 기타 관련 라이브러리 등을 활용하여 구현하고 이를 matplotlib를 이용해서 plot하는 문제였다. scipy와 pdepy를 이용하는 방법으로도 해결할 수 있었다. 또 다른 문제는 Savitzky–Golay filter를 numpy로 구현하는 문제였다. 새롭고 재밌다. 
• 학교 공부 2: 신입생세미나에서 이제 본격적으로 데이터 분석을 시킨다. sklearn, scikit-learn, networkx 등을 다루는 방법을 본격적으로 (혼자) 공부하기 시작해야 할 것 같다. 재밌을 것 같다. 굉장히 기대하는 중.
• 학교 공부 3: 시험이 다가와서 시험 공부를 하는 중. ACM-ICPC 본선은 어떻게 하지 ㅋㅋ
• 여가: 롤드컵 열심히 챙겨보고 있다.