Back to : cp-rounds
Contents

๋ฉค๋ฒ„๊ฐ€ ์กฐ๊ธˆ์”ฉ ๋ฐ”๋€Œ๋ฉด์„œ ์ง€๋‚œ 3๋…„๊ฐ„ UCPC, ICPC, HashCode ๋“ฑ์„ ํ•จ๊ป˜ํ•ด์˜จ ํŒ€ Little Piplup์œผ๋กœ ์ด๋ฒˆ์—๋Š” ๋‹ค์‹œ ์ œ๊ฐ€ ์ฐธ์—ฌํ•˜๊ฒŒ ๋˜์—ˆ์Šต๋‹ˆ๋‹ค.

์ด ํŒ€์€ 2019๋…„ ์ €์™€ Coffeetea, DHDroid๋กœ ์‹œ์ž‘ํ•ด์„œ PS ๊ณต๋ถ€๋„ ๊ฐ™์ด ํ•˜๊ณ , ๋งŽ์€ ๋Œ€ํšŒ๋ฅผ ๋›ฐ๋ฉด์„œ ๋‚˜๋ฆ„ ํ–‰๋ณต PS ํ•ด์˜จ ํŒ€์ž…๋‹ˆ๋‹ค. 2020๋…„์—๋Š” Hashcode๋ฅผ ๊ธฐ์ ์œผ๋กœ ์ €๋ž‘ ๊ทธ์ „๊นŒ์ง€ ๊ฐ™์ด ์—ฐ์Šต์…‹์„ ๋งŽ์ด ๋Œ์•˜๋˜ Dlwocks31์ด ๋“ค์–ด์™€์„œ 4๋ช…์ด ๋˜์—ˆ์Šต๋‹ˆ๋‹ค.

Hashcode๋Š” 4์ธํŒ€์ด์ง€๋งŒ, UCPC์™€ ICPC๋Š” 3์ธ 1ํŒ€์ž…๋‹ˆ๋‹ค. ๋˜ํ•œ, ICPC์˜ ๊ฒฝ์šฐ ํœดํ•™์ƒ์ด ๋ณธ์„ ์— ์ง„์ถœํ• ์ˆ˜ ์—†๋‹ค๋Š” ๊ทœ์ •์ด ์žˆ๋Š”๋ฐ ์ด ํŒ€์€ ์ €๋ฅผ ์ œ์™ธํ•œ 3๋ช…์ด ๋ชจ๋‘ ํœดํ•™์ƒ (๋ณ‘ํŠน ์ค‘)์ด๋ผ 2020 ICPC์—์„œ๋Š” ์ž์—ฐ์Šค๋Ÿฝ๊ฒŒ ์ œ๊ฐ€ ๋‹ค๋ฅธ ํŒ€์„ ์ฐพ์•„ ๋‚˜๊ฐ€๊ณ  3๋ช…์ด์„œ Army Piplup ์„ ๊ตฌ์„ฑํ•ด์„œ ๋‚˜๊ฐˆ ์ˆ˜ ์žˆ์—ˆ๊ณ , 2020 UCPC๋Š” dlwocks31์ด ๋‹ค๋ฅธ ํŒ€์›๋“ค์ด๋ž‘ ์ถœ์ „ํ–ˆ์—ˆ์Šต๋‹ˆ๋‹ค. 2021 UCPC๋Š”โ€ฆ 2๋ช… 2๋ช…์„ ๊ฐ€๋ฅด๊ณ  ํ•œ๋ช…์”ฉ์„ ๋” ์˜์ž…ํ–ˆ๋Š”๋ฐ, ์ €๋ž‘ dlwocks31์ชฝ์€ ์–ด๋ฆฌ์„์€ ์‹ค์ˆ˜๋กœ ๋Œ€ํšŒ๋ฅผ ์น˜๋ฅด์ง€ ๋ชปํ–ˆ์—ˆ์Šต๋‹ˆ๋‹ค.

์ด๋ฒˆ์—๋Š” dlwocks31์ด ๋”ฑํžˆ PS์— ๋”์ด์ƒ ๋™๊ธฐ๊ฐ€ ๋งŽ์ด ๋–จ์–ด์กŒ๋‹ค๋Š” ์‹์œผ๋กœ ๊ธฐํšŒ๋ฅผ ์–‘๋ณดํ•˜๊ธฐ๋„ ํ–ˆ๊ณ , ์ €๋Š” ๋‹ค๋ฅธ ํŒ€์›๋“ค์„ ๋ชจ์œผ๋”๋ผ๋„ ์„œ์šธ๋Œ€์—์„œ ๋ณธ์„ ์„ ์ง„์ถœํ•˜๊ธฐ๋Š” ์‰ฝ์ง€ ์•Š๊ฒ ๋‹ค๋Š” ํŒ๋‹จ์ด ๋“ค์–ด์„œ ํ–‰๋ณต PS๋ฅผ ์œ„ํ•ด ์ด ํŒ€ ๊ทธ๋Œ€๋กœ ๋‚˜๊ฐ€๊ธฐ๋กœ ํ–ˆ์Šต๋‹ˆ๋‹ค. ๋ฌด์—‡๋ณด๋‹ค ๊ฐ™์ด ๋ฌธ์ œ๋ฅผ ํ’€๊ณ  ํŒ€์—ฐ์Šตํ•˜๋Š” ๊ณผ์ •์„ ์ฆ๊ธธ ์ˆ˜ ์žˆ๋Š” ํŒ€์ด๋ผ์„œ ๊ทธ๋ ‡๊ธฐ๋„ ํ•ฉ๋‹ˆ๋‹ค.

ICPC๋Š” ์ˆœ์ˆ˜ํ•˜๊ฒŒ PS๋ฅผ ์ฆ๊ธฐ๋Ÿฌ ๋‚˜๊ฐ€์ง€๋งŒ (๋ณธ์„  ์ง„์ถœ๊ถŒ๋„ ์—†์œผ๋ฏ€๋กœ) ๊ทธ๋ž˜๋„ ์ด์™• ๋ชจ์ธ๊ฑฐ ํŒ€์—ฐ์Šต์ด๋‚˜ ํ•œ๋‘๋ฒˆ ํ•˜์ž๋Š” ์ƒ๊ฐ์œผ๋กœ GCPC 2020 ์…‹์„ ๋Œ์•˜์Šต๋‹ˆ๋‹ค.

GCPC๋Š” ๋น„๊ต์  ์‰ฌ์šด ๋ฆฌ์ €๋„๋กœ, ์›๋ž˜ 5์‹œ๊ฐ„ ์…‹์ด์ง€๋งŒ ์˜ˆ์„ ๋งŒ ๋‚˜๊ฐˆ๊ฑฐ๊ธฐ๋„ ํ•˜๊ณ  ์ €ํฌํ•œํ…Œ ์‹œ๊ฐ„์ด ๋งŽ์ด ์—†์–ด์„œ 3.5์‹œ๊ฐ„์œผ๋กœ ์žก๊ณ  ๋Œ์•˜์Šต๋‹ˆ๋‹ค. ํ’€๋งŒํ•œ ๋ฌธ์ œ๋Š” ๋‹ค ํ‘ผ๋“ฏ ํ•ฉ๋‹ˆ๋‹ค.

DHdroid๊ฐ€ ABCD, ์ œ๊ฐ€ EFGHI, Coffeetea๊ฐ€ JKLM์„ ์ฝ์ž๊ณ  ์ƒ๊ฐํ–ˆ์ง€๋งŒ ์ปค๋ฎค๋‹ˆ์ผ€์ด์…˜ ๋ฏธ์Šค๋กœ Coffeetea๊ฐ€ I๋ถ€ํ„ฐ ์ฝ์—ˆ๊ณ  M์€ ์•„๋ฌด๋„ ์žก์ง€ ์•Š์•˜์Šต๋‹ˆ๋‹ค. ใ…‹ใ…‹ใ…‹ใ…‹

F : Flip Flow (10๋ถ„ AC)

Solve : Gratus907 Code : Gratus907
์žฌ๋ฐŒ๊ฒŒ๋„ GCPC๋Š” ๋ฌธ์ œ์ œ๋ชฉ์ด ๋ฌธ์ œ ๋ฒˆํ˜ธ๋ฅผ ๋”ฐ๋ผ๊ฐ‘๋‹ˆ๋‹ค.

๋ชจ๋ž˜์‹œ๊ณ„๋ฅผ ๋’ค์ง‘์œผ๋ฉด์„œ ๋‚จ์€ ๋ชจ๋ž˜์˜ ์–‘์„ ํ™•์ธํ•˜๋Š” ๋ฌธ์ œ์ธ๋ฐ, ์ „์ฒด ์‹œ๊ฐ„ $t$๊ฐ€ ์ž‘์•„์„œ ๊ทธ๋Œ€๋กœ ์‹œ๋ฎฌ๋ ˆ์ด์…˜ ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. 10๋ถ„์— AC.

A : Adolescent Architecture / K : Knightly Knowledge (45 / 85๋ถ„ AC, ๊ฐ 1WA)

๊ฐ๊ฐ DHDroid / Coffeetea๊ฐ€ ์žก์•˜์Šต๋‹ˆ๋‹ค.

E๋Š” ๋”ฑ ๋ณด๊ธฐ์—๋„ ์–ด๋ ค์› ๊ณ , G๋Š” ๊ท€์ฐฎ์€ ๊ตฌํ˜„์ด ํ•„์š”ํ•ด ๋ณด์˜€์Šต๋‹ˆ๋‹ค. H๋Š” ๋„ˆ๋ฌด ๋ฌธ์ œ๊ฐ€ ๊ธธ์–ด์„œ ๊ฑธ๋Ÿฌ๋ฒ„๋ ธ๊ณ โ€ฆ โ€˜์ปดํ“จํ„ฐ๊ฐ€ ๋‚จ์œผ๋ฉดโ€™ G๋ฅผ ์งœ๊ฒ ๋‹ค๊ณ  ๋งํ–ˆ๋Š”๋ฐ, DHdroid์™€ Coffeetea๊ฐ€ A, K๊ฐ€ ์‰ฝ๋‹ค๊ณ  ์ฃผ์žฅํ–ˆ์œผ๋ฏ€๋กœ ์ปดํ“จํ„ฐ๋ฅผ ์ œ๊ฐ€ ์žก๊ณ ์žˆ๋Š”๊ฑด ์ข‹์€ ์ „๋žต์ด ์•„๋‹ˆ๋ผ๊ณ  ์ƒ๊ฐํ–ˆ์Šต๋‹ˆ๋‹ค.

๋‹ค๋งŒ ๋‘˜๋‹ค ๊ตฌํ˜„์„ ๊ทธ๋ ‡๊ฒŒ ๋น ๋ฅด๊ฒŒ ์ณ๋‚ด์ง€๋Š” ๋ชปํ–ˆ์Šต๋‹ˆ๋‹ค. ์ €๋Š” ๋‘ ๋ฌธ์ œ ๋‹ค ์ฝ์ง€ ์•Š์•˜์ง€๋งŒ ๊ฐ๊ฐ 2000, 2500๋ฐ”์ดํŠธ์˜ ์ฝ”๋”ฉ์ด ํ•„์š”ํ–ˆ๋˜ ๊ฒƒ์œผ๋กœ ๋ณด์•„ ๋‡Œ์ ˆ๋„ ์žˆ์—ˆ์ง€๋งŒ ๊ทผ๋ณธ์ ์œผ๋กœ ๊ตฌํ˜„๋‚œ์ด๋„๊ฐ€ ์ข€ ์žˆ์—ˆ๋˜๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค.

์ €๋Š” ์–‘์ชฝ ๋‹ค ๊ตฌํ˜„์— ์ฐธ์—ฌํ•˜์ง€ ์•Š์•˜๊ณ , ๋‘˜๋‹ค ๊ตฌ์ƒ์ด ๋๋‚˜๊ณ  ๊ตฌํ˜„๋งŒ ๋‚จ์€ ์ƒํƒœ์˜€๊ธฐ ๋•Œ๋ฌธ์—, DHDroid๊ฐ€ A๋ฒˆ์„ ์ฝ”๋”ฉํ•  ๋•Œ๋Š” Coffeetea๋ž‘ ๊ฐ™์ด I๋ฒˆ์„, Coffeetea๊ฐ€ K๋ฒˆ์„ ์ฝ”๋”ฉํ•˜๋Š” ๋™์•ˆ DHDroid๋ž‘ ๊ฐ™์ด C, D๋ฅผ ํ’€ ์ˆ˜ ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค. Coffeetea๊ฐ€ K๋ฒˆ์˜ ๊ตฌํ˜„์—์„œ ์ƒ๋‹นํžˆ ๋งŽ์ด ๊ณ ์ „ํ–ˆ๊ธฐ ๋•Œ๋ฌธ์—, ๋ฒ„๊ทธ๋ฅผ ์ฐพ๊ธฐ ์œ„ํ•ด ์ฝ”๋“œ๋ฅผ ๋”ฐ๋กœ ๋ณด๋ฉด์„œ (์‹ค์ „์—์„œ๋Š” ์ฝ”๋“œ ์ถœ๋ ฅ์— ํ•ด๋‹นํ•˜๋Š” ์„ ํƒ์ž…๋‹ˆ๋‹ค) ์ €ํ•œํ…Œ ์ค‘๊ฐ„์— ์ปดํ“จํ„ฐ๋ฅผ ๋„˜๊ฒจ์„œ I๋ฒˆ์„ (๋ช‡๋ฒˆ์˜ ๋””๋ฒ„๊น… ๋์—) ์„ฑ๊ณตํ–ˆ์Šต๋‹ˆ๋‹ค.

C : Confined Catching (67๋ถ„ AC)

Solve : Gratus907, DHDroid
๊ต‰์žฅํžˆ ์žฌ๋ฐŒ๋Š” ํผ์ฆํ‹ฑํ•œ ๋ฌธ์ œ์˜€๋‹ค๊ณ  ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค.
์ƒํ•˜์ขŒ์šฐ๋กœ ์›€์ง์ผ ์ˆ˜ ์žˆ๋Š” โ€˜๋งโ€™ ์ด ๋‚˜์—๊ฒŒ 2๊ฐœ, ์ƒ๋Œ€์—๊ฒŒ 1๊ฐœ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. $100 \times 100$ ๊ทธ๋ฆฌ๋“œ ์•ˆ์—์„œ, ๋‚ด๊ฐ€ ๋‘ ๋ง์„ ๋™์‹œ์— ์›€์ง์ด๋ฉด, ์ƒ๋Œ€๊ฐ€ ๊ทธ๊ฑธ ๋ณด๊ณ  ๋„๋ง์น  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋ง ๋‘ ๊ฐœ๋ฅผ ์ž˜ coordinationํ•ด์„œ, ์ƒ๋Œ€ ๋ง์„ โ€˜์žก์œผ๋ฉดโ€™ ์ด๊ธฐ๋Š” ๊ฒŒ์ž„์ž…๋‹ˆ๋‹ค. ๋‹จ, 600ํ„ด์˜ ์‹œ๊ฐ„ ์ œํ•œ์ด ์žˆ์Šต๋‹ˆ๋‹ค.

์ฒ˜์Œ์—๋Š” ๋‘ ๋ง์ด ์ด๋ฃจ๋Š” ์ง์‚ฌ๊ฐํ˜•์„ ์ขํžˆ๋Š” ๋“ฑ ๋ช‡๊ฐ€์ง€ ์•„์ด๋””์–ด๋ฅผ ์ƒ๊ฐํ–ˆ์ง€๋งŒ, ์ ์ ˆํ•œ ์•„์ด๋””์–ด๊ฐ€ ์—†์–ด ๊ณ ๋ฏผํ•˜๋˜ ์ค‘์— ์ œ๊ฐ€ ๋ง ํ•˜๋‚˜๋Š” $x$์ขŒํ‘œ๋ฅผ ๋จผ์ € ๋”ฐ๋ผ๋ถ™๊ณ , ๋ง ํ•˜๋‚˜๋Š” $y$์ขŒํ‘œ๋ฅผ ๋จผ์ € ๋”ฐ๋ผ๋ถ™๋Š” ์•„์ด๋””์–ด๋ฅผ ์ œ์‹œํ–ˆ์Šต๋‹ˆ๋‹ค. ์ƒ๋Œ€๊ฐ€ ์–ด๋Š์ชฝ์œผ๋กœ ๋„๋ง์น˜๋“  ๋‘ ๋ง ์ค‘ ์ ์–ด๋„ ํ•˜๋‚˜๋Š” ๊ฑฐ๋ฆฌ๋ฅผ ์ค„์ผ ์ˆ˜ ์žˆ์Œ์„ ๋ณด์žฅ๋ฐ›๊ธฐ ๋•Œ๋ฌธ์— (์ง์„ ์ƒ์˜ ๊ฒฝ์šฐ๊ฐ€ ์˜ˆ์™ธ๊ฐ€ ๋˜์ง€๋งŒ, ๋‹ค์Œ ํ„ด์—๋Š” ๋‹ค์‹œ ์ค„์ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค) ์–ด๋–ป๊ฒŒ ๋  ๊ฒƒ ๊ฐ™์•˜๊ณ , ์ž˜ ์ฝ”๋„ˆ๋กœ ๋ชฐ๋ฉด ์ด๊ธธ ์ˆ˜ ์žˆ๋‹ค๊ณ  ์ƒ๊ฐํ–ˆ์Šต๋‹ˆ๋‹ค.

DHDroid๊ฐ€ ์ด๊ฑธ ๋ฐ›๊ณ  ์ž ๊น ์ƒ๊ฐํ•ด๋ณด๋”๋‹ˆ โ€˜๋‚ด ๋ง ๋‘ ๊ฐœ์™€ ๋ฒฝ์ด ์ด๋ฃจ๋Š” ์ง์‚ฌ๊ฐํ˜•์ด ์ค„์–ด๋“ ๋‹คโ€™ ๋Š” ๋…ผ์ฆ์œผ๋กœ ์ด ๋ฐฉ๋ฒ•์ด ์˜ฌ๋ฐ”๋ฆ„์„ ์ฆ๋ช…ํ–ˆ๊ณ , ์ œ๊ฐ€ Coffeetea์—๊ฒŒ ์ž ๊น ์ปดํ“จํ„ฐ๋ฅผ ๋ฐ›์•„์„œ ๊ตฌํ˜„ํ•ด์„œ ๋งž์•˜์Šต๋‹ˆ๋‹ค.

I : Impressive Integers (103๋ถ„ AC, 4 WA)

Solve : Coffeetea, Gratus907
์š”์•ฝํ•˜์ž๋ฉด, ์–ด๋–ค $n$์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ž์—ฐ์ˆ˜ $a, b, c$๋ฅผ ๊ณจ๋ผ์„œ, ํ•œ ๋ณ€์˜ ๊ธธ์ด๊ฐ€ $c$์ธ ์ •์‚ผ๊ฐํ˜•์„ ํ•œ ๋ณ€์˜ ๊ธธ์ด๊ฐ€ $a$ ์™€ $b$์ธ ์ •์‚ผ๊ฐํ˜•๋“ค๋กœ ์ฑ„์šฐ๋Š”๋ฐ ์ •ํ™•ํžˆ $n$๊ฐœ๋ฅผ ์“ฐ๋„๋ก ํ•  ์ˆ˜ ์žˆ๋Š”์ง€์— ๋Œ€ํ•œ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

Coffeetea๊ฐ€ ๋จผ์ € ๋งจ ์œ„์— 1๊ฐœ ๋˜๋Š” 4๊ฐœ๋งŒ ์“ฐ๊ณ , ๋‚˜๋จธ์ง€๋ฅผ ์ž˜ ์ฑ„์›Œ๋„ฃ์œผ๋ฉด ๋ ๊ฒƒ๊ฐ™๋‹ค๋Š” ๊ฐ„๋‹จํ•˜์ง€๋งŒ ๋ฌธ์ œ๋ฅผ ๋ฐ”๋กœ ํ•ด๊ฒฐํ•˜๋Š” ์•„์ด๋””์–ด๋ฅผ ๋˜์กŒ๊ณ , ์ œ๊ฐ€ ๋นˆ ๋กœ์ง์„ ์ฑ„์›Œ๋„ฃ์–ด์„œ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ–ˆ์Šต๋‹ˆ๋‹ค. $n$์ด ํฐ ์ง์ˆ˜์ผ ๋•Œ๋Š”, ๋งจ ์œ„์— ํฐ ์‚ผ๊ฐํ˜• 1๊ฐœ๋ฅผ ๋†“๊ณ , ์•„๋ž˜๋ฅผ ํ•œ ๋ณ€์˜ ๊ธธ์ด๊ฐ€ 1์ธ ์‚ผ๊ฐํ˜• $n-1$๊ฐœ๋กœ ์ฑ„์šธ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ($n-1$์ด ํ™€์ˆ˜์ด๊ธฐ ๋•Œ๋ฌธ์—, ์œ„์•„๋ž˜๋กœ ์ฑ„์›Œ๋„ฃ์œผ๋ฉด ๋ฉ๋‹ˆ๋‹ค) ๋ฐ˜๋Œ€๋กœ $n$์ด ํฐ ํ™€์ˆ˜์ผ ๋•Œ๋Š” ๋งจ ์œ„์— ์‚ผ๊ฐํ˜• 4๊ฐœ๋ฅผ ๋†“๊ณ , ์•„๋ž˜๋ฅผ ํ•œ ๋ณ€์˜ ๊ธธ์ด๊ฐ€ ์ง์ˆ˜์ธ ์‚ผ๊ฐํ˜• $n-4$๊ฐœ๋กœ ์ฑ„์›Œ๋„ฃ์œผ๋ฉด ๋ฉ๋‹ˆ๋‹ค. ์ด ๋ฐฉ๋ฒ•์œผ๋กœ $n = 2, 3, 5$ ์™ธ์—๋Š” ๋ชจ๋“  ๊ฒฝ์šฐ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์Œ์„ ๋ณด์ด๋ฉด ๋ฉ๋‹ˆ๋‹ค.

๊ตฌํ˜„์—์„œ ์ˆซ์ž๋ฅผ off-by-one ์—๋Ÿฌ ๋‚ด์„œ ๋ฌด๋ ค 4๋ฒˆ์„ ํ‹€๋ ธ์Šต๋‹ˆ๋‹ค. ํ‘ํ‘โ€ฆ

D : Decorative Dominoes (142๋ถ„ AC)

Solve : DHDroid, Gratus907 Code : Gratus907
์žฌ๋ฐŒ๊ฒŒ ํ’€์—ˆ์Šต๋‹ˆ๋‹ค. ๋„๋ฏธ๋…ธ์— ์ˆซ์ž๋ฅผ ์จ๋„ฃ๋˜, ์ˆซ์ž๊ฐ€ 2๋ฒˆ ์ด์ƒ ์ค‘๋ณต๋˜์–ด์„œ๋Š” ์•ˆ ๋˜๊ณ , ๋„๋ฏธ๋…ธ์นธ ํ•˜๋‚˜๋Š” ์ ์–ด๋„ ์ฃผ๋ณ€์— ๊ฐ™์€ ์ˆซ์ž๊ฐ€ ์จ์žˆ๋Š” ๋„๋ฏธ๋…ธ๊ฐ€ ํ•˜๋‚˜ ์žˆ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

๋ฌธ์ œ๋ฅผ ์ด๋ถ„ ๋งค์นญ์œผ๋กœ ๋งŒ๋“ค์–ด ํ’€๋ฉด ๊ทธ๋ ‡๊ฒŒ ์–ด๋ ต์ง€๋Š” ์•Š์€๋ฐ ๊ตฌํ˜„์ด ์ƒ๋‹นํžˆ ๊ท€์ฐฎ์Šต๋‹ˆ๋‹ค. DHDroid๊ฐ€ ์ด๋ถ„๋งค์นญ์˜ ๋Œ€๋žต์ ์ธ ์•„์ด๋””์–ด๋ฅผ ์ œ์‹œํ•˜๊ณ , ์ œ๊ฐ€ ์ •ํ™•ํžˆ ์–ด๋–ป๊ฒŒ ํ’€๊ฑด์ง€ ์ข€ ๊ณ ๋ฏผํ•ด๋ณด๋‹ค๊ฐ€ ํ’€์—ˆ์Šต๋‹ˆ๋‹ค. pair๋ฅผ ๋…ธ๋“œ๋กœ ๋‹ค์‹œ ์ธ์ฝ”๋”ฉํ•œ๋‹ค๋˜๊ฐ€ ํ•˜๋Š” ๊ตฌํ˜„์˜ ์žก๋‹คํ•œ ํŠธ๋ฆญ๋“ค์ด ๋งŽ์ด ๋“ค์–ด๊ฐ„๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค.

์ด๋•Œ, ์ œ๊ฐ€ ๊ตฌํ˜„ํ•˜๋Š” ๋™์•ˆ DHDroid๋Š” ๊ณ„์† L์— ๋Œ€ํ•œ ์•„์ด๋””์–ด๋ฅผ ์ œ์‹œํ•˜๊ณ  Coffeetea์™€ B๋ฅผ ํ•ด๊ฒฐํ–ˆ์Šต๋‹ˆ๋‹ค. D์™€ L์„ ์˜ค๊ฐ€๋ฉด์„œ ์ €๋ž‘ DHdroid๊ฐ€ ํ’€์ด๋ฅผ ๋‘˜๋‹ค ๊ฑฐ์˜ ์™„์„ฑํ–ˆ์—ˆ๊ธฐ ๋•Œ๋ฌธ์—, L๋ฒˆ๋„ ์‚ฌ์‹ค ์‹œ๊ฐ„์ด ์ถฉ๋ถ„ํ•˜๋‹ค๋ฉด ์ฝ”๋”ฉํ•  ์ˆ˜ ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค.

G : Gravity Grid (160๋ถ„ AC, 3 WA)

Solve : Gratus907 Code : Gratus907
๋‹จ์ˆœ ์‹œ๋ฎฌ๋ ˆ์ด์…˜ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์ค‘๋ ฅ์ด ์ž‘์šฉํ•˜๋Š” ์นธ์—์„œ ์—ด๋งŒ ๊ณ ๋ฅด๋ฉด์„œ ํ‹ฑํƒํ† ๋ฅผ ํ•˜๋Š”๋ฐ, $k$๊ฐœ๋ฅผ ํ•œ์ค„๋กœ (๊ฐ€๋กœ, ์„ธ๋กœ, ๋Œ€๊ฐ์„ ) ๋ชจ์œผ๋ฉด ์Šน๋ฆฌํ•ฉ๋‹ˆ๋‹ค.

๊ฐ€๋กœ ๋ฐฉํ–ฅ, ์„ธ๋กœ ๋ฐฉํ–ฅ, ๋Œ€๊ฐ์„  ๋ฐฉํ–ฅ์˜ DSU๋ฅผ ๊ด€๋ฆฌํ•˜๋ฉด ์–ด๋ ต์ง€ ์•Š์Šต๋‹ˆ๋‹ค. ๊ฐ€๋กœ๋ฐฉํ–ฅ๊ณผ ์„ธ๋กœ๋ฐฉํ–ฅ์˜ ํฌ๊ธฐ๋Š” ์ž๋ช…ํ•œ๋ฐ, ๋Œ€๊ฐ์„ ๋ฐฉํ–ฅ์€ ๋Œ€๊ฐ์„ ์— ์ ์ ˆํ•œ ์ธ๋ฑ์Šค๋ฅผ ๋ถ€์—ฌํ•˜์—ฌ $(h + w)$๊ฐœ์˜ DSU๋ฅผ $\min(h, w)$๊ฐœ ์นธ์„ ๊ฐ–๋„๋ก ๊ด€๋ฆฌํ•˜๋ฉด ์ž˜ ํ•ด๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ค‘๊ฐ„์— ์‹ค์ˆ˜๋กœ, $h$์™€ $w$๋ฅผ ๋ฐ”๊ฟ” ์ผ๋Š”๋ฐ ๋†€๋ž๊ฒŒ๋„ WA๊ฐ€ ์•„๋‹ˆ๋ผ MLE๋ฅผ ๋ฐ›์•˜์Šต๋‹ˆ๋‹ค. ์–ด๋–ค ์›๋ฆฌ๋กœ MLE๊ฐ€ ๋‚˜๋Š”์ง€๋Š” ํŒŒ์•…ํ•˜์ง€ ๋ชปํ•œ ์ฑ„๋กœ, ๋ฒกํ„ฐ๋กœ ์ •์ˆ˜ 900๋งŒ ๊ฐœ๋ฅผ allocateํ•˜๋Š”๊ฑฐ ์ž์ฒด๊ฐ€ ๋ฌธ์ œ๊ฐ€ ์žˆ๋Š”๊ฑด๊ฐ€ ํ•˜๋Š” ์ƒ๊ฐ์— new int๋ฅผ ์“ฐ๋Š” ๋“ฑ ์‚ฝ์งˆ์„ ํ–ˆ์ง€๋งŒ ์›์ธ์€ ๋‹จ์ˆœ ์‹ค์ˆ˜์˜€์Œ์„ ํ•œ์ฐธ ๋‚˜์ค‘์— ์ฐพ์•„๋ƒˆ์Šต๋‹ˆ๋‹ค.

B : Bookshelf Building (175๋ถ„ AC, 3 WA)

Solve : DHDroid, Coffeetea Code : DHDroid
์ฝ์–ด๋ณด์ง€ ์•Š์•˜์ง€๋งŒ ์ œ๊ฐ€ G๋ฒˆ ํ‘ธ๋Š” ๋™์•ˆ ๋‘˜์ด ์ž˜ ํ’€๊ณ  ์ฝ”๋”ฉํ–ˆ์Šต๋‹ˆ๋‹ค.

M : Mixtape Management (199๋ถ„ AC)

Solve : Coffeetea, Gratus907 ์‰ฌ์šด ๋ฌธ์ œ์ด์ง€๋งŒ ํŒ€์›๊ฐ„์˜ ์ปค๋ฎค๋‹ˆ์ผ€์ด์…˜ ์‹ค์ˆ˜๋กœ ์•„๋ฌด๋„ ์ฝ์ง€ ์•Š์•„์„œ ๋ฒ„๋ ค์ง„ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ๋ฌธ์ œ๊ฐ€ ๋งค์šฐ ๊ธธ๊ณ  ์ง€๋ฌธ์ด ํ˜ผ๋ž€์Šค๋Ÿฌ์šด๋ฐ, ์ˆซ์ž์˜ ํฌ๊ธฐ ์ •๋ ฌ๊ณผ ๋ฌธ์ž์—ด๋กœ์จ์˜ ์ •๋ ฌ ๊ฐ„์— ๋ฐœ์ƒํ•˜๋Š” ์ฐจ์ด์— ๋Œ€ํ•œ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

์ด ์ˆซ์ž๊ฐ€ ๋ช‡๋ฒˆ์งธ์— ์œ„์น˜ํ•ด์•ผ ํ•˜๋Š”์ง€๋ฅผ ํŒŒ์•…ํ•œ ๋‹ค์Œ, ๊ทธ ์•ž์—๋Š” ๋ชจ๋‘ 1๋“ค์„, ์ž๊ธฐ ์ž์‹ ์€ 2๋ฅผ, ๋’ค์—๋Š” 3๋“ค์„ ๋ถ™์ด๋ฉด ๋ฉ๋‹ˆ๋‹ค. ์ด ๋ง๋งŒ์œผ๋กœ๋Š” ์ „ํ˜€ ๋ฌด์Šจ๋ง์ธ์ง€ ์•Œ ์ˆ˜๊ฐ€ ์—†์ง€๋งŒ..

์˜ˆ์ œ 4 2 6 1 5 7 3 ์„ ๋ณด๋ฉด, 1์ด 4๋ฒˆ์งธ์ด๋ฏ€๋กœ 1 1 1 2 3 3 3 ์œผ๋กœ ๋งŒ๋“ญ๋‹ˆ๋‹ค. ์ดํ›„์—๋Š”, 2๊ฐ€ ๋‘๋ฒˆ์งธ์ด๋ฏ€๋กœ 11, 12, 13, 2 (์ด๋ฏธ ๋๋‚œ ์ˆซ์ž๋Š” ๊ฑด๋“œ๋ฆฌ์ง€ ์•Š์Šต๋‹ˆ๋‹ค), 33, 33, 33์œผ๋กœ ๋งŒ๋“ค๊ณ โ€ฆ ์ด๋Ÿฐ์‹์œผ๋กœ 1, 2, 3์„ ๋ถ™์—ฌ์„œ ๋งŒ๋“ค๋ฉด ๋ฉ๋‹ˆ๋‹ค.

์˜ˆ์ œ์— ๋Œ€ํ•œ ์ €ํฌ์˜ ๋‹ต์€ 1112 12 131312 2 33132 3313332 332 ์ž…๋‹ˆ๋‹ค. 20์ค„ ๋‚ด์™ธ์˜ ์ฝ”๋“œ๋กœ ํ•ด๊ฒฐ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค. ใ…‹ใ…‹! 199๋ถ„ AC.

L : Lexicographical Lecturing (209๋ถ„ AC)

Solve : DHDroid, Gratus907 Code : Gratus907 ๋จผ์ € ๋ฌธ์ œ๋ฅผ ์„ค๋ช…ํ•˜์ž๋ฉด, $n$ ๊ฐœ์˜ ๊ธธ์ด $L$์งœ๋ฆฌ ๋ฌธ์ž์—ด์ด ์ฃผ์–ด์ง€๊ณ , ์ด ๋ฌธ์ž์—ด์˜ ์–ด๋–ค $[i, j]$ ๊ตฌ๊ฐ„๋“ค๋งŒ์„ ์ด์šฉํ•˜์—ฌ ์ •๋ ฌํ•œ ๊ฒฐ๊ณผ๊ฐ€ ์›๋ž˜์˜ ์ •๋ ฌ ๊ฒฐ๊ณผ์™€ ๊ฐ™๊ฒŒ ํ•˜๋Š” ์ตœ์†Œ ๊ธธ์ด $[i, j]$๋ฅผ ์ฐพ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

Prefix์— ๊ด€ํ•œ ๋ฐฐ์—ด์„ ๊ด€๋ฆฌํ•˜๋Š”๋ฐ, p[k][j] ๋Š” ํ˜„์žฌ ๋ณด๋Š” $k$๋ฒˆ ๋ฌธ์ž์—ด๊ณผ ๊ทธ ์•ž ๋ฌธ์ž์—ด์˜ $j$๋ฒˆ์งธ ๋ฌธ์ž๋ฅผ ๋น„๊ตํ•œ ๊ฒฐ๊ณผ๋ฅผ ์ €์žฅํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ, ์šฐ๋ฆฌ๊ฐ€ ์›ํ•˜๋Š” $[i, j]$๋Š” ์ด $p$๋ฐฐ์—ด์—์„œ ๋‹ค์Œ๊ณผ ๊ฐ™๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.

  • $p$๋ฐฐ์—ด์˜ sub-matrix $[2, n] \times [i, j]$๋ฅผ ๋ฝ‘์•˜์„ ๋•Œ, ๋ชจ๋“  ํ–‰์— leading 1์ด ์žˆ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. $p$๋ฐฐ์—ด์˜ ์ •์˜๋ฅผ ์ƒ๊ฐํ•ด๋ณด๋ฉด, sub-matrix์˜ row๊ฐ€ 1๋กœ ์‹œ์ž‘ํ•œ๋‹ค๋ฉด (์ฒซ๋ฒˆ์งธ non-zero element๊ฐ€ 1์ด๋ผ๋Š” ๋œป) ์ •๋ ฌ ๊ฒฐ๊ณผ๊ฐ€ ์˜ฌ๋ฐ”๋ฅด๊ณ , -1์ด๋ผ๋ฉด ์ •๋ ฌ ๊ฒฐ๊ณผ๊ฐ€ ํ‹€๋ฆฌ๋ฉฐ, ๋ชจ๋“  element๊ฐ€ 0์ด๋ผ๋ฉด ๋น„๊ต๊ฐ€ ๋ถˆ๊ฐ€๋Šฅํ•ด์„œ ํŒ๋‹จํ•  ์ˆ˜ ์—†๊ธฐ ๋•Œ๋ฌธ์— ์—ญ์‹œ ์˜ฌ๋ฐ”๋ฅด์ง€ ์•Š์Šต๋‹ˆ๋‹ค.
  • ๊ทธ๋Ÿฌ๋ฉด, ์ด๋ฅผ ์–ด๋–ป๊ฒŒ ํŒŒ์•…ํ•  ๊ฒƒ์ธ์ง€๊ฐ€ ๋ฌธ์ œ์ธ๋ฐโ€ฆ
  • ๊ฐ i, j๋งˆ๋‹ค, โ€œ๋‚ด ๋’ค๋กœ ๋ณด์ด๋Š” ์ฒซ๋ฒˆ์งธ +1โ€๊ณผ โ€œ๋‚ด ๋’ค๋กœ ๋ณด์ด๋Š” ์ฒซ๋ฒˆ์งธ -1โ€ ์˜ ์œ„์น˜๋ฅผ ์ €์žฅํ•ฉ๋‹ˆ๋‹ค. ์ด์ œ, ์–ด๋–ค $[i, -]$ ๊ตฌ๊ฐ„์ด ์˜ฌ๋ฐ”๋ฅด๊ธฐ ์œ„ํ•ด์„œ๋Š” $i$๋ฒˆ ๋’ค๋กœ ๋‚˜ํƒ€๋‚˜๋Š” ์ฒซ๋ฒˆ์งธ 1์˜ ์œ„์น˜๊ฐ€ ์ฒซ๋ฒˆ์งธ -1๋ณด๋‹ค ์•ž์ด์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.
  • ์ด์ œ, $i$๋กœ ์‹œ์ž‘ํ•˜๋Š” ๊ตฌ๊ฐ„๋“ค ์ค‘, ์ ์–ด๋„ ๋ชจ๋“  ํ–‰์ด leading 1์„ ๊ฐ–๋„๋ก ๊ตฌ๊ฐ„ ๋์ ์„ ๋’ค๋กœ ๋ฐ€์–ด์ค˜์•ผ ํ•ฉ๋‹ˆ๋‹ค.
  • ๊ฐ $i$๋กœ ์‹œ์ž‘ํ•˜๋Š” ๊ตฌ๊ฐ„๋“ค์„ $O(n)$์— ํŒ๋‹จ๊ฐ€๋Šฅํ•ด์„œ, $O(nL)$ ์‹œ๊ฐ„์— ์ž‘๋™ํ•ฉ๋‹ˆ๋‹ค.

์ด๋ฒˆ ์—ฐ์Šต ํ•˜์ด๋ผ์ดํŠธ๋Š”, M๋ฒˆ์„ ๋งž๊ณ  ๋‚˜์„œ ์‹œ๊ฐ„์ด 11๋ถ„ ๋‚จ์•„์žˆ์—ˆ๋Š”๋ฐ ์ œ๊ฐ€ ์ด๊ฑธ 10๋ถ„ ๋งŒ์— ์งœ์„œ ์˜ˆ์ œ๋งŒ ๋Œ๋ ค๋ณด๊ณ  ๋ฐ”๋กœ ๋‚ด์„œ ๋งž์•˜๋‹ค๋Š” ์ ์ž…๋‹ˆ๋‹ค. ใ…‹ใ…‹!! ์ œ๊ฐ€ ๊ตฌํ˜„์„ ๋ชปํ•˜๋Š”๊ฒƒ์€ ๊ตฌํ˜„์ด ๋Š๋ ค์„œ๊ฐ€ ์•„๋‹ˆ๋ผ ๋ง๋ ธ์„๋•Œ ๋‹ต์ด ์—†์–ด์„œ ๊ทธ๋Ÿฐ๊ฑฐ๊ณ , ์‚ฌ์‹ค ๊ตฌํ˜„ ์†๋„๋Š” ๊ทธ๋Ÿญ์ €๋Ÿญ ๋Š๋ฆฌ์ง€ ์•Š์€ ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค.

Review

  • ์—ฌ์ „ํžˆ ์ด ํŒ€์€ ๊ทธ๋ƒฅ PS๋ฅผ ์ฆ๊ธธ ์ˆ˜ ์žˆ๊ฒŒ ํ•ด์ฃผ๋Š” ์›๋™๋ ฅ์ž…๋‹ˆ๋‹ค. ์„ธ๋ช…์˜ ์žฅ๋‹จ์ ์ด ๋น„๊ต์  ๋šœ๋ ทํ•˜๊ณ  ์„œ๋กœ ๋ณด์™„์ ์ธ ๊ตฌ์„ฑ์ž…๋‹ˆ๋‹ค.
  • GCPC ์…‹ ์ž์ฒด๋Š” ๊ดœ์ฐฎ์€๋ฐ, 5์‹œ๊ฐ„์ด์—ˆ๋‹ค๋ฉด ์•„๋งˆ ๋‚จ์€ 1์‹œ๊ฐ„ ๋ฐ˜๋™์•ˆ ํ•˜๋‚˜ ์žก๊ณ  ํ’€๊ธฐ ์‰ฝ์ง€ ์•Š์•˜์„ ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค. ์‹ค์ œ๋กœ ๋‚จ์€ ๋ฌธ์ œ๋“ค์€ ์ถฉ๊ฒฉ์ ์ธ ๋‚œ์ด๋„ (๋‹ค์ด์•„ ๋˜๋Š” ?) ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค.
  • ์ œ๊ฐ€ ๊ตฌํ˜„์— ๋ฌถ์—ฌ์žˆ๋Š”๋™์•ˆ ๋‘๋ช…์ด J๋„ ์ข€ ํ’€์–ด๋†จ๋˜๋ฐ, ๋ฌด์Šจ ๊ฐ๋„์ •๋ ฌ + ๋ฏธ์นœ๊ธฐํ•˜ + ๋‹จ์ ˆ์  ๋ฌธ์ œ์˜€์Šต๋‹ˆ๋‹ค. ๊ฒฐ๊ณผ์ ์œผ๋กœ ์†”๋ฃจ์…˜์€ ๊ฑฐ์˜ ๋‹ค ๋งž์•˜๋˜ ๊ฒƒ์œผ๋กœ ๊ธฐ์–ตํ•˜๋Š”๋ฐ, ์ €๋Š” 24์‹œ๊ฐ„ ์ค˜๋„ ๊ทธ๊ฑธ ๊ตฌํ˜„ํ•  ์ž์‹ ์ด ์—†์œผ๋ฏ€๋กœ ์•„๋งˆ ์–ด์ฐจํ”ผ AC๋ฅผ ๋ฐ›์ง€๋Š” ๋ชปํ–ˆ์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค.