Back to : cp-rounds
Contents

์˜ฌํ•ด Codejam์˜ (๋‚˜ํ•œํ…Œ ์žˆ์–ด) ์‚ฌ์‹ค์ƒ ๋งˆ์ง€๋ง‰ round์ด๋ฏ€๋กœ (R3 ๋Š” ์žฌ๋ฐŒ๊ฒŒ ํ•˜๊ฒ ์ง€๋งŒ competition์œผ๋กœ์จ๋Š” ์–ป์„๊ฒŒ ์—†๋‹ค) Hashcode ๋•Œ์ฒ˜๋Ÿผ prep๊ณผ ๊ณผ์ •์„ ์ข€ ์ ์–ด๋ณด๋ ค๊ณ  ํ•œ๋‹ค. ์•ž์œผ๋กœ ๋ฉ”์ด์ €ํ•œ ๋Œ€ํšŒ๋Š” ์ด๋ ‡๊ฒŒ ์ ์–ด๋ณผ ์ƒ๊ฐ์ด๋‹ค.

Preperation

๊ทธ๋ ‡๊ฒŒ ๋งํ•˜๊ธด ํ–ˆ์ง€๋งŒ ์ค€๋น„ํ• ์ˆ˜ ์žˆ์—ˆ๋˜๊ฑด ๋”ฑํžˆ ์—†๋‹ค. ์˜ฌํ•ด๋Š” CP์— ์“ฐ๊ธฐ์—๋Š” ๋„ˆ๋ฌด ํ• ์ผ์ด ๋งŽ๋‹ค.

๋ฐฉํ•™๋•Œ๋ฉด ๋ชจ๋ฅผ๊นŒโ€ฆํ•™๊ธฐ์ค‘์— PS/CP์— ๋งŽ์€ ์‹œ๊ฐ„์„ ํˆฌ์žํ•˜๊ธฐ์—๋Š” ์•„๋ฌด๋ž˜๋„ ์–ด๋ ค์›€์ด ๋งŽ๋‹ค. ๊ทธ๋ž˜๋„ ์ž‘๋…„ ์ฝ”๋“œ์žผ๊ณผ ์ง€๊ธˆ ๋น„๊ตํ–ˆ์„๋•Œ (PS์ ์ธ ์ธก๋ฉด์—์„œ) ์–ด๋–ค ์ ๋“ค์ด ๋‚˜์•„์กŒ๋Š”์ง€ / ๋‚˜์•„์ง€์ง€ ์•Š์•˜๋Š”์ง€ ๋น„๊ตํ•ด๋ณด๋ฉด ์ค€๋น„๋ฅผ ๋˜์ƒˆ๊ธฐ๋Š” ์ธก๋ฉด์—์„œ ์กฐ๊ธˆ์€ ๋„์›€์ด ๋ ๊ฒƒ ๊ฐ™๊ธฐ๋„ ํ•˜๋‹ค.

  • Courses. Problem solving์€ ๊ฒฐ๊ตญ ์•„์ด๋””์–ด์™€ ์ง€์‹์ด ๋‘˜ ๋‹ค ํ•„์š”ํ•œ๋ฐ, ๋ช‡๋ช‡ ๋‚ด์šฉ๋“ค - ์ž‘๋…„ 1ํ•™๊ธฐ์— ๋“ค์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜, ์ง€๊ธˆ ๋“ฃ๊ณ ์žˆ๋Š” ์ •์ˆ˜๋ก  ๋“ฑ - ์€ ๋„์›€์ด ๋˜๋Š”๊ฑด ์‚ฌ์‹ค์ด๋‹ค. ๋Œ€์ถฉ ๋‹ค ์•„๋Š” ๋‚ด์šฉ์ด๊ธด ํ–ˆ์ง€๋งŒ ํ˜ผ์ž์„œ๋Š” ์ ˆ๋Œ€ ํ•˜์ง€ ์•Š์„ revisit์„ ๋‹ค์‹œ ํ•ด๋ณด๋Š”๊ฑด ๋ถ„๋ช…ํžˆ ์˜๋ฏธ๊ฐ€ ์žˆ๋‹ค. Generalํ•˜๊ฒŒ, ์ •์ˆ˜๋ก  ๊ฐ™์€ ํŒŒํŠธ๋“ค์€ ์ง€์‹์ ์ธ ์ธก๋ฉด๋ณด๋‹ค๋Š” ๊ทธ๋ƒฅ ๊ณ ๋ฏผํ•ด๋ณด๋Š” ์‹œ๊ฐ„์„ ๊ฐ–๋Š”๊ฒŒ ์˜๋ฏธ๊ฐ€ ์žˆ๋‹ค๊ณ  ์ƒ๊ฐํ•œ๋‹ค.

  • C++ ๊ตฌํ˜„๋Šฅ๋ ฅ์€ ์˜คํžˆ๋ ค ์ž‘๋…„๋งŒ ๋ชปํ•˜๋‹ค. 2ํ•™๊ธฐ ์†Œ๊ฐœ์›์‹ค์ด ๋ถ„๊ธฐ์ ์ด ๋˜์–ด์„œ ๊ทธ๋Ÿฐ๊ฑฐ ๊ฐ™์€๋ฐ, ๋Œ์•„์˜ค๋ ค๋ฉด ์•„์ง ๋ฉ€์—ˆ๋‹ค๊ณ  ์ƒ๊ฐํ•œ๋‹ค. 2019๋…„ ICPC ๋•Œ ํŒ€์›๋“ค์ด ๊ต‰์žฅํžˆ ๊ตฌํ˜„์„ ํž˜๋“ค์–ดํ•ด์„œ ์•„๋‹ˆ ๋ฉ€์ฉกํ–ˆ๋˜ ์‚ฌ๋žŒ๋“ค์ด ์™œ์ด๋Ÿฌ๋‚˜ ์‹ถ์—ˆ๋Š”๋ฐ, ๋Œ€์ถฉ ์™œ๊ทธ๋Ÿฐ์ง€ ์•Œ๊ฑฐ ๊ฐ™๊ธฐ๋„ ํ•˜๋‹ค.

  • ๊ทธ๋™์•ˆ CF rating์€ ๋‹ต๋ณด๋ฅผ ๊ฑฐ๋“ญํ–ˆ๋Š”๋ฐ, ํ•œ๋ฌธ์ œ ์žก๊ณ  ํ‘ธ๋Š” ๋Šฅ๋ ฅ์€ ์ž‘๋…„์— ๋น„ํ•ด ๋‚˜์•„์กŒ๋‹ค๊ณ  ์ƒ๊ฐํ•œ๋‹ค. dhdroid ๊ฐ™์€ ๊ฒฝ์šฐ์—๋Š” ๋น ๋ฅธ ์ฝ”๋”ฉ ์‹ค๋ ฅ์„ ๊ฐ–์ถ”์ง€๋Š” ๋ชปํ–ˆ์ง€๋งŒ ์–ด๋ ค์šด ๋ฌธ์ œ๋ฅผ ๊ณ ๋ฏผํ•˜๋ฉด ๋‚˜๋ณด๋‹ค ํ›จ์”ฌ ์ฒด๊ณ„์ ์œผ๋กœ ๊ด€์ฐฐ์„ ์Œ“์•„๋‚˜๊ฐ€๋Š” ๋Šฅ๋ ฅ์ด ์žˆ๋Š”๋ฐ, ๊ฐ™์ด ๊ณต๋ถ€ํ•˜๋ฉด์„œ ์ด๋Ÿฐ๊ฑธ ๋งŽ์ด ๋ฐฐ์› ๋‹ค.

Preliminary & Round 1

  • Preliminary๋Š” 30์  ์ ˆ๋Œ€ํ‰๊ฐ€ ํ˜•์‹์ด๋ฏ€๋กœ ์นดํŽ˜์— ์•‰์•„์„œ ๊ทธ๋ƒฅ ๋Œ€์ถฉ ์•ž ๋ช‡๋ฌธ์ œ๋งŒ ๋‚ด๋ณด๊ณ  ๋˜์กŒ๋‹ค. ๊ทธ๋•Œ ๊ฝค ๋ฐ”์œ ์ผ์ •๋“ค์ด ์žˆ์—ˆ๊ธฐ ๋•Œ๋ฌธ์—โ€ฆ
  • Round 1์€ ๋ญ”๊ฐ€ ํ•ญ์ƒ R1B๋ฅผ ์น˜๊ฒŒ ๋˜๋Š” ๊ธฐ๋ถ„์ด๋‹ค.

Problem 1 : Minimum Sort

Easy. ๋ฐ”๋กœ ๋– ์˜ค๋ฅด๋Š” Naive ํ’€์ด๋ฅผ ๊ทธ๋ƒฅ ๊ตฌํ˜„ํ•˜๋ฉด ๋œ๋‹ค.

[1, 100] ์ค‘ ๊ฐ€์žฅ ์ž‘์€๊ฑธ ๋ฝ‘๊ณ , ๋งจ ์•ž์œผ๋กœ ๋ณด๋‚ธ ๋‹ค์Œ, [2, 100] ์ค‘ ๊ฐ€์žฅ ์ž‘์€๊ฑธ ๋ฝ‘๊ณ โ€ฆ. ์ด๋ ‡๊ฒŒ ํ•˜๋ฉด ์†Œ๋ชจํ•˜๋Š” ์ฝ”์ธ ์ˆ˜๋Š” $1/2 + 1/3 + \dots 1/100$ ๊ฐœ ์ •๋„์ด๊ณ , ์ด ๊ฐ’์€ 6๋ณด๋‹ค ์ž‘์œผ๋ฏ€๋กœ ์ด๋Œ€๋กœ ์งœ์„œ ๋‚ด๋ฉด ๋œ๋‹ค.

Problem 2 : Matrygons

$K$๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ, ์„ ๋งŒ์กฑํ•˜๋Š” distinctํ•œ ์ˆ˜์—ด $x_1, x_2, \dots x_N$ ์ค‘ $N$์ด ์ตœ๋Œ€์ธ ์ˆ˜์—ด์„ ์ฐพ๋Š” ๋ฌธ์ œ.์กฐ๊ฑด>

  • $\sum_{i = 1}^{N} x_i = K$ ์—ฌ์•ผ ํ•˜๋ฉฐ
  • $x_1$ ์ด $x_2$์˜ ์•ฝ์ˆ˜, $x_2$๊ฐ€ $x_3$์˜ ์•ฝ์ˆ˜โ€ฆ. $x_N$ ๊นŒ์ง€ ์ด๋ฅผ ๋งŒ์กฑํ•ด์•ผ ํ•œ๋‹ค.

๋จผ์ €, $K$ ๊ฐ€ $x_1$ ์˜ ๋ฐฐ์ˆ˜์ž„์„ ์‰ฝ๊ฒŒ ๊ด€์ฐฐํ•  ์ˆ˜ ์žˆ๋‹ค. ๋˜ํ•œ, $K - x_1$ ์€ $x_2$์˜ ๋ฐฐ์ˆ˜์ด๊ณ โ€ฆ ์ด๋ฅผ ๋ฐ˜๋ณตํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ๊ฒƒ์ด ์ฒซ๋ฒˆ์งธ ๊ด€์ฐฐ์ด๋‹ค.

๋‘๋ฒˆ์งธ๋กœ, $N$์ด reasonableํ•˜๊ฒŒ ์ž‘์Œ์„ ๊ด€์ฐฐํ•˜์ž. $2x_i \leq x_{i+1}$ ์ž„์„ ํ™•์ธํ•  ์ˆ˜ ์žˆ๋Š”๋ฐ (๋ฐฐ์ˆ˜์—ฌ์•ผ ํ•˜๊ณ , ๊ฐ™์œผ๋ฉด ์•ˆ ๋˜๋ฏ€๋กœ) ์ด๋ฅผ ๋ณด๋ฉด, $N$์€ ๋งŽ์•„์•ผ $\log K$, 30 ์ •๋„์ด๋‹ค.

์ด ๋‘๊ฐ€์ง€๋ฅผ ์ด์šฉํ•˜๋ฉด, $f(k, t)$ ๋ฅผ โ€œํ˜„์žฌ $x = t$, $K = k$์ผ ๋•Œ $x$ ๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ด์„œ ์ˆ˜์—ด์„ ๋งŒ๋“ค์–ด์„œ $k$๋ฅผ ๋งŒ๋“ค๊ณ ์ž ํ•  ๋•Œ, ์ตœ๋Œ€์˜ $N$๊ฐ’โ€ ์œผ๋กœ ์ •์˜ํ•˜๋ฉด $f(k, t)$ ๋ฅผ ์žฌ๊ท€์ ์œผ๋กœ ๊ฝค ๋น ๋ฅด๊ฒŒ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ๋‹ค. ์„ค๋ช…ํ•˜๊ธฐ๊ฐ€ ๊ต‰์žฅํžˆ ๊นŒ๋‹ค๋กญ์ง€๋งŒ ์ฝ”๋“œ๋Š” ๋งค์šฐ ๊ฐ„๋‹จํ•˜๋ฏ€๋กœ ์•„๋ž˜ ์ฝ”๋“œ๋ฅผ ์ฐธ๊ณ ํ•˜์ž.

์ฃผ์˜ํ•  ์ ์€, 1๊ฐํ˜•์ด๋‚˜ 2๊ฐํ˜•์€ ์—†์œผ๋ฏ€๋กœ ์ฒ˜์Œ์—๋Š” 3๊ฐํ˜• ์ด์ƒ์œผ๋กœ ์‹œ์ž‘ํ•ด์•ผ ํ•จ์„ ์ฃผ์˜ํ•˜์ž. (์ด๊ฑธ๋กœ 1ํ‹€ํ–ˆ๋‹คโ€ฆ)

๋ผ์šด๋“œ๊ฐ€ ๋๋‚˜๊ณ  dhdroid ์™€ discussionํ–ˆ๋Š”๋ฐ ์—ญ์‹œ DPํ™ฉ๋‹ต๊ฒŒ ๋‚˜๋ณด๋‹ค ํ›จ์”ฌ ์ข‹์€ DP ์†”๋ฃจ์…˜์„ ๊ฐ€์ ธ์™”๋‹ค. :fan:

Problem 3 : Hidden Pancakes

์ด ๋ฌธ์ œ์˜ ๊ฒฝ์šฐ, ์ฃผ์–ด์ง„ ๋ฌธ์ œ ์ƒํ™ฉ์„ ์ž˜ ์ด์šฉํ•˜๋ฉด โ€œ$i$ ๋ฒˆ์ด $j$๋ฒˆ๋ณด๋‹ค ํฌ๋‹ค/์ž‘๋‹คโ€ ํ˜•ํƒœ์˜ ์ •๋ณด๋ฅผ ๋งŽ์ด ์–ป์„ ์ˆ˜ ์žˆ๋‹ค. ์ด๋Ÿฌํ•œ ์ •๋ณด๋“ค์ด consistent ํ•˜๋‹ค๋ฉด, transitivity์— ์˜ํ•ด imply๋˜๋Š” ์ •๋ณด๋“ค์„ ์ œ์™ธํ•จ์œผ๋กœ์จ Directed tree๋ฅผ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, ์˜ˆ์ œ 2๋Š” 1 1 2 ์ธ๋ฐ, ์ด๋ฅผ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๋ณผ ์ˆ˜ ์žˆ๋‹ค.

  • ์ฒ˜์Œ์—๋Š” <1> ์ด ๋ณด์ด๋Š” ์ƒํ™ฉ์ด๋‹ค.
  • 1 ๋‹ค์Œ์— 1์ด ์˜จ ์‹œ์ ์—์„œ, ๋ณด์ด๋Š”๊ฒŒ 1๊ฐœ์ด๋ฏ€๋กœ ํ˜„์žฌ ๋ณด์ด๋Š” ๊ฒƒ์€ <2> ์ด๋‹ค. 2๋ฒˆ์ด 1๋ฒˆ์„ ์Šคํƒ์—์„œ ์ซ“์•„๋ƒˆ์œผ๋ฏ€๋กœ, 2๋ฒˆ์ด 1๋ฒˆ๋ณด๋‹ค ํฌ๋‹ค.
  • ๊ทธ๋‹ค์Œ 2๊ฐœ๊ฐ€ ๋ณด์ด๋ฏ€๋กœ <2, 3> ์ด๋‹ค. 3๋ฒˆ์ด 2๋ฒˆ์„ ์ซ“์•„๋‚ด์ง€ ๋ชปํ–ˆ์œผ๋ฏ€๋กœ 2๋ฒˆ์ด 3๋ฒˆ๋ณด๋‹ค ํฌ๋‹ค.

์ด๋ฅผ ํŠธ๋ฆฌ๋กœ ๊ทธ๋ฆฌ๋ฉด 2๋ฒˆ์ด ๋ฃจํŠธ๊ฐ€ ๋˜๊ณ , 1๋ฒˆ๊ณผ 3๋ฒˆ์ด 2๋ฒˆ์˜ child node์ธ ํŠธ๋ฆฌ๊ฐ€ ๋œ๋‹ค.

๊ฐ™์€ ๋ฐฉ๋ฒ•์œผ๋กœ, ์˜ˆ์ œ 1์ธ 1 2 2 1 ์„ ๋ณด์ž.

  • ์ฒ˜์Œ์—๋Š” <1> ์ด ๋ณด์ด๋Š” ์ƒํ™ฉ์ด๋‹ค.
  • ๋‘๋ฒˆ์งธ ์‹œ์ ์˜ ์Šคํƒ์€ <1, 2> ์ด๋ฏ€๋กœ 1์ด 2๋ณด๋‹ค ํฌ๋‹ค.
  • ์„ธ๋ฒˆ์งธ ์‹œ์ ์˜ ์Šคํƒ์€ <1, 3> ์ธ๋ฐ, ์Šคํƒ์—์„œ 3์ด 2๋ฅผ ์ซ“์•„๋ƒˆ์œผ๋ฏ€๋กœ 3์ด 2๋ณด๋‹ค ํฌ๋‹ค. ๋˜ํ•œ, 3์ด 1๋ณด๋‹ค๋Š” ์ž‘๋‹ค.
  • ๋งˆ์ง€๋ง‰ ์‹œ์ ์—์„œ <4> ๊ฐ€ ๋ชจ๋‘ ์ซ“์•„๋ƒˆ์œผ๋ฏ€๋กœ 4๊ฐ€ 1๋ณด๋‹ค ํฌ๋‹ค.

๋”ฐ๋ผ์„œ, 4 > 1 > 3 > 2 ์ž„์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค. ์ด๋ฅผ ํŠธ๋ฆฌ๋กœ ๊ทธ๋ฆฌ๋ฉด ํ•œ ์ค„๋กœ ์ญ‰ ์ด์–ด์ง„ ํŠธ๋ฆฌ๊ฐ€ ๋œ๋‹ค.

์ด๋ ‡๊ฒŒ ํŠธ๋ฆฌ๋ฅผ ๊ทธ๋ฆฌ๊ณ  ๋‚˜๋ฉด, ์ด โ€œํŠธ๋ฆฌ๊ฐ€ ์ œ๊ณตํ•˜๋Š” partial orderโ€๋ฅผ ๊นจ์ง€ ์•Š์œผ๋ฉด์„œ $n$๊ฐœ์˜ ํŒฌ์ผ€์ต ํฌ๊ธฐ๋ฅผ ์ •ํ•˜๋Š” ๋ฌธ์ œ๊ฐ€ ๋˜๋Š”๋ฐ, ์ด๋Š” ๋‹ค์‹œ ๋งํ•˜๋ฉด 1, 2, โ€ฆ $n$์„ ๊ฐ ํŠธ๋ฆฌ ๋…ธ๋“œ์— ์จ๋„ฃ๋˜ topological order๋ฅผ ๊นจ์ง€ ์•Š๋Š” permutation์˜ ๊ฐœ์ˆ˜๋ฅผ ์ฐพ๋Š” ๋ฌธ์ œ๊ฐ€ ๋œ๋‹ค.

์ด๋Š” ์ฆ‰, ํ˜„์žฌ ์ฃผ์–ด์ง„ ํŠธ๋ฆฌ์˜ ์ ๋ฒ•ํ•œ topological order์˜ ๊ฐœ์ˆ˜๋ฅผ ์„ธ๋Š” ๋ฌธ์ œ์™€ ๊ฐ™๋‹ค. ์ด ๋ฌธ์ œ๋Š” ๋‚˜๋ฆ„๋Œ€๋กœ well-known ์ด๋ฏ€๋กœ, ์•ฝ๊ฐ„ ๊ตฌ๊ธ€๋งํ•ด๋ณด๋ฉด Tree DP ๋กœ ์ด๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์ฐพ์„ ์ˆ˜ ์žˆ๋‹ค. ์•ณ์ฝ”๋”์— ๋ฌธ์ œ๋กœ๋„ ๋‚˜์˜จ ์  ์žˆ๋‹ค. ๋ฌธ์ œ ๋งํฌ

๋ถ„๋ช… ์ € ์•ณ์ฝ”๋” ๋ฌธ์ œ๋ฅผ ํ’€๋•Œ๋Š” ์ƒ๊ฐ์„ ํ•ด์„œ ($O(n \log n)$์ด๊ธด ํ–ˆ์ง€๋งŒ ์ด๊ฑธ ํ˜ผ์ž ์ฐพ์•„๋ƒˆ์—ˆ๋Š”๋ฐ, ์™œ์ธ์ง€ ๋ชจ๋ฅด๊ฒ ์ง€๋งŒ ๋ผ์šด๋“œ ๋•Œ๋Š” ์ €๋Ÿฐ ์ƒ๊ฐ์„ ์ „ํ˜€ ๋ชปํ–ˆ๋‹ค. :( Tree DP๋Š” ํ•ญ์ƒ ๋„ˆ๋ฌด ์–ด๋ ค์šด๋“ฏโ€ฆ)

Round ์ดํ‰

์˜ฌํ•ด์˜ ์ฒซ ๋ฉ”์ด์ € ๋Œ€ํšŒ์ธ๋ฐ ๋‚˜๋ฆ„ ์žฌ๋ฐŒ์—ˆ๋‹ค. ์ž‘๋…„์ด๋‚˜ ์žฌ์ž‘๋…„ Round 2์— ๋น„ํ•˜๋ฉด ์กฐ๊ธˆ ์‰ฌ์›Œ์ง„๋“ฏํ•œ๋ฐ, ์–ด์ฐจํ”ผ ์ƒ๋Œ€ํ‰๊ฐ€๋‹ˆ๊นŒ ํฐ ์˜๋ฏธ๋Š” ์—†์„ ์ˆ˜๋„โ€ฆ

1000๋“ฑ์ด๋ผ๋Š” ์ปคํŠธ๋ฅผ ์ •ํ•ด๋†“๊ณ  ์‹œ์ž‘ํ•˜๋Š” ๋ผ์šด๋“œ๋‹ค ๋ณด๋‹ˆ 66์ ์„ ๋ฐ›์€ ์‹œ๊ฐ„์œผ๋กœ ๊ฐˆ๋ฆด์ˆ˜๋ฐ–์— ์—†๋Š”๋ฐ, ๊ทธ๋ž˜๋„ ๋‹คํ–‰ํžˆ ๋ง‰ ์ฒซ ํƒœ์Šคํฌ ๋นจ๋ฆฌํ‘ผ ์‹œ๊ฐ„ ์ด๋Ÿฐ์‹์œผ๋กœ ๊ฐˆ๋ฆฐ speed์ค‘์‹ฌ์˜ ๋Œ€ํšŒ๋Š” ์•„๋‹ˆ๋ผ์„œ ์•ฝ๊ฐ„ ๋‹คํ–‰์ด๋‹ค. ๊ฐ„๋‹จํ•œ ์•„์ด๋””์–ด / DP / ํŠธ๋ฆฌ DP ๋ผ๋Š” ์ฒซ 3๋ฌธ์ œ์˜ ์„ธํŒ…๋„ reasonableํ–ˆ๋‹ค๊ณ  ๋ณด๊ณ โ€ฆ

R3๋„ ์žฌ๋ฐŒ๊ฒŒ ์น˜๊ณ  ํ›„๊ธฐ์ •๋„๋Š” ์˜ฌ๋ฆด ๊ณ„ํš์ด๋‹ค :P