rkm0959

문제

스포 방지선

___________________________________________________________________________________________________________

___________________________________________________________________________________________________________

풀이

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 본선은 어떻게 하지 ㅋㅋ
• 여가: 롤드컵 열심히 챙겨보고 있다. 

8문제. 대략 난이도순.

BOJ 17257 불확정성이 넘쳐흘러

BOJ 16998 It's a Mod, Mod, Mod World

BOJ 11691 LCM(i, j)

BOJ 4862 마지막 자리

BOJ 8293 Prime Prime Power

BOJ 14861 LCM 더하기

BOJ 16941번 꼬리별

BOJ 13714번 약수의 개수

• 미적분학 2, 선형대수학 2, 고속 프로그래밍 방법 및 실습, 이산수학 모두 A+
  
• 알고리즘 지식 더 넓히기, 그리고 아는 알고리즘도 다시 제대로 공부하기
• https://datascienceschool.net/ 여기 최대한 많이 읽기
• 수올 or 정올 계절학기 조교 가능하면 하기
• 방학 때 운전면허 따기 + 정보처리기능사 따기