Back to : ps-weekly
Contents

July 11 - July 18, 2021

์ด ๊ธ€์— ๊ตฌํ˜„์ฝ”๋“œ ๋งํฌ๊ฐ€ ์—†๋”๋ผ๋„ PS ๋ ˆํฌ ๋งํฌ ์— ๊ฐ€์„œ ๋Œ€ํšŒ ๋‹จ์œ„๋กœ ๋“ค์–ด๊ฐ€๋ฉด ๋ณดํ†ต ์˜ฌ๋ ค๋†“์€ ์ฝ”๋“œ๋ฅผ ๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

Recent Updates

  • 2021 SCPC ๋ผ์šด๋“œ 1์€ ๋ญ ๋ฌด๋‚œํžˆ ํ†ต๊ณผํ–ˆ์Šต๋‹ˆ๋‹ค.

Rounds

(ํŒ€์—ฐ์Šต) ์„œ๊ฐ•๋Œ€ํ•™๊ต 2020 SPC Div.1 (Champion)

(๋Œ€ํšŒ) SCPC 2021 Round 1

(Atcoder) Atcoder Beginner Round 210

  • ๋ผ์šด๋“œ ๋งํฌ
  • 582๋“ฑ, -9 (1844 -> 1835).
  • D๋ฒˆ DP๋ฌธ์ œ๋ฅผ ๋ชป ํ’€์–ด์„œ ๋ ˆ์ดํŒ…์„ ์ข€ ๊นŽ์•„๋จน์—ˆ์Šต๋‹ˆ๋‹ค. ๋Œ€์‹  E๋ฒˆ (์ˆ˜ํ•™..์ด๋ผ๊ธด ์ข€ ์• ๋งคํ•˜๊ณ  ์ž˜ ๋ชจ๋ฅด๊ฒ ์Šต๋‹ˆ๋‹ค) ์„ ํ’€์–ด์„œ ๋ณธ์ „์€ ์นœ๋“ฏ ํ•ฉ๋‹ˆ๋‹ค.

Problems

์ด๋ฒˆ์—๋Š” DP ์—ฐ์Šต์„ ํ•˜๊ธฐ๋กœ ํ–ˆ์Šต๋‹ˆ๋‹ค. ๋ฐฑ์ค€ ๋ฒˆํ˜ธ๋ฅผ ์ ์–ด๋†จ์œผ๋ฏ€๋กœ ๋ฌธ์ œ์„ค๋ช…์€ ๊ฐ€๊ธ‰์  ์ƒ๋žตํ•ฉ๋‹ˆ๋‹ค.


IOI 2009-4, Raisins (BOJ 5463 ๊ฑดํฌ๋„)

  • ๋‚œ์ด๋„ Gold 1
  • IOI์— ์ด๋Ÿฐ ๋ฌธ์ œ๊ฐ€ ๋‚˜์˜จ์  ์žˆ๋Š”์ง€๋Š” ๋ชฐ๋ž์Šต๋‹ˆ๋‹ค. ๋ฌด์Šจ 20์„ธ๊ธฐ ๋Œ€ํšŒ๋„ ์•„๋‹ˆ๊ณ  2009๋…„์—..?
  • ๊ฑฐ์˜ straightforwardํ•œ DP๋กœ ํ•ด๊ฒฐ์ด ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.
    • dp[r1][c1][r2][c2] ๋ฅผ ์ง์ ‘ $[r1, c1] \times [r2, c2]$ ์‚ฌ๊ฐํ˜•์˜ DP๊ฐ’์ด๋ผ๊ณ  ์ •์˜ํ•˜๋ฉด,
    • ์ด์ œ ์ด ๊ฐ’์€ ๋ชจ๋“  ๊ฐ€๋กœ/์„ธ๋กœ ์ปท์„ ์ง์ ‘ ํ™•์ธํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.
    • ๊ตฌํ˜„ ์ฝ”๋“œ ๊ฐ€ ์ƒ๋‹นํžˆ ๊ฐ„๋‹จํ•˜๋ฏ€๋กœ ํ™•์ธํ•˜๋ฉด ๋„์›€์ด ๋ ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค. ๋ ˆํฌ์—์„œ IOI๋ฅผ ์ฐพ์•„๊ฐ€๋ฉด ๋ฉ๋‹ˆ๋‹ค.
  • ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” $O(n^4)$ ์นธ DP๋ฅผ ์นธ๋‹น $O(n)$ ์‹œ๊ฐ„์— ์ฑ„์šฐ๋Š” ๊ฒƒ์ด๋ฏ€๋กœ $O(n^5)$ ์ž…๋‹ˆ๋‹ค.

์„œ๊ฐ•๋Œ€ํ•™๊ต SPC 2015-1F, ๋ชฌ์Šคํ„ฐ (BOJ 11573)

  • ๋‚œ์ด๋„ Gold 1
  • ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ dp[i][j][k] ๋ฅผ ๋นจ๊ฐ„์ƒ‰ ๋…ธ๋ž€์ƒ‰ ํŒŒ๋ž€์ƒ‰์ด $i, j, k$ ๋งˆ๋ฆฌ ๋‚จ์€ ์ƒํ™ฉ์ด๋ผ๊ณ  ์ƒ๊ฐํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.
  • ์ด๋•Œ, Random choice์— ์˜ํ•ด ๋นจ๊ฐ„์ƒ‰๊ณผ ๋…ธ๋ž€์ƒ‰์ด ๋งŒ๋‚  ํ™•๋ฅ ์€ $\frac{ij}{ij + jk + ki}$ ์ž…๋‹ˆ๋‹ค.
  • ์ด๋ ‡๊ฒŒ ๊ฐ state transition์˜ ํ™•๋ฅ ์„ ๊ตฌํ•ด์„œ, ํ™•๋ฅ ์„ ํƒ‘๋‹ค์šด DP๋กœ ์ฐพ์•„์ฃผ๋ฉด ๋ฉ๋‹ˆ๋‹ค.
  • ์–ด๋–ค ํŠน์ • ์ข…์˜ ๋ชฌ์Šคํ„ฐ๊ฐ€ ์•„์˜ˆ ์—†์–ด์ง€๋ฉด ๋‘ ์ข…๋ฅ˜ ์ค‘์—๋Š” ํ•ญ์ƒ ์ด๊ธฐ๋Š” ์ชฝ์ด ์ •ํ•ด์ ธ ์žˆ์œผ๋ฏ€๋กœ ํ™•๋ฅ ์ด (1, 0, 0) ํ˜•ํƒœ๋กœ ๋‚˜์˜ต๋‹ˆ๋‹ค. ์ด๋ฅผ ๋ฒ ์ด์Šค ์ผ€์ด์Šค๋กœ ์“ฐ๋ฉด ๋ฉ๋‹ˆ๋‹ค.
  • ๋Œ€์นญ์„ฑ์„ ์ž˜ ์ด์šฉํ•˜๋ฉด $n^3$ ๊ฐœ์˜ ์‹ค์ˆ˜๊ฐ’๋งŒ์œผ๋กœ ๊ณ„์‚ฐํ• ์ˆ˜ ์žˆ๋Š”๊ฒƒ ๊ฐ™์€๋ฐ, ์ €๋Š” $p_1, p_2, p_3$ ์„ struct๋กœ ๋ฌถ์–ด์„œ ๋Œ๋ ธ์Šต๋‹ˆ๋‹ค.

์—ฐ์„ธ๋Œ€ํ•™๊ต 2018-C ๋‚˜๋ฌด ์œ„์˜ ์ž…์ž (BOJ 15669)

  • ๋‚œ์ด๋„ Platinum 5
  • ์ •์  U, V์— ๋Œ€ํ•ด, ํŽธ์˜์ƒ depth(u) < depth(v) ๋ผ๊ณ  ํ•ฉ์‹œ๋‹ค.
  • ์ด๋•Œ, v์˜ โ€˜์œ„์—์„œโ€™ ํ•˜๋‚˜, โ€˜์•„๋ž˜์„œโ€™ ํ•˜๋‚˜๋ฅผ ๊ณจ๋ผ์„œ ๊ทธ ๊ฑฐ๋ฆฌ๊ฐ€ ํ™€์ˆ˜/์ง์ˆ˜๊ฐ€ ๋˜๋Š” ์ •์ ์Œ ๊ฐœ์ˆ˜๋ฅผ ์„ธ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.
    • ๊ฐ€์žฅ ์‰ฌ์šด ๋ฐฉ๋ฒ•์€, dp[i] ์— i๋ฅผ ๋ฃจํŠธ๋กœ ํ•˜๋Š” ์„œ๋ธŒํŠธ๋ฆฌ์—์„œ ๊นŠ์ด๊ฐ€ ํ™€์ˆ˜/์ง์ˆ˜์ธ ์ ์˜ ๊ฐœ์ˆ˜๋ฅผ ๋ฏธ๋ฆฌ ์„ธ ๋†“๊ณ 
    • ๊ฑฐ๋ฆฌ๊ฐ€ ์ง์ˆ˜์ด๋ ค๋ฉด v ์•„๋ž˜ ์„œ๋ธŒํŠธ๋ฆฌ์—์„œ ์ง์ˆ˜ ๊นŠ์ด, v ์•„๋ž˜๊ฐ€ ์•„๋‹Œ ๊ณณ์—์„œ ์ง์ˆ˜ ๊นŠ์ด
    • ๋˜๋Š” ๋‘˜๋‹ค ํ™€์ˆ˜ ๊นŠ์ด์ธ ๋…ธ๋“œ๋“ค์˜ ๊ฐœ์ˆ˜์˜ ๊ณฑ์ž…๋‹ˆ๋‹ค.
  • ์—ญ์‹œ ์ฝ”๋“œ๊ฐ€ ์กฐ๊ธˆ๋” ๋ณด๊ธฐ ์‰ฌ์šด ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ๋ชจ๋“  ์ •๋ณด๋Š” DFS๋ฅผ ๋Œ๋ฆฌ๋ฉด์„œ Tree DP ํ•  ์ˆ˜ ์žˆ์–ด์„œ $O(n)$ ์— ํ•ด๊ฒฐ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.

์—ฐ์„ธ๋Œ€ํ•™๊ต 2018-L ์—ฐ์„ธ์›Œํ„ฐํŒŒํฌ (BOJ 15678)

  • ๋‚œ์ด๋„ Platinum 5
  • ํ•ต์‹ฌ์€ $D_i = \max_{i - d \leq j < i} (D_j + A_i)$ ๋ผ๋Š” DP์‹์ด๊ณ ,
  • ์ด ์‹์—์„œ $A_i$๋Š” ์ด๋ฏธ ์ •ํ•ด์ ธ ์žˆ์œผ๋ฏ€๋กœ $[i - d, i)$ ๊ตฌ๊ฐ„์˜ ์ตœ๋Œ“๊ฐ’์„ ๋นจ๋ฆฌ ๊ตฌํ• ์ˆ˜ ์žˆ์œผ๋ฉด ๋ฉ๋‹ˆ๋‹ค.
  • Deque DP Optimization์ด๋ผ๋Š” ๋ฐฉ๋ฒ•์„ ์ ์šฉํ•˜๋Š” ๊ธฐ๋ณธ ์—ฐ์Šต๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์ด ๋ฐฉ๋ฒ•์€ ์–ธ์  ๊ฐ€ ๋”ฐ๋กœ ์†Œ๊ฐœํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.
  • $n$ ์ด ์ž‘์•„์„œ ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ๋กœ $O(n \log n)$ ์—๋„ ํ’€ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

IOI 2002-4, Batch Scheduling (BOJ 5498)

  • ๋‚œ์ด๋„ Platinum 3
  • ์ง€๋ฌธ์ด ๊ต‰์žฅํžˆ ์ดํ•ดํ•˜๊ธฐ ์–ด๋ ต์Šต๋‹ˆ๋‹ค.
  • T ์˜ ๋ถ€๋ถ„ํ•ฉ์„ TS, F์˜ ๋ถ€๋ถ„ํ•ฉ์„ FS ๋ผ๊ณ  ์ƒ๊ฐํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.
  • ๋’ค์—์„œ๋ถ€ํ„ฐ ์—ญ์ˆœ์œผ๋กœ Batch๋ฅผ ๋งŒ๋“ค๋ฉด์„œ ์˜ค๋Š” ์‹์œผ๋กœ ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค.
    • Batch ๋ธ”๋ก ํ•˜๋‚˜๊ฐ€ i, i+1, ... j ๊ตฌ๊ฐ„์„ ์ปค๋ฒ„ํ•œ๋‹ค๋ฉด, t + s + (TS[j] - TS[i-1]) ์— (FS[j] - FS[i-1]) ์— ๊ณฑํ•ด์•ผ ํ•˜๋Š”๋ฐ, ๊ฐ ๋ธ”๋ก์˜ ์‹œ์ž‘์  t๋ฅผ ๋„์ €ํžˆ ๊ณ„์‚ฐํ•  ๋ฐฉ๋ฒ•์ด ์—†์Šต๋‹ˆ๋‹ค.
  • ์ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด, ์•ž ๋ธ”๋ก์—์„œ์˜ ์†Œ๋ชจ ์‹œ๊ฐ„์„ ๋’ท ๋ธ”๋ก์— ๊ณ„์† ๋”ํ•ด ์ฃผ๋Š” ์‹์œผ๋กœ, (s + (TS[j] - TS[i-1])) * (FS[n] - FS[i-1]) ๋กœ ๊ณ„์‚ฐํ•ด์„œ ๋”ํ•ด์ฃผ๋ฉด ๋ชจ๋“  ๋ธ”๋ก์„ ๋”ํ–ˆ์„๋•Œ ๊ฒฐ๊ณผ๊ฐ€ ๊ฐ™์Šต๋‹ˆ๋‹ค.
  • ๋”ฐ๋ผ์„œ ๋‹ค์Œ DP์‹์„ ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค. \(D_i = \min_{i \leq j} (D_j + (s + TS_{j} - TS_{i-1}) (FS_{n} - FS_{i-1}))\) ์ด ์‹์€ ๊ทธ๋ƒฅ ๊ณ„์‚ฐํ•˜๋ฉด $O(n^2)$ ๋ผ์„œ, ๋” ์ค„์ด๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค.
  • ์—ฌ๊ธฐ์„œ, $j$์™€ ๋ฌด๊ด€ํ•œ ํ•ญ์„ ๋‹ค min ๋ฐ–์œผ๋กœ ๋นผ์„œ ์ •๋ฆฌํ•˜๋ฉด, $D_j + TS_{j} \times u_i$ ๋“ค์˜ minimum์„ ๋น ๋ฅด๊ฒŒ ๊ณ„์‚ฐํ•˜๋Š” ๋ฌธ์ œ๊ฐ€ ๋ฉ๋‹ˆ๋‹ค ($u_i$๋Š” $i$์— ์˜ํ•ด ๊ฒฐ์ •๋˜๋Š” ์ƒ์ˆ˜๊ฐ’)
    • ์ด๋Ÿฌํ•œ DP๋ฅผ Convex Hull Trick์œผ๋กœ ๋น ๋ฅด๊ฒŒ ์ฒ˜๋ฆฌํ•  ์ˆ˜ ์žˆ์Œ์ด ์•Œ๋ ค์ ธ ์žˆ์Šต๋‹ˆ๋‹ค. $TS_{j}$์˜ ์„ฑ์งˆ์„ ๋งค์šฐ ์ž˜ ์ด์šฉํ•ด์„œ ์Šคํƒ์— ์ž˜ ์™”๋‹ค๊ฐ”๋‹คํ•˜๋Š” $O(n)$ ํ’€์ด๋„ ๊ฐ€๋Šฅํ•˜๊ณ โ€ฆ
    • Li-Chao Tree๊ฐ™์€ ๋†€๋ผ์šด (์ด์ œ ๋ฆฌ์ฐจ์˜ค๋Š” ๋ณ„๋กœ ๋†€๋ผ์šด๊นŒ์ง€๋Š” ์•„๋‹™๋‹ˆ๋‹ค) ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ๋ฐ•์œผ๋ฉด $O(n \log n)$ ์— ํ’€ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
    • Li-Chao Tree์— ๋Œ€ํ•ด์„œ๋Š” kjp4155๋‹˜์˜ ์†Œ๋ฉค ๊ธ€ ์ด ์ž˜ ์•Œ๋ ค์ ธ ์žˆ๊ณ , ๋ฌด์ง€์„ฑ ๋ณต๋ถ™ ๊ฐ€๋Šฅํ•œ ์ตœ๊ณ ์˜ ์ฝ”๋“œ์ž…๋‹ˆ๋‹ค.
    • ICPC์—๋„ ๋ช‡๋ฒˆ ๋‚˜์˜จ ์ž๋ฃŒ๊ตฌ์กฐ์ธ๋งŒํผ ํ•˜๋‚˜ ๊ฐ€์ง€๊ณ  ์žˆ์œผ๋ฉด ์ข‹์„๋“ฏ ํ•ฉ๋‹ˆ๋‹ค
  • ์ด์™€๋Š” ๋ณ„๋ก ์œผ๋กœ, ์ด ๋ฌธ์ œ๋Š” ๋ฌด๋ ค 20๋…„ ์ „์˜ ๋ฌธ์ œ๋ผ์„œ $O(n)$ ์ด ์ •ํ•ด์ด๋ฉด์„œ ($n \log n$ ๊นŒ์ง€๋Š” ํ—ˆ์šฉํ–ˆ๊ณ ) $n$์ด 1๋งŒ๋ฐ–์— ์•ˆ ๋ฉ๋‹ˆ๋‹ค. ์š”์ฆ˜์— ๋‚˜์˜จ๋‹ค๋ฉด 500๋งŒ์ด๋‚˜ ์ตœ์†Œ 100๋งŒ์œผ๋กœ ๋‚ด์ง€ ์•Š์•˜์„๊นŒ์š”? 500๋งŒ ๋ฆฌ์ฐจ์˜ค๋Š” ๋ถˆ๊ฐ€๋Šฅํ• ๊ฑฐ๊ณ , 100๋งŒ ๋ฆฌ์ฐจ์˜ค๋Š” ์ž˜ ๋ชจ๋ฅด๊ฒ ์Šต๋‹ˆ๋‹ค.
  • ์Šฌํ”„๊ฒŒ๋„, ์ด๊ฒƒ ๋•Œ๋ฌธ์— $O(n^2)$์˜ ๋‚˜์ด๋ธŒํ•œ DP๊ฐ€ 100ms๋Œ€๋กœ ํ†ต๊ณผํ•ฉ๋‹ˆ๋‹ค. ์„ธ์›”์˜ ํ๋ฆ„์ด ๋Š๊ปด์ง€๊ธฐ๋„ ํ•˜๋ฉด์„œ, ๋™์‹œ์— ๋งŒ์•ฝ ์ง€๊ธˆ๋ณด๋‹ค ์ปดํ“จํ„ฐ๊ฐ€ ๋‹ค์‹œ 10๋ฐฐ ๋นจ๋ผ์ ธ์„œ ์ง€๊ธˆ $O(n^2)$ ๊ฐ€ ์•ˆ ๋šซ๋ฆฌ๋Š” ๋ฌธ์ œ๋“ค์ด ๋‹ค ๋šซ๋ฆฌ๊ฒŒ ๋˜๋ฉด ๊ธฐ์กด ๋ฌธ์ œ๋“ค์„ ์˜จ๋ผ์ธ์ €์ง€ ์ƒ์—์„œ ๋ฆฌ๋งˆ์Šคํ„ฐํ•  ํ•„์š”๊ฐ€ ์žˆ์„์ˆ˜๋„ ์žˆ๊ฒ ๋‹ค, ํ•˜๋Š” (์ €์™€๋Š” ๋ณ„๋กœ ์ƒ๊ด€์—†๋Š” ์ผ์ด์ง€๋งŒ) ์ƒ๊ฐ๋„ ๋“ค๊ฒŒ ํ•˜๋„ค์š”.

JOI 2009-4 ๆ•ฃๆญฉ (BOJ 5573 ์‚ฐ์ฑ…)

  • ๋‚œ์ด๋„ Platinum 4
  • ์ด๋ฒˆ์ฃผ์— ์ œ๊ฐ€ ํฌ์ŠคํŒ…ํ•˜๋Š” ๋ฌธ์ œ์ค‘ ๊ฐ€์žฅ ์–ด๋ ค์› ์Šต๋‹ˆ๋‹ค.
  • $N-1$ ๋ฒˆ์งธ์˜ ๋ณด๋“œ ์ƒํƒœ๋ฅผ ์•Œ๊ณ  ์žˆ๋‹ค๋ฉด, $N$๋ฒˆ์งธ๋Š” ์ง์ ‘ ์‹œ๋ฎฌ๋ ˆ์ด์…˜ํ•ด์„œ ๋„์ฐฉํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  • ํŠน์ • ์นธ์— ์ง€๊ธˆ๊นŒ์ง€ ๋„๋‹ฌํ•œ ํšŸ์ˆ˜๋ฅผ ์•ˆ๋‹ค๋ฉด, ๊ทธ ์นธ์˜ ์ƒํƒœ๋ฅผ ์•Œ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  • $(1, 1)$ ์„ ๋ฐŸ๋Š” ํšŸ์ˆ˜๋Š” $N-1$๋ฒˆ์ž…๋‹ˆ๋‹ค.
  • ์–ด๋–ค ์นธ์„ ๋ฐŸ๋Š” ํšŸ์ˆ˜๊ฐ€ $K$๋ฒˆ์ด๋ฉด, ๊ณ„์† ์˜ค๋ฅธ์ชฝ๊ณผ ์•„๋ž˜๊ฐ€ ์™”๋‹ค๊ฐ”๋‹คํ•˜๋ฏ€๋กœ ๊ทธ์ค‘ ์ ˆ๋ฐ˜์€ ์˜ค๋ฅธ์ชฝ์œผ๋กœ, ์ ˆ๋ฐ˜์€ ์•„๋ž˜๋กœ ๋‚ด๋ ค๊ฐ€๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.
    • ๋‹จ, $K$๊ฐ€ ํ™€์ˆ˜์ด๋ฉด 0๋ฒˆ์งธ์— ์–ด๋Š ๋ฐฉํ–ฅ์ด์—ˆ๋Š”์ง€๋ฅผ ๋ณด๊ณ  ํ•œ๋ฒˆ ๋”๊ฐ€๋ฉด ๋ฉ๋‹ˆ๋‹ค.
    • ์ฆ‰, dp[i][j+1], dp[i+1][j] ์— dp[i][j]/2 ๋ฅผ (ํ•„์š”ํ•˜๋‹ค๋ฉด 1๋งŒํผ ๋”) ๋”ํ•ด์ฃผ๋ฉด ๋ฉ๋‹ˆ๋‹ค.
  • ์ด ์•„์ด๋””์–ด๊ฐ€ ๊ต‰์žฅํžˆ ๋– ์˜ฌ๋ฆฌ๊ธฐ ํž˜๋“ค์—ˆ์Šต๋‹ˆ๋‹ค. ์—ญ์‹œ DP๋Š” ์–ด๋ ต๋„ค์š”.