Back to : ps-weekly
Contents

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

์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ ๋ฌธ์ œ๋ฅผ ์˜ค๋žœ๋งŒ์— ๋ฐ€๋ฉด์„œ ์ž๋ฃŒ๊ตฌ์กฐ์— ๋Œ€ํ•œ ์ดํ•ด๋ฅผ ๋˜์งš์—ˆ๋‹ค๋Š” ์ •๋„์˜ ์˜์˜๊ฐ€ ์žˆ๋Š”๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค.