Back to : ps-weekly
Contents

May 10 - May 17, 2021.

Google Codejam 2021, Round 2

PS๋ฅผ ์‹œ์ž‘ํ•˜๊ณ  ์„ธ ๋ฒˆ์งธ Codejam์ด๋‹ค. ์ฒ˜์Œ์œผ๋กœ Round 3์— ์ง„์ถœํ•˜๊ณ  Codejam ํ‹ฐ์…”์ธ ๋ฅผ ์–ป์—ˆ๋‹ค.

์ˆœ์œ„๋Š” 855๋“ฑ์œผ๋กœ, ๊ฑฐ์˜ ๋ง‰์ฐจ๋ฅผ ํƒ”์ง€๋งŒ ์•„๋ฌดํŠผ ํ‹ฐ์…”์ธ ๋ฅผ ๋ฐ›์•˜๋‹ค๋Š” ์‚ฌ์‹ค์ด ๋งค์šฐ ๊ณ ๋ฌด์ ์ด๋‹ค (?)

๋‚˜๋ฆ„๋Œ€๋กœ ์ค‘์š”ํ•œ ๋Œ€ํšŒ์ด๋ฏ€๋กœ ๋ณ„๋„๋กœ ํฌ์ŠคํŒ…ํ•˜๊ธฐ๋กœ ํ•œ๋‹ค.

[Virtual] Google Codejam 2018, Round 2

Codejam์„ ๋Œ€๋น„ํ•˜๊ธฐ ์œ„ํ•ด ์˜์›ํ•œ ํŒฝ๋„๋ฆฌ๋“ค dhdroid, dlwocks31 ๊ณผ ํ•จ๊ป˜ 2018 Round 2๋ฅผ virtual๋กœ ๋Œ์•˜๋‹ค. ๋งŽ์€ ๋ถ€์กฑํ•จ์„ ๋Š๊ผˆ๋‹ค.

Falling Balls

๋‚˜๋ฆ„๋Œ€๋กœ ์žฌ๋ฐŒ๋Š” Greedy construction ๋ฌธ์ œ์ด๋‹ค. ๋จผ์ €, /๊ณผ \์— ๋Œ€ํ•œ ์กฐ๊ฑด์œผ๋กœ๋ถ€ํ„ฐ, ์‹œ์ž‘ํ•˜๋Š” ๊ณต๋“ค์ด ๊ต์ฐจํ•ด์„œ ์›€์ง์ด์ง€ ๋ชปํ•จ์„ ๊ด€์ฐฐํ•˜์ž. ๊ทธ๋Ÿฌ๊ณ  ๋‚˜๋ฉด ๊ฒฐ๊ตญ ์™ผ์ชฝ์—์„œ $k$๋ฒˆ์งธ๋ผ๋Š” ๊ณต์˜ ์ƒ๋Œ€์  ์œ„์น˜๊ฐ€ ์ž˜ ๋ณด์กด๋˜๋ฏ€๋กœ, ์–ด๋Š ๊ณต์ด ์–ด๋””๋กœ ๊ฐ€์•ผ ํ•˜๋Š”์ง€๋ฅผ ์ •ํ™•ํ•˜๊ฒŒ ์•ˆ๋‹ค. ์ด๋ฅผ ๋งž์ถ”์–ด constructํ•˜๊ธฐ๋Š” ์–ด๋ ต์ง€ ์•Š๋‹ค.

Graceful Chainsaw Jugglers (small)

$O(n^4)$ ์˜ ์ž๋ช…ํ•œ DP๋ฅผ ์ด์šฉํ•˜์—ฌ small์„ ๊ธ์—ˆ๊ณ , ์–ด๋–ป๊ฒŒ๋“  ์ด๋ฅผ ์ค„์—ฌ๋ณด๋ ค๊ณ  ์ด๋ฆฌ์ €๋ฆฌ ๋งŽ์€ ๊ณ ๋ฏผ์„ ํ–ˆ์ง€๋งŒ ์„ฑ๊ณตํ•˜์ง€ ๋ชปํ–ˆ๋‹ค.

๋๋‚˜๊ณ  dhdroid ์˜ ์†”๋ฃจ์…˜์„ ๋“ค์—ˆ๋Š”๋ฐ, DP์˜ ์ฐจ์›์„ ์ค„์ด๋Š” ์•„์ด๋””์–ด๊ฐ€ ์ƒ๋‹นํžˆ ๋งค๋ ฅ์ ์ด๋‹ค. ๋ญ”๊ฐ€ ํ˜•ํƒœ์ ์œผ๋กœ ์ž์ฃผ ๋ณด์ด๋Š” DP์ธ ๋“ฏ ํ•จ์—๋„ ๋– ์˜ฌ๋ฆฌ์ง€ ๋ชปํ•œ ์ ์€ ์ข€ ์•„์‰ฝ๋‹ค. ํ’€์ด์—๋Š” $O(n^{8/3})$ ์˜ ๋†€๋ผ์šด ํ’€์ด๊ฐ€ ์ ํ˜€ ์žˆ์œผ๋‚˜, $O(n^3)$ ๋„ ๋ฌธ์ œ ํ•ด๊ฒฐ์— ์•„๋ฌด๋Ÿฐ ์ง€์žฅ์ด ์—†๊ณ  ํ›จ์”ฌ ๋– ์˜ฌ๋ฆฌ๊ธฐ ์‰ฝ๋‹ค.

Costume Change

์ค‘์š”ํ•œ ํฌ์ธํŠธ ํ•˜๋‚˜๋Š”, ์‚ฌ์‹ค ์ƒ‰๊น”์€ ์ถฉ๋ถ„ํžˆ ๋งŽ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค. ์ฆ‰, ํ˜„์žฌ์˜ โ€˜ํŠน๋ณ„ํ•˜์ง€ ์•Š์Œโ€™ ์ด๋ผ๋Š” ์ด์Šˆ๋งŒ resolveํ•˜๋ฉด ๋œ๋‹ค.

์–ด๋–ค $n \times n$ ๊ทธ๋ฆฌ๋“œ ์ƒ์—์„œ, $k$๊ฐœ์˜ ์ ๋“ค์ด ๋†“์—ฌ ์žˆ์„ ๋•Œ, ์ด์ค‘์˜ subset์„ ์Šค๋„์ฟ ์Šค๋Ÿฝ๊ฒŒ ๋ฝ‘๋Š” ๋ฐฉ๋ฒ• (๊ฐ ํ–‰์— ํ•˜๋‚˜, ๊ฐ ์—ด์— ํ•˜๋‚˜ ์ดํ•˜๋ฅผ ์œ ์ง€ํ•˜๋Š” ๋ฐฉ๋ฒ•) ์€ ๋น„๊ต์  well-known์ด๋‹ค. ํ–‰์„ ํ‘œํ˜„ํ•˜๋Š” ์ •์  $n$๊ฐœ์™€ ์—ด์„ ํ‘œํ˜„ํ•˜๋Š” ์ •์  $n$๊ฐœ๋ฅผ ๋งŒ๋“ค๊ณ , $(i, j)$ ์— ์ ์ด ๋†“์—ฌ ์žˆ์Œ์„ $r_i \to c_j$ ๊ฐ„์„ ์œผ๋กœ ํ‘œํ˜„ํ•œ ๋‹ค์Œ, ์ด๋“ค๊ฐ„์˜ maximum bipartite matching์„ ์ฐพ์œผ๋ฉด ๋œ๋‹ค. ์ด๊ฒƒ๋งŒ ์ฐพ๋Š” ๋ฐฉ๋ฒ•์€ ์ข‹์€ ๋ฐฉ๋ฒ•์ด ๋งŽ์ด ์žˆ์ง€๋งŒ, ๋ฌด์ง€์„ฑ ํ”Œ๋กœ์šฐ๊ฐ€ ๊ฐ€์žฅ ์‰ฝ๊ฒŒ ๊ตฌํ˜„ํ• ์ˆ˜ ์žˆ๋‹ค.