7์ 1-2์ฃผ์ฐจ Weekly PS
July 01 - July 11, 2021
์ด ๊ธ์ ๊ตฌํ์ฝ๋ ๋งํฌ๊ฐ ์๋๋ผ๋ PS ๋ ํฌ ๋งํฌ ์ ๊ฐ์ ๋ํ ๋จ์๋ก ๋ค์ด๊ฐ๋ฉด ๋ณดํต ์ ๊ฐ ์ฌ๋ ค๋์ ์ฝ๋๋ฅผ ๋ณผ ์ ์์ต๋๋ค.
Recent Updates
- 2021 UCPC์ (ํ๋ช
์ ๋ฏธ์ ) ์ฐธ์ฌํ ์์ ์
๋๋ค. ํ์ฌ ๊ณํ๋ ํ์์
dlwocks31
๊ณผgyuni
๋ก, dlwocks31์ ์ง๋ 2๋ ๊ฐ PS๋ฅผ ๊ฐ์ด ๋์์์๊ณgyuni
๋๊ณผ๋ 2019 UCPC์ฏค์ ํ์ฐ์ต ์คํ๋ง(?) ์ผ๋ก ๋ง๋๋ณธ์ ์ด ์์ต๋๋ค. - 2021 SCPC๋ ์ผ๋จ์ ์ถ์ ํฉ๋๋ค.
Rounds
Atcoder Beginner Round 208
- ๋ผ์ด๋ ๋งํฌ
- 420๋ฑ, +4 (1840 -> 1844).
- D๋ฒ๊น์ง ๋ฌด๋ํ๊ฒ ํ์๋๋ฐ E๋ฒ ๊ตฌํ์์ ๋๋ฌด ์ฌํ๊ฒ ๋ง๋ ธ์ต๋๋ค. ๋ฑํ ์ฌ๋ฐ์ง๋ ์๊ณ โฆ F๋ฒ์ ์ข ์ฌ๋ฐ๋ ์ํ๋ฌธ์ ๊ฐ๋๋ฐ E์ ๋ง๋ ค์ ์ฝ์ด๋ณด์ง๋ ๋ชปํ๋ค์.
(Virtual) Codeforces Round 490 (Div.3)
- E๋ฒ์ด ์ข ์ฌ๋ฐ๋ ๋ฌธ์ ์์ต๋๋ค. ๋๋จธ์ง๋ ๋ฑํ.
- Directed Graph๊ฐ ์ฃผ์ด์ง๊ณ , ์ ์ $s$๊ฐ ์์ด์ ์ฌ๊ธฐ์ ๋ชจ๋ ์ ์ด ๋๋ฌ๊ฐ๋ฅํ๊ธฐ ์ํด ์ต์ ๊ฐ์์ ๊ฐ์ ์ ์ถ๊ฐํ๋ ๋ฌธํญ์ ๋๋ค. $n, m$์ 5์ฒ์ผ๋ก $O(nm)$ ํ์ด๊ฐ ๋ฌด๋ํ ์ ๋ ํฌ๊ธฐ.
- ๋ชจ๋ ์ ์์ BFS๋ฅผ ๋์์ ๋๋ฌ๊ฐ๋ฅํ ์ ๋ค์ ๋ฏธ๋ฆฌ ๊ณ์ฐํ์ฌ, ๊ฐ ์ ์์ ๋๋ฌ๊ฐ๋ฅํ ์งํฉ $R_i$๋ฅผ ๋ค๊ณ ์๊ธฐ๋ก ํฉ์๋ค. ์ด์ , $s$์์ ๋๋ฌ ๋ถ๊ฐ๋ฅํ ์ ๋ค์ $T$๋ผ๊ณ ํ๊ณ , ์ด์ฐจํผ ๋๋ฌ๊ฐ๋ฅํ ์ ๋ค์ ์๋ฏธ๊ฐ ์์ผ๋ฏ๋ก $R_i$ ๋์ $R_i \cap T$๋ฅผ ์๊ฐํจ์ผ๋ก์จ ๋ชจ๋ $R_i \subset T$๊ฐ ๋๊ฒ ํฉ๋๋ค. ๊ทธ๋ฌ๋ฉด $R_i$๋ค ์ค ์ต์ ๊ฐ์์ ์งํฉ์ผ๋ก $T$๋ฅผ ๋ฎ๋ ๋ฌธ์ ๊ฐ ๋ฉ๋๋ค.
- ์ด๋ set cover๋ผ๋ ๋งค์ฐ ์ ๋ช ํ NP-complete ๋ฌธ์ ์ด๋ฏ๋ก ๋น์ฐํ ๊ทธ๋๋ก๋ ํ ์ ์์ต๋๋ค. ๊ทธ๋ฌ๋, $R_i$๋ค์ ๋ํด ์์๊ฐ ์กด์ฌํจ์ ๊ธฐ์ตํฉ์๋ค.
- $a$์์ $b$๋ก ๊ฐ ์ ์๋ค๋ฉด, $R_a$๋ $R_b$๋ฅผ ํฌํจํฉ๋๋ค.
- ๋ฐ๋ผ์, ์๋ก ๋๋ฌ๊ฐ๋ฅํ ์ ๋ค์ ๋ฌถ๊ณ ๋๋ฉด, ๋จ์ $R$๋ค์ set inclusion์ ์ํด ์ด๋ค partial order๋ฅผ ์ด๋ฃน๋๋ค.
- ์ด์ฐจํผ ์ ํ๊ฐ๋ฅผ ๋จน๋๋ค๋ฉด, partial order์ ์ฒด์ธ์ ์๊ฐํ ๋ ๋ฌด์กฐ๊ฑด ๊ฐ ์ฒด์ธ์ ๊ฐ์ฅ ์์ ์๋ ์ ๋ค์ ๋จน๋๊ฒ์ด ์ด๋์ ๋๋ค.
- ์ด๋ค์ ์ด๋ป๊ฒ ๊ตฌ๋ถํ ์ ์์๊น์? ๊ฐ์ฅ ๊ฐ๋จํ ๋ฐฉ๋ฒ์, $R_i$ ๋ค ์ค ํฐ ๊ฒ๋ถํฐ ๋จน์ผ๋ฉด ๋ฉ๋๋ค. ์ฒด์ธ์ ๋จธ๋ฆฌ๋ ๊ทธ ์๋ ๋ ธ๋๋ค๋ณด๋ค ํฌ๋ฏ๋ก, ์ด๋ ๊ฒ ํ๋ฉด ๋จธ๋ฆฌ๋ฅผ ์ ๋จน์ ์ฒด์ธ์์ ์๋ ๋ ธ๋๋ฅผ ๋จน์ ์ผ์ ์์ต๋๋ค. ๋จธ๋ฆฌ๋ฅผ ์ด๋ฏธ ๋จน์๋๋ฐ ๊ทธ ์๋ ๋ ธ๋๋ฅผ ๋จน๋ ์ผ์ ๋ฐฉ์งํ๊ธฐ ์ํด, ๋ ธ๋๋ฅผ ๋จน์ผ๋ฉด์ ๊ทธ ๋ ธ๋์์ ๋๋ฌ๊ฐ๋ฅํ ($R_i$์ ํฌํจ๋) ๋ชจ๋ ์ ์ ๋ค์ ์ง์๋๋ค.
- ์ด ๋ฐฉ๋ฒ์ด ์ ์ ๋นํ์ง ์ฆ๋ช ์ ์ด๋ ต์ง ์์ต๋๋ค.
- ๊ตฌํ ๋งํฌ
- ๋ณ๊ฐ๋ก, SCC๋ฅผ ์ ํ์ฉํ๋ฉด ์ง์ ๋ชจ๋ ์ ์์ BFS๋ฅผ ๋์ง ์๋ Linear time ํ์ด๊ฐ ์๋ค๊ณ ํฉ๋๋ค.
Problems
์ง๋๊ฐ ์ค๋ ฅ์ ๋์ฐพ๊ธฐ ์ํ ๋ชฉ์ ์ผ๋ก ๋ช๊ฐ ๋ฐ์์ต๋๋ค. ์ฃผ๋ก ์ธ๊ทธ๋จผํธ ํธ๋ฆฌ ๋ฌธ์ ๋ฅผ ๋ฐ๊ธฐ๋ก ํ์ต๋๋ค :)
์ธ๊ทธ๋จผํธ ํธ๋ฆฌ ๊ตฌํ์ ์ฌ๊ท ํธ๋ฆฌ์ ๋น์ฌ๊ท ํธ๋ฆฌ๋ฅผ ์์ด ์ฐ๋ ํธ์ ๋๋ค. ๊ฐ๋จํ ๋ ผ์ํ์๋ฉด, ์์ชฝ์๋ ๋ค์๊ณผ ๊ฐ์ ์ฅ๋จ์ ์ด ์์ต๋๋ค.
- ์ฌ๊ทํธ๋ฆฌ๋ ๋ฐ๋ฐ๋ฅ๋ถํฐ ์ ๊ฐ ์งฐ๊ธฐ ๋๋ฌธ์, ๋์์ ๋ณด๋ค ์ ํํ๊ฒ ์ดํดํ๊ณ ์์ด ๋ณํ๋ฌธ์ ๋ฅผ ํ๊ธฐ์ ํธํฉ๋๋ค.
- ์ฌ๊ทํธ๋ฆฌ๊ฐ ๊ทผ๋ณธ์ ์ผ๋ก (Fundamentally์ ์ข์ ๋ฒ์ญ์ด๊ฐ ๋ ์ค๋ฅด์ง ์๋ค์) ์ข๋ ์ง๊ด์ ์ ๋๋ค.
- ๋ฐ๋ฉด, ๋น์ฌ๊ทํธ๋ฆฌ๋ ํ์คํ ๋ ๋น ๋ฆ ๋๋ค. ์์๊ฐ ์ํฅ์ ์ฃผ๋ ๋ฌธ์ ๋ฅผ ๋ง์ด ๋ณธ์ ์ ์์ง๋ง, $O(n \log n)$ ์๋ฃจ์ ์ด ์๋ ๋ฌธ์ ์ ๊ฒฝ์ฐ ๊ฐ๋ ๋น ๋ฅธ $O(n \log^2 n)$์ ํต๊ณผํ๊ณ ๋๊ฐ์ ์๋ฃจ์ ์ ์์๊ฐ ํฌ๋ฉด ์งค๋ฆฝ๋๋ค. ์ด๋ ๊ฐ๋ ์ ์ฉํฉ๋๋ค.
- ๋น์ฌ๊ทํธ๋ฆฌ๋ ๋๋ฆฌ ์๋ ค์ง ๊ตฌํ์ฒด์ธ Efficient and Easy Segment Trees ๋ฅผ ๊ฐ์ ธ์์ ์กฐ๊ธ ๊ณ ์ณ ์ฐ๊ณ ์์ต๋๋ค. ๋ง์ ์ฌ๋๋ค์ด ๊ณต์ ํ๋ ๋ผ์ด๋ธ๋ฌ๋ฆฌ๋ฅผ ์ด๋ค๋ ๊ฒ์ ๊ทธ ์์ฒด๋ก ์ฅ์ ์ ๋๋ค.
์ ๊ฐ ์ฐ๋ ์ฌ๊ทํธ๋ฆฌ ๊ตฌํ์ฒด๋ ์ฟผ๋ฆฌ๋ฅผ $[l, r]$ ์๋ค ๋ ๋ฆฌ๊ณ , ๋น์ฌ๊ทํธ๋ฆฌ ๊ตฌํ์ฒด๋ ๊ฐ์ ธ์จ ์ฝ๋๋ผ์ $[l, r)$ ์๋ค ๋ ๋ฆฝ๋๋ค. ํน์ ์ ์ฝ๋๋ฅผ ๋ณด์ค์ผ์ด ์๋ค๋ฉด ์ฐธ๊ณ ํด์ฃผ์ธ์..? ใ ใ ใ
ICPC Mid Atlantic 2006, BOJ 1849 ์์ด
- ๋์ด๋ : Platinum 4
- $1, 2, \dots n$ ์ permutation์ ์ฐพ๋ ๋ฌธ์ ์ธ๋ฐ, ๊ฐ $i$์ ๋ํด, $i$ ์์ ์๋ ์๋ค ์ค $i$๋ณด๋ค ํฐ ์์ ๊ฐ์ $A_i$ ๊ฐ ์ฃผ์ด์ง๋๋ค.
- ๊ธฐ๋ณธ์ ์ธ ์์ด๋์ด๋, ๊ฐ $i$๊ฐ ๋ค์ด๊ฐ ์์น๋ฅผ ์ฐพ์์ฃผ๋ ๊ฒ์ ๋๋ค. 1์ ์ ์ธํ ๋ชจ๋ ์๊ฐ 1๋ณด๋ค ํฌ๊ธฐ ๋๋ฌธ์, $A_1$์ด ์ฃผ์ด์ง๋ฉด 1์ด ๋ค์ด๊ฐ์ผ ํ ์์น๋ฅผ ๊ทธ๋ฅ ์ ์ ์์ต๋๋ค. 1์ ์ฐพ๊ณ ๋๋ฉด, 2๋ ๋จ์ ์๋ฆฌ๋ค ์ค $A_2$๋ฒ์งธ ์๋ฆฌ์ ๋ค์ด๊ฐ์ผ ํ๋ค๋ ๊ฒ์ ์ด๋ ต์ง ์๊ฒ ์ ์ ์์ต๋๋ค.
- ๊ฒฐ๊ตญ์ $1, 2, \dots n$ ์ ๋ํด, ์ด ์งํฉ์์ ์๋ฅผ ํ๋ ๋ฝ์๋ด๊ณ , ๋จ์ ์๋ ์๋ค ์ค $k$๋ฒ์งธ๋ฅผ ๋น ๋ฅด๊ฒ ๊ตฌํ๋ ์๋ฃ๊ตฌ์กฐ๊ฐ ํ์ํฉ๋๋ค.
- Order statistics tree๋ฅผ ์ด์ฉํ์ฌ $O(n \log n)$์ ์ฝ๊ฒ ํด๊ฒฐํ ์ ์๊ณ , segment tree๋ก๋ ๊ฐ์ ๋ณต์ก๋๋ก ๊ตฌํํ ์ ์์ต๋๋ค.
CERC 2010D, BOJ 3429 ๋ฐฉ์ด์
- ๋์ด๋ : Platinum 4
- ์์ด $A_i$๊ฐ ํ๋ ์ฃผ์ด์ง๊ณ , ์์ด์์ ์ต์ฅ ๊ธธ์ด์ ์ฐ์ํ๋ ์ฆ๊ฐ ๋ถ๋ถ ์ ์ฐพ๋ ๋ฌธ์ ์ ๋๋ค. ๋จ, ๋ฑ ํ ๋ฒ ์๋ ์์ด์์ ์ฐ์ํ ๋ถ๋ถ ํ๋๋ฅผ ๋ค์ด๋ผ ์ ์์ต๋๋ค.
- ์๋ฅผ ๋ค์ด, 5, 3, 4, 9, 2, 8, 6, 7, 1 ์์ (9, 2, 8) ๋ถ๋ถ์ ๋ผ์ด๋ด๊ณ ๊ฐ์ด๋ฐ 3, 4, 6, 7์ ์ทจํ๋ ์์ ๋๋ค.
-
DP1[i]
,DP2[i]
๋ฅผ ๊ฐ๊ฐ $i$๋ฒ์งธ๋ฅผ ์ค๋ฅธ์ชฝ / ์ผ์ชฝ ๋์ผ๋ก ํ๋ ์ต์ฅ ๊ธธ์ด์ ์ฐ์ํ๋ ์ฆ๊ฐ ๋ถ๋ถ์ด๋ผ๊ณ ํฉ์๋ค. ์ด์ , ์ฐ๋ฆฌ๊ฐ ์ํ๋ ๊ฐ์ ๋ชจ๋ $i < j$, $A_i < A_j$์ ๋ํด, $D_1(i) + D_2(j)$ ๋ฅผ ๊ณ์ฐํ์ฌ ์ด๋ฅผ maximizeํ๋ ๊ฒ์ ๋๋ค. - ์ ํํ์ Naiveํ๊ฒ ๊ณ์ฐํ๋ ค๊ณ ์๋ํ๋ฉด โ๋ชจ๋ $i < j$, $A_i < A_j$โ ์์ ์ด๋ฏธ $O(n^2)$ ์๊ฐ์ด ๊ฑธ๋ฆฝ๋๋ค.
- ๋์ , $A_i$๊ฐ ํฐ ๊ฒ๋ถํฐ $D_2(i)$์ ๊ฐ๋ค์ ์ธ๊ทธ๋จผํธ ํธ๋ฆฌ ๊ฐ์ ์๋ฃ๊ตฌ์กฐ์ ์
๋ฐ์ดํธํ๊ณ , ์ฌ๊ธฐ์ $[i, n]$ ๊ตฌ๊ฐ์ ์ต๋๊ฐ์ ์ฟผ๋ฆฌํ๋ ์์ผ๋ก ์๊ฐํ๋ฉด $O(n \log n)$ ์๊ฐ์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์์ต๋๋ค. ์ฝ์ด ๋ก์ง์ ์ฝ๋๋โฆ
for (int i = n-1; i >= 0; i--) { int u = arr[i].second; int q = s.query(u, n); s.modify(u, dp2[u]); dp[u] = dp1[u] + q; ans = max(ans, dp[u]); } cout << ans << '\n'; }
-
arr[i].second
๋ $A_i$ ์์ผ๋ก ์ ๋ ฌํ ํ ๋ค์ ์ธ๋ฑ์ค๋ฅผ ๊ฐ์ ธ์ค๊ธฐ ์ํจ์ ๋๋ค. ๋๋ต์ ์ธ ์ ๋ฐ์ดํธ ์์๋ ๋ฐ๋ก ๋์ผ๋ก ๋ณด๋ ๋๋ก์ ๋๋ค. - ์ฃผ์ํ ์ ์, $A_i = A_j$ ์ธ $i, j$๊ฐ ์์์ด ๋ณด์ฅ๋์ด์์ง ์๊ธฐ ๋๋ฌธ์, ์ฟผ๋ฆฌํ ๋ ์ ๋ฐ์ดํธ ์์๋ฅผ ์กฐ์ฌํด์ผ ํฉ๋๋ค. $A_i$๊ฐ ๊ฐ์ ๋ ๋ญ๋ถํฐ $D_2(i)$ ๋ฅผ ์ธ๊ทธํธ๋ฆฌ์ ๋ฃ์ด์ฃผ๋์ง๊ฐ ์ค์ํ๋ฐ, $A_i = A_j$์ด๋ฉด $D_2(i)$์ ์ ๋ฌด๊ฐ ํ์ํ๋ $j$ ์ฟผ๋ฆฌ์ ์ํฅ์ ์ค ์ ์๋๋ก, ์ผ์ชฝ๋ถํฐ ์ ๋ฐ์ดํธํด์ผ ํฉ๋๋ค.
UCPC 2018 ์์ F, BOJ 15899 ํธ๋ฆฌ์ ์๊น
- ๋์ด๋ : Platinum 2
- ํธ๋ฆฌ์ ๊ฐ ์ ์ ์ด 1๋ถํฐ $C$ ์ฌ์ด์ ์๊น์ ๊ฐ์ง๊ณ ์๊ณ , $f(v, c)$ ๋ฅผ $v$๋ฅผ ๋ฃจํธ๋ก ํ๋ ์๋ธํธ๋ฆฌ์์ ์๊น์ด $c$์ดํ์ธ ์ ์ ์ ๊ฐ์๋ก ์ ์ํ ๋ ์ด๋ฅผ ๋นจ๋ฆฌ ๊ณ์ฐํ๋ ๋ฌธ์ ์ ๋๋ค.
- Euler Tour ๋ผ๋ ํ ํฌ๋์ ์ด์ฉ, ํธ๋ฆฌ๋ฅผ ๋ฐฐ์ด๋ก ํด ์ฃผ๋ฉด ์๋ธํธ๋ฆฌ์ ๋ํ ์ฟผ๋ฆฌ๊ฐ ์ฐ๋ฆฌ๊ฐ ์ ์ดํดํ๊ณ ์๋ ๊ตฌ๊ฐ์ ๋ํ ์ฟผ๋ฆฌ๋ก ๋ฐ๋๋๋ค.
- ์ฟผ๋ฆฌ๋ฅผ ์คํ๋ผ์ธ ์ฒ๋ฆฌํด์, ์๊น์ด ์์ ์ฟผ๋ฆฌ๋ถํฐ ์ฒ๋ฆฌํ๊ฒ ์ต๋๋ค.
- ์ด์ , ์๊น์ด ์์ ๊ฒ๋ถํฐ ์ ๋ฐ์ดํธํ๋ฉด์ ์ค๊ฐ์ค๊ฐ ํ์ด๋ฐ์ด ๋ ๋๋ง๋ค ์ฟผ๋ฆฌ๋ฅผ ์ฒ๋ฆฌํด ์ฃผ๋ฉด ๋ฉ๋๋ค.
BOJ 14287 ํ์ฌ ๋ฌธํ 3
- ๋์ด๋ : Platinum 4
- ์ ๋ฌธ์ ์ ๋๊ฐ์ด Euler Tour ๋ฅผ ์ด์ฉํ์ฌ ํธ๋ฆฌ๋ฅผ ๋ฐฐ์ด๋ก ํด๊ณ
- ์นญ์ฐฌ๋ฐ์ ๋ ธ๋์ ๊ฐ์ ๋ํ ๋ค์
- ์ฟผ๋ฆฌ๊ฐ ๋ค์ด์ค๋ฉด ๊ทธ ๋ ธ๋์ ์๋ธํธ๋ฆฌ๊ฐ ๋ฐ์ ์นญ์ฐฌ์ ๊ฐ์ ํฉํ๋ฉด ๋์ ๋๋ค.
- ๊ตฌํ์ด ๋งค์ฐ ๋จ์ํด์, ์ค์ผ๋ฌํฌ์ด ๊ตฌํ์ ํ์ธํ๊ธฐ์ ์ ์ ํฉ๋๋ค.
- ๋๋ฆ๋๋ก ๊นจ๋ํ๊ฒ ๊ตฌํํ๋ ค๊ณ ๋ ธ๋ ฅํ ๋งํฌ ์ฐธ๊ณ .
BAPC 2005E, BOJ 5419 ๋ถ์ํ
- ๋์ด๋ : Platinum 4
- ์ ํ์ ์ธ โ์ค์ํ + ์ธ๊ทธํธ๋ฆฌโ ์ ๋๋ค.
- ๋ฌธ์ ๋ฅผ ๋จ์ํํ๊ธฐ ์ํด, ์ขํํ๋ฉด์ N๊ฐ์ ์ ์ด ์๊ณ , ๋จ๋์ชฝ ๋์ ๋ถ๋์ชฝ์ผ๋ก ๊ฐ๋ค๊ณ ์๊ฐํด ๋ด ์๋ค. ์ขํ์์ถ์ ํ๋ค์ Y์ขํ๋ค์ ๋ค์ง์ด ๋ฒ๋ฆฌ๋ฉด ์ด๋ ๊ฒ ๋ง๋๋ ๊ฒ์ ์ด๋ ต์ง ์๊ฒ ๊ฐ๋ฅํฉ๋๋ค.
- ์ด์ , ๊ฐ ์ ๋ค์ $(x_i, y_i)$ ๋ผ๊ณ ํ๊ณ , 1์ฐจ์ ์ธ๊ทธ๋จผํธ ํธ๋ฆฌ ํ๋๋ฅผ ๋ง๋ญ๋๋ค. ๊ฐ ์ ์ ์ธ๊ทธํธ๋ฆฌ์ $x_i$ ๋ฒ ์์น์ ์ถ๊ฐํ ๊ฒ์ ๋๋ค.
- ์ฐ๋ฆฌ๊ฐ ์ํ๋ ๊ฒ์, $(x_i, y_i)$์ ์์ ์ธ๊ทธํธ๋ฆฌ์ $[x_i, \infty]$ ์ฟผ๋ฆฌ๋ฅผ ๋ ๋ ธ์๋ ์ฌ๊ธฐ์๋ถํฐ ๋ถ๋์ชฝ์ผ๋ก ๊ฐ์์๋ ์ ์ ๊ฐ์๋ฅผ ์ป๋ ๊ฒ์ ๋๋ค. ๊ทธ๋ฌ๋ ์ฐ๋ฆฌ์ ์ธ๊ทธํธ๋ฆฌ๋ $y$์ขํ๋ฅผ ๊ธฐ์ตํ์ง ์๊ณ ๊ทธ๋ฅ ๋ฌด์์ ์ ์ ๊ฐ์๋ฅผ ์ธ๊ธฐ ๋๋ฌธ์, $y$์ขํ๋ ์ฐ๋ฆฌ๊ฐ ์ค์ํํด์ผ ํฉ๋๋ค.
- $y$์ขํ๊ฐ ํฐ ์์๋๋ก, ์ฆ ์์์๋ถํฐ ์ธ๊ทธํธ๋ฆฌ์ ์ ์ ํ๋์ฉ ๋ฃ์ผ๋ฉด์, ์ด ์ ๊น์ง ๋ฃ์ ๋ค์ ๋์ชฝ์ ๋ฐ๋ผ๋ณด๋ฉด ๋๋ณด๋ค ์๋ (y์ขํ ๊ธฐ์ค) ์ ๋ค์ ์์ง ์์ ์ถ๊ฐ๊ฐ ๋์ง ์์๊ธฐ ๋๋ฌธ์ ๋ถ๋์ชฝ ์ ๋ค๋ง ๋ณด์ด๊ฒ ๋ฉ๋๋ค.
- ์ฃผ์ํ ์ ์, ์ ์ ์ ํํ ์ธ๊ธฐ ์ํด์๋ $y$์ขํ๊ฐ ๊ฐ์ ์ ๋ค์ $x$์ขํ๊ฐ ํฐ ์ชฝ๋ถํฐ ์ฒ๋ฆฌํด์ผ ํฉ๋๋ค.
SCCC 2019E, BOJ 17131 ์ฌ์ฐ๊ฐ ์ ๋ณด์ฌ์ ์ฌ๋ผ์จ ์ด์
- ๋์ด๋ : Platinum 4
- ๋ฐ๋ก ์ ๋ฌธ์ ์ ๊ฑฐ์ ๋๊ฐ์ต๋๋ค.
- $y$ ์ขํ ์์๋๋ก ๋ด๋ ค์ค๋ฉด์ ์ ๋ฐ์ดํธํ๊ณ ์ฟผ๋ฆฌํฉ๋๋ค. ์ด๋ฌธ์ ๋ $[0, x_i - 1]$ ๊ณผ $[x_i+1, \infty]$ ๋ฅผ ์ฟผ๋ฆฌํด์ ๊ณฑํ๋ ๋ฐฉ์์ ๋๋ค.
- ๋ฑ ํ๋ ์ฃผ์ํ ์ ์, ์ ๋ฌธ์ ์๋ ๋ฌ๋ฆฌ $y$์ขํ๊ฐ ๊ฐ์ ์ ๋ค์ ์ ๋ฐ์ดํธํ๋ ์์๋ฅผ ์ด๋ป๊ฒ ์ค๋ ๊ผฌ์ด๊ฒ ๋ฉ๋๋ค. $y$์ขํ๊ฐ ๊ฐ์ ์ ๋ค์ ๋ฐ๋ก ๊ธฐ์ตํด ๋จ๋ค๊ฐ ํ๋ฒ์ ์ ๋ฐ์ดํธํด์ผ ํฉ๋๋ค. ์ฝ๋๋ฅผ ์ฐธ๊ณ ํด ์ฃผ์ธ์.
BOJ 16993, ์ฐ์ํฉ๊ณผ ์ฟผ๋ฆฌ
- ๋์ด๋ : Platinum 2
- ์ฐ์ํฉ๊ณผ ์ฟผ๋ฆฌ๋ ์์ โ๊ธ๊ด์ธ๊ทธโ ๋ฅผ ์ด์ฉํ์ฌ ํ ์ ์์์ด ๋งค์ฐ ์ ์๋ ค์ ธ ์์ต๋๋ค.
- ์ธ๊ทธ๋จผํธ ํธ๋ฆฌ๋ฅผ ์ฌ์ฉํ๋, ๋ค์๊ณผ ๊ฐ์ ์ ๋ณด๋ค์ ์ ์ฅํฉ๋๋ค. ์ธ๊ทธํธ๋ฆฌ์ ํ ๋
ธ๋๊ฐ ๊ตฌ๊ฐ $[l, r]$ ์ ๋์ํ๋ค๋ ์ฌ์ค์ ๊ธฐ์ตํฉ์๋ค.
- ์๊ธฐ๊ฐ ๋ด๋นํ๋ ๊ตฌ๊ฐ์ ์ผ์ชฝ ๋์์ ์์ํด์ ์ป์ ์ ์๋ ์ต๋ ๊ตฌ๊ฐํฉ
- ์๊ธฐ๊ฐ ๋ด๋นํ๋ ๊ตฌ๊ฐ์ ์ค๋ฅธ์ชฝ ๋์์ ์์ํด์ ์ป์ ์ ์๋ ์ต๋ ๊ตฌ๊ฐํฉ
- ์๊ธฐ๊ฐ ๋ด๋นํ๋ ๊ตฌ๊ฐ์ ์ต๋ ๊ตฌ๊ฐํฉ
- ์๊ธฐ๊ฐ ๋ด๋นํ๋ ๊ตฌ๊ฐ์ ํฉ
- ์ด ๋ค ์ ๋ณด๋ฅผ ls, rs, ms, s๋ผ๊ณ ํ๋ฉด, ๋ ๋
ธ๋๋ฅผ ํฉ์น ๋ ๋ค์๊ณผ ๊ฐ์ด ์๊ฐํ๋ฉด ๋ฉ๋๋ค.
- ๋ ธ๋ $a$, $b$๋ฅผ ํฉ์ณ์ $e$๋ก ๋ง๋ค ๋,
-
e.s
๋ ์๋ช ํฉ๋๋ค. -
e.ls
๋,e
์ ์ผ์ชฝ ๋์์ ์์ํด์ผ ํ๋ฏ๋กa.ls
๊ฐ ๋ต์ผ ์๋ ์๊ณ , a๋ฅผ ๋ค ๋จน๊ณ b์ ์ผ์ชฝ ์ผ๋ถ๋ฅผ ๋จน๋ ๊ฒฝ์ฐ๊ฐ ๋ต์ผ ์๋ ์์ต๋๋ค. ํ์๋a.s + b.ls
๊ฐ ์ต๋์ผ ๊ฒ์ ๋๋ค (ls์ ์ ์). ๋ฐ๋ผ์, ๋ ๊ฐ ์ค ์ต๋๋ฅผ ์ทจํฉ๋๋ค. - ๊ฐ์ ์๋ฆฌ๋ก,
e.rs
๋b.rs
์b.s + a.rs
์ค ํฐ ๊ฐ์ ๊ณ ๋ฅด๋ฉด ๋ฉ๋๋ค. - ๋ง์ง๋ง์
e.ms
์ ๋๋ค. ์ด๋ ๋ค์ ๊ฒฝ์ฐ๋ฅผ ๋๋์ด ์๊ฐํ๋ฉด,a
๊ตฌ๊ฐ์ ํฌํจ๋ ๋ต์ ๊ฐ๊ฑฐ๋ (a.ms
),b
๊ตฌ๊ฐ์ ํฌํจ๋ ๋ต์ ๊ฐ๊ฑฐ๋ (b.ms
), ๋ ๊ตฌ๊ฐ์ ๊ฑธ์น ๋ต์ ๊ฐ๊ฑฐ๋ (์ด ๋ต์ดa.rs + b.ls
๊ฐ ์ต์ ์์ ๊ด์ฐฐํฉ๋๋ค) ์ธ๊ฐ์ง ๊ฒฝ์ฐ (๋์นญ์ ์ ์ธํ๋ฉด ๋๊ฐ์ง) ๋ฐ์ ์์ต๋๋ค.
- ๋ฐ๋ผ์, ์์๋ฐฐ์ ์๊ฐ์ ์ง๋ถํ์ฌ ๋ชจ๋ ์ ๋ณด๋ฅผ ๊ด๋ฆฌํ ์ ์๊ณ , ์ฐ์ํฉ ์ฟผ๋ฆฌ๋ฅผ ๋๊ฐ์ด ๋ ๋ ค์ค ์ ์์ต๋๋ค.
- ๋ ๋ ธ๋๋ฅผ ํฉ์น ๋, ๋จ์ํฉ์์๋ ์ข์ฐ๊ฐ ์๊ด์์ง๋ง ์ด๋ฐ ํน์ํ ์ฐ์ฐ์ ํ ๋๋ ์ข์ฐ๋ฅผ ์กฐ์ฌํด์ผ ํฉ๋๋ค.
Review
์ธ๊ทธ๋จผํธ ํธ๋ฆฌ ๋ฌธ์ ๋ฅผ ์ค๋๋ง์ ๋ฐ๋ฉด์ ์๋ฃ๊ตฌ์กฐ์ ๋ํ ์ดํด๋ฅผ ๋์ง์๋ค๋ ์ ๋์ ์์๊ฐ ์๋๊ฒ ๊ฐ์ต๋๋ค.