Back to : cp-rounds
Contents

Little Piplup ํŒ€์œผ๋กœ ๋ณต๊ท€ํ•ด์„œ ICPC 2021์„ ์žฌ๋ฐŒ๊ฒŒ ์น˜๊ณ  ์™”์Šต๋‹ˆ๋‹ค.

๋Š˜ ๋Œ€ํšŒ๊ฐ€ ๋๋‚˜๊ณ  ๋‚˜๋ฉด Whining์„ ํ•ด์™”์ง€๋งŒ, ์ด๋ฒˆ ๋Œ€ํšŒ๋Š” ์†”์งํžˆ ๋งํ•˜๋ฉด Whiningํ• ๊ฒŒ ๋ณ„๋กœ ์—†์Šต๋‹ˆ๋‹ค. 18๋“ฑ์˜ ์„ฑ์ ์„ ๊ฑฐ๋‘์—ˆ๋Š”๋ฐ, ํ’€์—ˆ์–ด์•ผ ํ•  ๋ฌธ์ œ ๋Š” ๋‹ค ํ’€์ง€ ์•Š์•˜๋‚˜ ์‹ถ์Šต๋‹ˆ๋‹ค.

picture 1

Prep - ๋Œ€ํšŒ๊ณผ์ • ํƒ€์ž„๋ผ์ธ์— ๋”ฐ๋ฅธ ์˜์‹์˜ ํ๋ฆ„ - Retrospect์˜ ์ˆœ์„œ๋กœ ์ž‘์„ฑํ•ฉ๋‹ˆ๋‹ค.

ํ‰์†Œ๋ณด๋‹ค ์•ž๋’ค ๊ธ€์ด ๋งŽ์ด ๊ธธ๊ณ  ์žฅํ™ฉํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ์™ผ์ชฝ ์•„๋ž˜ Table of Content๋ฅผ ๋ณด๋ฉด ๋ฌธ์ œ์— ๋Œ€ํ•œ ์ด์•ผ๊ธฐ๋งŒ ๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

Preperation / Our Team

ํŒ€์—ฐ์Šต ๋‘๋ฒˆ์„ ํ–ˆ์Šต๋‹ˆ๋‹ค.

์ด ํŒ€์˜ ๊ฐ๊ด€์ ์ธ ์ „๋ ฅ์„ ์ €๋Š” ๊ฐœ์ธ์ ์œผ๋กœ ์ ์–ด๋„ 2100 3๋ช… ์ •๋„ ์ˆ˜์ค€, ๋‚ด์ง€๋Š” ๋ฌธ์ œ์…‹์„ ์กฐ๊ธˆ ์ž˜ ํƒ€๋ฉด 1๋ ˆ๋“œ๊ฐ€ ์„ž์ธ ํŒ€๊ณผ๋„ ๋น„๋ฒผ๋ณผ ์ˆ˜ ์žˆ๋‹ค๊ณ  ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค. ๊ฐ€์žฅ ์ตœ๊ทผ์˜ ํŒ€ ๋Œ€ํšŒ๋Š” Hashcode 2021์ด์—ˆ๋Š”๋ฐ, ๊ทธ๋•Œ์™€ ์ง€๊ธˆ ํŒ€์„ ๋น„๊ตํ•˜๋ฉด (dlwocks31์˜ ๋ถ€์žฌ๋ฅผ ์ œ์™ธํ•˜๊ณ  ์„ธ๋ช…๋งŒ) ํฌ๊ฒŒ ๋‹ฌ๋ผ์ง„ ๊ฒƒ์€ ์—†์œผ๋ฏ€๋กœ ๊ทธ๋•Œ ์ผ๋˜ ๊ธฐ๋ก์— ๋”ํ•˜์—ฌ ํŒ€์›๋“ค์— ๋Œ€ํ•œ ์–˜๊ธฐ๋ฅผ ์กฐ๊ธˆ ํ•ด๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.

  • Gratus907 : ์ˆ˜ํ•™์ ์ธ ๋ฌธ์ œ์— ๋น„๊ต์  ๊ฐ•ํ•˜๊ณ , ๋ง๋ฆฌ์ง€ ์•Š์„๋•Œ๊นŒ์ง€๋Š” ๊ตฌํ˜„์ด ๋น ๋ฅด์ง€๋งŒ ๋ง๋ฆฌ๋ฉด ํ•œ์—†์ด ๋ง๋ฆฌ๋Š” ๊ฒฝํ–ฅ์ด ์žˆ์Šต๋‹ˆ๋‹ค.
    • ๊ทธ๋ž˜๋„ ์ œ ์ฝ”๋”ฉ ๊ฒฝํ—˜์ด ์Œ“์ด๋ฉด์„œ ์˜ˆ์ „๋งŒํผ ์ฝ”๋”ฉ์ด ๋ง๋ฆฌ์ง€ ์•Š์Šต๋‹ˆ๋‹ค.
    • ๋ฐ˜๋ฉด์—, ํ•œ๋ฒˆ ์–ด๋–ค ๋ฐฉ๋ฉด์œผ๋กœ ๋น ์ง€๋ฉด ๋ฌดํ•œํ•œ ๋‡Œ์ ˆ์„ ์ด์–ด๊ฐ€๋Š” ๊ฒฝํ–ฅ์ด ์žˆ์Šต๋‹ˆ๋‹ค. ์ด๋Š” FFT์— ํŒจ๋ฐฐํ•œ SCPC 2021 ๊ฐ™์€ ์ƒํ™ฉ์—์„œ ์ •๋ง ๋”์ฐํ–ˆ์Šต๋‹ˆ๋‹ค.
    • ์ˆ˜ํ•™ ๋ณต์ˆ˜์ „๊ณต์„ ํ†ตํ•ด ์–ป์€ ์ง€์‹์€ ๋”ฑํžˆ PS์— ๋„์›€์ด ๋˜์ง€ ์•Š์ง€๋งŒ, ์”น๋•๊ฐ™์€ ์ •์ˆ˜๋ก  ๋ฌธ์ œ ํ•œ๋‘๊ฐœ๋ฅผ ๊ฐ€๋” ์ณ๋‚ผ ์ˆ˜ ์žˆ๋Š”๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค.
    • ์•„์นด๋ฐ๋ฏนํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ณต๋ถ€๋ฅผ ๊ทธ๋ž˜๋„ ์ด์ค‘์— ๊ฐ€์žฅ ๋งŽ์ด ํ–ˆ์—ˆ์Šต๋‹ˆ๋‹ค.
  • DHDroid : Constructiveํ•œ ๋ฌธ์ œ์— ๋งค์šฐ ๊ฐ•ํ•˜๊ณ , ๊ด€์ฐฐ์„ ์ •๋‹นํ™” (์ฆ๋ช…) ํ•˜๋Š” ๋Šฅ๋ ฅ์ด ๋›ฐ์–ด๋‚ฉ๋‹ˆ๋‹ค.
    • ์ด ๋Šฅ๋ ฅ์„ ์‹ค์ œ๋กœ ๋ณด์—ฌ์ค€ ๋Œ€ํšŒ๊ฐ€ ์—ญ์‹œ SCPC 2021์ž…๋‹ˆ๋‹ค. Round 2 ํ•˜๋…ธ์ดํƒ‘์—์„œ ์ผ๋ถ€ ๋ ˆ๋“œ๋“ค๋„ ๋‹ฌ์„ฑ์„ ์–ด๋ ค์›Œํ–ˆ๋˜ 250์ ์„ ๋‹ฌ์„ฑํ•˜๊ณ , ์ €๋ณด๋‹ค ํ›จ์”ฌ ๋†’์€ ์„ฑ์ ์œผ๋กœ 2๋ผ์šด๋“œ๋ฅผ ๋งˆ์นœํ›„ ๋ณธ์„ ์—์„œ 5๋“ฑ์ƒ์„ ๋ฐ›๋Š” ์พŒ๊ฑฐ๋ฅผ ๋ณด์—ฌ์คฌ์Šต๋‹ˆ๋‹ค.
    • ๋ณธ์ธ์˜ ํ‘œํ˜„์„ ๋นŒ๋ฆฌ์ž๋ฉด ์ •๋ง ์–ด๋ ค์šด ๋ฌธ์ œ์— ๋„์ „ํ•ด์„œ ๋ช‡ ์‹œ๊ฐ„ ๊ณ ๋ฏผ์„ ์ด์–ด๊ฐ€๋Š” ๋ณธ์ธ์˜ ์—ฐ์Šต๋ฐฉ์‹์ด ๋„์›€์ด ๋œ๋‹ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.
    • ํ•™๊ณผ ๋™๊ธฐ์ด๊ณ  ์นœ๊ตฌ์ง€๋งŒ ์ด๋ ‡๊ฒŒ ์–ด๋ ค์šด ๋ฌธ์ œ๋ฅผ ๋Œ€ํ•˜๋Š” ์ž์„ธ๋ฅผ ๋ณด๋ฉด์„œ ํ•ญ์ƒ ๋งŽ์€ ๊ฒƒ์„ ๋ฐฐ์›๋‹ˆ๋‹ค.
    • ๋ฐ˜๋Œ€๋กœ ์ œํ•œ์‹œ๊ฐ„์ด ์งง์€ ๋Œ€ํšŒ์— ์‚ด์ง ์•ฝํ•ฉ๋‹ˆ๋‹ค. 2์‹œ๊ฐ„์งœ๋ฆฌ ์ฝ”๋“œํฌ์Šค๊ฐ€ ๊ฐ€์žฅ ๋Œ€ํ‘œ์ ์ด์ฃ .
  • Coffeetea : ๊ทธ๋ฆฌ๋””ํ•˜๊ฑฐ๋‚˜ ํœด๋ฆฌ์Šคํ‹ฑํ•œ ๊ด€์ฐฐ, ๋Œ€๋žต์ ์ธ ๊ฒฝํ–ฅ์„ฑ์˜ ํŒŒ์•…์— ๊ฐ•ํ•ฉ๋‹ˆ๋‹ค. ๋ญ”๊ฐ€ ๋ฌธ์ œ์— ๋น™์˜ํ•˜๋Š” ํŠน์„ฑ์ด ์žˆ์–ด์„œ ๊ธ€์“ธ๋•Œ Coffeetea์˜ ํ‘œํ˜„์„ ๋งŽ์ด ๋นŒ๋ฆฌ๊ฒŒ ๋ฉ๋‹ˆ๋‹ค :)
    • ์ €๋Š” ๊ทธ๋•Œ ์ด ํŒ€์— ์—†์—ˆ์ง€๋งŒ, ์ž‘๋…„ ICPC F๋ฒˆ ๊ฐ™์€ ๋ฌธ์ œ์—์„œ ๊ฐ€์žฅ ์ž˜ ๋Š๋‚„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. (์ด ๋ฌธ์ œ๋Š” ๊ทธ๋ ‡๊ฒŒ ์–ด๋ ต์ง€ ์•Š์ง€๋งŒ์š”)
    • Hashcode ์Šคํƒ€์ผ์˜ ๋Œ€ํšŒ์—์„œ ์ดˆ๊ธฐ ์•„์ด๋””์–ด๋ฅผ ์ •๋ง ์ž˜ ๋˜์ ธ์ฃผ๊ณ , ๋ฐ์ดํ„ฐ๋ฅผ ์Šฅ ๋ณด๊ณ  ํŠน์„ฑ์„ ๋น ๋ฅด๊ฒŒ ์บ์น˜ํ•ฉ๋‹ˆ๋‹ค.
    • ๋งŽ์ด ๋ณต์žกํ•œ ๊ตฌํ˜„์€ ์ €๋ณด๋‹ค ์ž˜ ํ•ฉ๋‹ˆ๋‹ค. ์ €๋ณด๋‹ค ์ข€๋” ๊ตฌํ˜„์— ๋Œ€ํ•ด ์ฒด๊ณ„์ ์œผ๋กœ ๊ณ ๋ฏผํ•˜๊ณ , ๋†“์น˜๋Š” ์ผ€์ด์Šค๊ฐ€ ๋น„๊ต์  ์ ์œผ๋ฉฐ, ๋””๋ฒ„๊น…ํ• ๋•Œ์˜ ๋ˆ๊ธฐ์™€ ์ž์„ธ๊ฐ€ ๋›ฐ์–ด๋‚ฉ๋‹ˆ๋‹ค. ์—ญ์‹œ ํ•ญ์ƒ ๋งŽ์€ ๊ฒƒ์„ ๋ฐฐ์šฐ๊ฒŒ ๋˜๋Š” ์นœ๊ตฌ์ž…๋‹ˆ๋‹ค.
    • ๊ฐœ๋ฐœ ๊ณต๋ถ€์— ๋งŽ์€ ์‹œ๊ฐ„๊ณผ ๋…ธ๋ ฅ์„ ํˆฌ์žํ–ˆ๊ธฐ ๋•Œ๋ฌธ์— ์ด๋Ÿฐ ๊ตฌํ˜„ ์‹ค๋ ฅ์„ ๊ฐ–์ถ˜ ๊ฒƒ ๊ฐ™์€๋ฐ, ๋ฐ˜๋Œ€๋กœ ์†Œ์œ„ โ€˜๊ณ ์ธ๋ฌผ ์•Œ๊ณ ๋ฆฌ์ฆ˜โ€™ ์— ๋Œ€ํ•œ ๊ณต๋ถ€๋ฅผ ๋งŽ์ด ํ•˜์ง€๋Š” ์•Š์•˜์Šต๋‹ˆ๋‹ค.

๋Œ€ํšŒ ์‹œ์ž‘ ์ „๋‚ ๊นŒ์ง€ ํŒ€๋…ธํŠธ๋ฅผ ์ž‘๋…„ ์ œ ํŒ€๋…ธํŠธ์— ์–น์–ด์„œ ๋‚˜๋ฆ„๋Œ€๋กœ ์—ด์‹ฌํžˆ ์ค€๋น„ํ–ˆ์Šต๋‹ˆ๋‹ค. ํ›„์ˆ ํ•˜์ง€๋งŒ, ์•ฝ๊ฐ„์˜ ๋ถ€์กฑํ•จ์€ ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค.

ํŒ€๋…ธํŠธ๋ฅผ ์ค€๋น„ํ•  ๋•Œ ์ƒ๊ฐํ•ด์•ผ ํ•˜๋Š” ๊ธฐ์ค€์€, (๋ณดํŽธ ํƒ€๋‹นํ•œ ์ƒ๊ฐ์„ ์ œ๊ฐ€ ๋‚˜๋ฆ„๋Œ€๋กœ ํ‘œํ˜„ํ•ด ๋ณด์ž๋ฉด) โ€œ์–ด ์ด๊ฑฐ ๊ทธ๊ฑด๋ฐโ€ ์™€ AC๋ฅผ ๋ฐ›๋Š” ์‹œ์  ์‚ฌ์ด์˜ ์‹œ๊ฐ„์˜ expectation์„ minimizeํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ด ๋ง์˜ ์˜๋ฏธ๋Š”, ๊ตฌํ˜„ ์‹ค์ˆ˜๊ฐ€ ๋‚ ๋งŒํ•œ ๋ถ€๋ถ„๋“ค์ด๋‚˜ ๊ตฌํ˜„์ด ๋ณต์žกํ•œ ์ž๋ฃŒ๊ตฌ์กฐ, ์•Œ์ง€๋งŒ ๊ตฌ๊ธ€๋ง ์—†์ด๋Š” ์ฝ”๋”ฉ์ด ๋ถˆ๊ฐ€๋Šฅํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋“ฑ์„ ์ ์–ด ๊ฐ€์•ผ ํ•œ๋‹ค๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ €ํฌ ํŒ€์„ ์˜ˆ๋กœ ๋“ค์ž๋ฉด

  • ์ˆ˜๋งŽ์€ ๊ธฐํ•˜ ๊ตฌํ˜„์„ ์ค€๋น„ํ–ˆ์Šต๋‹ˆ๋‹ค. ๋Œ€ํšŒ ์‹œ๊ฐ„ ์ค‘์— ์„ ๋ถ„ - ์„ ๋ถ„ ๊ต์ฐจ๋ฅผ ๊ตฌํ˜„ํ•ด ๋ณด์…จ๋‚˜์š”? ใ…‹ใ…‹!
  • segment tree์—์„œ lazy propagation์˜ ๊ฐœ๋…์€ ์ž˜ ์•Œ๊ณ  ์žˆ์œผ๋‚˜ ๊ตฌํ˜„์‹œ ์‹ค์ˆ˜ํ•  ๊ฒƒ์„ ๋Œ€๋น„ํ•˜์—ฌ ์ ์–ด ๊ฐ”์Šต๋‹ˆ๋‹ค.
  • Dinic๊ณผ HeavyLight Decomposition ๋“ฑ์„ ์ ์–ด ๊ฐ”์Šต๋‹ˆ๋‹ค.

25ํŽ˜์ด์ง€๋Š” ํšจ์œจ์ ์œผ๋กœ ์ž˜ ๊พน๊พน ๋ˆŒ๋Ÿฌ ์“ฐ๋ฉด ์ƒ๊ฐ๋ณด๋‹ค ๊ฝค ๋งŽ์Šต๋‹ˆ๋‹ค. ์ €ํฌ ํŒ€๋…ธํŠธ๋Š” [๋งํฌ] ์—์„œ ๋ณผ ์ˆ˜ ์žˆ๋Š”๋ฐ, ICPC ์ „๋‚  ๊ธ‰ํ•˜๊ฒŒ ๋งŽ์€ ๊ฒƒ์„ ์ถ”๊ฐ€ํ•˜๋Š๋ผ ์™ธ๊ด€์˜ ์•„๋ฆ„๋‹ค์›€์„ ๋งŽ์ด ์žƒ์–ด๋ฒ„๋ ธ์Šต๋‹ˆ๋‹ค๋งŒ ์•ž์œผ๋กœ ๊ณ„์† ์—…๋ฐ์ดํŠธ๋  ๊ฒƒ์ž…๋‹ˆ๋‹ค (์ œ ๊ฐœ์ธ์ ์œผ๋กœ๋Š” archive์˜ ์˜๋ฏธ๊ฐ€ ์žˆ์–ด์„œ์š”.)

ํŒ€๋…ธํŠธ ๋งจ ๋์žฅ์—๋Š” Checkpoint๋ฅผ ๋ถ™์—ฌ ๊ฐ”์Šต๋‹ˆ๋‹ค. ์ด ์ฒดํฌํฌ์ธํŠธ๋Š” ์ œ๊ฐ€ ๊ณ„์† ๊ด€๋ฆฌํ•˜๊ณ  ์žˆ๋Š” ๋…ธํŠธ์ธ๋ฐ, ์ œ๊ฐ€ ๋‚˜๊ฐ€๋Š” ํŒ€๋Œ€ํšŒ์—์„œ๋Š” ํŒ€๋…ธํŠธ ๋งจ ๋์žฅ์— ๋ถ™์—ฌ ๋‚˜๊ฐ‘๋‹ˆ๋‹ค. picture 1
(์ด๋ฏธ์ง€๋ฅผ ์šฐํด๋ฆญ-์ƒˆ ํƒญ์œผ๋กœ ์—ด๊ธฐํ•ด์„œ ํฐ ํ™”๋ฉด์œผ๋กœ ๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค)

๋ชจ๋“  ํฌ์ธํŠธ๋“ค์€ ์ œ๊ฐ€ ๋ฌธ์ œ๋ฅผ ํ’€๋ฉด์„œ ๊ฒฝํ—˜ํ•ด๋ณธ ๊ฒƒ๋“ค์ž…๋‹ˆ๋‹ค. PS ์˜ค๋‹ต๋…ธํŠธ๋ผ๊ณ ๋‚˜ ํ• ๊นŒ์š”.

๋ณธ ๋Œ€ํšŒ

์ €ํฌ๋Š” ์Šคํ„ฐ๋””์นดํŽ˜์—์„œ ๋Œ€ํšŒ๋ฅผ ์น˜๋ €๊ธฐ ๋•Œ๋ฌธ์—, ๋ฌธ์ œ์ง€๊ฐ€ ๋œจ๋Š”๊ฑธ ํ™•์ธํ•˜๋Š” ์ฆ‰์‹œ ์ œ๊ฐ€ ์ธ์‡„๋ฅผ ํ•˜๋Ÿฌ ๋‚˜๊ฐ€๋ฉด์„œ ํŒ€์›๋“ค์ด ํ™”๋ฉด์„ ๋ฐ˜์œผ๋กœ ๋‚˜๋ˆ ์„œ A, B๋ฅผ ์ฝ์—ˆ์Šต๋‹ˆ๋‹ค. ๋ฌธ์ œ์ง€ ์ธ์‡„๊นŒ์ง€๋Š” ํ”„๋ฆฐํ„ฐ๊ฐ€ ๋Š๋ฆฐ๋ฐ๋‹ค ๋ฌธ์ œ์ง€ ํ•ฉ๋ณธ pdf ํŒŒ์ผ์ด ๋ฐ”๋กœ ๋„˜์–ด์˜ค์ง€ ์•Š์•„์„œ, ๊ฑฐ์˜ 7๋ถ„ ๊ฐ€๊นŒ์šด ์‹œ๊ฐ„์ด ์†Œ์š”๋˜์—ˆ์Šต๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ ๋ฌธ์ œ์ง€๋ฅผ ์ธ์‡„ํ•˜๋Š” ํ”„๋ฆฐํ„ฐ ์•ž์— ์„œ์„œ ์ €๋„ ๋ฌธ์ œ๋ฅผ ๋ณผ ์ˆ˜ ์žˆ์—ˆ๊ธฐ ๋•Œ๋ฌธ์— ์‹ค์งˆ์ ์ธ ์‹œ๊ฐ„์ƒ์˜ ๋กœ์Šค๋Š” ๊ฑฐ์˜ ์—†์Šต๋‹ˆ๋‹ค. ๋Œ€ํšŒ ๊ทœ์ •์ƒ ํŒ€์› 1์ธ ์ด์ƒ์ด ์˜ค๋žœ ์‹œ๊ฐ„ ์ž๋ฆฌ๋ฅผ ๋น„์›Œ์„œ๋Š” ์•ˆ๋˜๊ณ  (์•„๋งˆ๋„ ์ด ๊ทœ์ •์ด strictly enforce๋˜๋Š” ๊ฒƒ์€ ์–ด์ฐจํ”ผ ๊ธฐ์ˆ ์ ์œผ๋กœ ๋ถˆ๊ฐ€๋Šฅํ–ˆ์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค๋งŒ), ํŒ€์›๋“ค์˜ ํšจ์œจ์„ ์œ„ํ•ด ๋ฌธ์ œ์ง€๊ฐ€ 1/3์ •๋„ ์ธ์‡„๋  ๋•Œ๋งˆ๋‹ค ์ œ๊ฐ€ ๊ณ„์† ํŒ€์›๋“ค์—๊ฒŒ ๋ฐฐ๋‹ฌํ–ˆ์Šต๋‹ˆ๋‹ค.

๊ทธ ์‚ฌ์ด์—, I๋ฒˆ์˜ ์ฒซ Solve๋“ค์ด ๋“ฑ์žฅํ•˜๊ธฐ ์‹œ์ž‘ํ–ˆ์Šต๋‹ˆ๋‹ค. ์ฒ˜์Œ์— ์–ด๋–ป๊ฒŒ ๋‹ค๋ฅธ ํŒ€๋“ค์ด 12๋ฌธ์ œ ์ค‘ 9๋ฒˆ์งธ์— ์žˆ๋Š” ๋ฌธ์ œ๋ฅผ ์ฐพ์•„๋‚ด์„œ ํ’€์—ˆ๋Š”์ง€ ์˜์•„ํ–ˆ์ง€๋งŒ, ์ƒ๊ฐํ•ด๋ณด๋‹ˆ 4/4/4๋กœ ๋ถ„๋ฐฐํ•˜๋ฉด ํŒ€์›์ค‘ ํ•œ๋ช…์—๊ฒŒ๋Š” ๊ฐ€์žฅ ๋จผ์ € ์ฝ๋Š” ๋ฌธ์ œ๋‹ˆ๊นŒ ๊ทธ๋Ÿฐ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค. (๊ทธ๋Ÿผ์—๋„ ์•ฝ๊ฐ„์˜ ์˜๋ฌธ์ด ์žˆ์Šต๋‹ˆ๋‹ค. ์ฐพ์•„๋ณด๋‹ˆ ์ž‘๋…„์—๋„ I๋ฒˆ์ด ๊ฐ€์žฅ ์‰ฌ์šด ๋ฌธ์ œ์˜€๊ณ , ๊ทธ ์ „๊นŒ์ง€๋Š” ๋“ฑ๋ก์ด ์žˆ๋Š” ์ž๋ฆฌ์˜€๋Š”๋ฐ ํ˜น์‹œ ๊ทธ ์‚ฌ์‹ค์„ ์ธ์ง€ํ•˜๊ณ  ์žˆ๋Š” ํŒ€๋“ค์ด ์žˆ์„๊นŒ์š”?)

์ธ์‡„ ์ค‘์— ์ €๋Š” ํŒ€์›๋“ค์ด A, B ๋ถ€ํ„ฐ ์ฝ๊ณ  ์žˆ์Œ์„ ๊ฐ์•ˆํ•˜์—ฌ ์ ๋‹นํžˆ ๋ช‡๊ฐœ ๋–ผ๊ณ  E๋ฅผ ์ฝ์—ˆ์Šต๋‹ˆ๋‹ค. ํ•œ๊ตญ์–ด๊ธธ๋ž˜ ์Šฌ์ฉ B, C๋„ ํ•œ๋ฒˆ์”ฉ ์ฝ์—ˆ๋Š”๋ฐ B๋Š” ๋”ฑ๋ด๋„ ๊ตฌํ˜„์ด ๋…ธ๋‹ต์ด๊ณ  C๋Š” ์—„์ฒญ๋‚˜๊ฒŒ ์–ด๋ ค์›Œ ๋ณด์˜€๊ธฐ ๋•Œ๋ฌธ์—โ€ฆ ์ œ๊ฐ€ ์ธ์‡„๋ฅผ ๋งˆ์น˜๋ฉด์„œ 2์‹œ 8๋ถ„์ฏค ๋ฐฉ์— ๋ณต๊ท€ํ–ˆ๋Š”๋ฐ, ์ด๋ฏธ ํŒ€์›๋“ค์ด I๋ฒˆ์„ ์ฝ๊ณ  ์†”๋ฃจ์…˜์„ ์ œ์‹œํ–ˆ์œผ๋ฉฐ B๊ฐ€ ๊ตฌํ˜„ ๋…ธ๋‹ต์ด๋ผ๋Š” ์‚ฌ์‹ค๋„ ์ธ์ง€ํ•˜๊ณ  ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค.

Problem I : Sport Climbing Combined

Solve : DHdroid
Code : DHDroid

๋ฌด์Šจ ๋ฌธ์ œ์ธ์ง€ ๋ฐฉ๊ธˆ ์ฒ˜์Œ ์ฝ์—ˆ๋Š”๋ฐ, ๋”ฑํžˆ ํ• ๋ง์ด ์—†์Šต๋‹ˆ๋‹ค. $p_i \times q_i \times r_i$๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌํ•ด์„œ ๊ทธ $b_i$๋ฅผ ์ถœ๋ ฅํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค. 13๋ถ„์— AC๋ฅผ ๋ฐ›์•˜์Šต๋‹ˆ๋‹ค.

์ด๋•Œ ์ €๋Š” E๋ฒˆ์˜ ํ’€์ด๊ฐ€ ๊ฐ„๋‹จํ•œ $O(B N^2)$ DP๋กœ ๊ฐ€๋Šฅํ•˜๋‹ค๋Š” ๊ฒƒ์„ ์ด๋ฏธ ์ธ์ง€ํ–ˆ๊ธฐ ๋•Œ๋ฌธ์— ($30 * 4000^2$ ์ด๋ฉด 4.8์–ต์ด์ง€๋งŒ ์‹ค์ œ๋กœ๋Š” ๊ทธ ์ ˆ๋ฐ˜๋งŒ ์จ์„œ ๊ดœ์ฐฎ์Šต๋‹ˆ๋‹ค), ๋ฐ”๋กœ ์ œ๊ฐ€ E๋ฅผ ์žก๊ฒ ๋‹ค๊ณ  ์ฃผ์žฅํ–ˆ์Šต๋‹ˆ๋‹ค. ์•„๋ฌด๋„ E๋ฅผ ํ’€์ง€ ์•Š์•˜๋‹ค๋Š” ์‚ฌ์‹ค์ด ์ข€ ๋งˆ์Œ์— ๊ฑธ๋ฆฌ์ง€๋งŒโ€ฆ

Problem E : Histogram

Solve : Gratus907
Code : Gratus907

๋ฐฐ์—ด์„ ์ตœ๋Œ€ B๊ฐœ์˜ ๊ตฌ๊ฐ„์œผ๋กœ ๋‚˜๋ˆ„์–ด, ๊ฐ ๊ตฌ๊ฐ„์—์„œ์˜ ๋ถ„์‚ฐ์˜ ํ•ฉ์„ ์ตœ์†Œํ™”ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. $n$์ด ๋” ์ปค์ง€๋ฉด DP ์ตœ์ ํ™” ๊ธฐ๋ฒ• ๋“ฑ์„ ์ƒ๊ฐํ•ด ๋ณผ ์ˆ˜ ์žˆ๊ฒ ์ง€๋งŒ, ์ด์ •๋„๋Š” $B \times N$ ํ…Œ์ด๋ธ”์„ ์นธ๋‹น $O(N)$ ์— ๊ตฌํ•ด๋„ ์ถฉ๋ถ„ํ•ฉ๋‹ˆ๋‹ค.

๋จผ์ €, ์–ด๋–ค ๊ตฌ๊ฐ„ $[j, i]$ ์˜ ๋ถ„์‚ฐ $V(j, i)$ ์„ $O(1)$์— ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค๋ฉด, ์ด ๋ฌธ์ œ๋Š” ๊ฐ„๋‹จํžˆ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ํ™˜์›๋ฉ๋‹ˆ๋‹ค. \(D(b, i) = \min_{j < i} V(j, i) + D(b-1, j-1)\) ๊ทธ๋Ÿฐ๋ฐ, ๋ถ„์‚ฐ์€ ์›์†Œ์˜ ํ•ฉ๊ณผ ์ œ๊ณฑ์˜ ํ•ฉ์„ ์•ˆ๋‹ค๋ฉด $O(1)$์— ๊ตฌํ•  ์ˆ˜ ์žˆ๊ณ  (์ œํ‰-ํ‰์ œ ๊ณต์‹), ์ด๋Š” prefix sum์œผ๋กœ ์ตœ์ ํ™” ๊ฐ€๋Šฅํ•œ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

์ด ๋ฌธ์ œ์˜ ๊ตฌํ˜„์€ ๊ธˆ๋ฐฉ ํ–ˆ์ง€๋งŒ, ์‹ค์ˆ˜๋กœ n์„ ์จ์•ผ ํ•  ์ž๋ฆฌ์— MAXN ์ธ 4000์„ ์จ๋„ฃ์–ด์„œ ํ•œ๋ฒˆ ํ‹€๋ ธ์Šต๋‹ˆ๋‹ค. ์ดํ›„ ์ด๋ฅผ ๋ฐ”๋กœ ์บ์น˜ํ•˜๊ณ , ๊ณ ์ณค์œผ๋‚˜ ๋งฅ๋ถ์— ์—ฐ๊ฒฐํ•œ ์™ธ์žฅ ํ‚ค๋ณด๋“œ์˜ ๋‹จ์ถ•ํ‚ค๊ฐ€ ์ต์ˆ™ํ•˜์ง€ ์•Š์•„์„œ(๋ณ€๋ช…๊ฐ™๊ฒ ์ง€๋งŒ ์ง„์งœ์ž…๋‹ˆ๋‹คโ€ฆ.) ์ œ์ถœ๊ณผ ๋™์‹œ์— ์–ด ์ €์žฅ ์•ˆ๋œ๊ฑฐ ์•„๋‹Œ๊ฐ€? ๋ผ๋Š” ๋น„๋ช…์„ ์ง€๋ฅด๋ฉฐ 1๋ฒˆ ๋” ํ‹€๋ฆฌ๊ณ  2ํ‹€ ํ›„ 23๋ถ„์— AC๋ฅผ ๋ฐ›์•˜์Šต๋‹ˆ๋‹ค.

์ €ํฌ ํŒ€์ด ์ด ๋ฌธ์ œ First Solve๋ฅผ ๋ฐ›์•˜์Šต๋‹ˆ๋‹ค. ๊ฐœ์ธ์ ์œผ๋กœ ICPC๊ฐ™์€ ํฐ ๋Œ€ํšŒ์—์„œ ํผ์†”์€ ์ฒ˜์Œ์ด๋ผ ๊ต‰์žฅํžˆ ๊ธฐ๋ถ„์ด ์ข‹์•˜์Šต๋‹ˆ๋‹ค. ใ…‹ใ…‹!!

์ด์ œ, Coffeetea๊ฐ€ โ€˜B๋ฒˆ์€ ๋ฏธ์นœ๋“ฏ์ด ์ผ€์ด์Šค๋ฅผ ๋‚˜๋ˆ ์•ผ ํ•œ๋‹ค. ์ผ๋‹จ ๊ตฌํ˜„์„ ์‹œ์ž‘ํ•˜๊ฒ ์ง€๋งŒ ๋ˆ„๊ตฐ๊ฐ€ ์งค๊ฒŒ์žˆ์œผ๋ฉด ๋ฐ”๋กœ ์ธํ„ฐ์…‰ํŠธํ•ด์„œ ๋‹ค๋ฅธ๊ฑฐ ๊ตฌํ˜„ ํ•˜๋Š”๊ฒŒ ์ข‹๊ฒ ๋‹คโ€™ ๋Š” ๋ง์„ ํ–ˆ๊ณ , ๊ณง DHDroid๊ฐ€ J๋ฅผ ๋ฐ”๋กœ ์งค์ˆ˜์žˆ๋‹ค๊ณ  ์„ ์–ธํ•ด์„œ ์ปดํ“จํ„ฐ๋ฅผ ๋‚ด์คฌ์Šต๋‹ˆ๋‹ค.

์ถ”๊ฐ€๋กœ, ์ €๋Š” A๋ฒˆ์„ ์ฝ๊ณ  ๋ฐ”๋กœ โ€˜์ˆ˜์ฟผ ์–ด๋”˜๊ฐ€์— ์žˆ์„ ๋ฒ•ํ•œ ๋ฌธ์ œ๋‹คโ€™, โ€˜Moโ€™s Algorithm์œผ๋กœ ํ’€ ์ˆ˜ ์žˆ์„ ๊ฒƒ ๊ฐ™์€๋ฐ, ๋‚ด๊ฐ€ ๊ทธ๊ฑฐ ๊ตฌํ˜„์„ ๋ชปํ•œ๋‹ค. ์ •ํ™•ํžˆ ์ดํ•ดํ•œ๊ฒŒ ์•„๋‹ˆ๋ผ์„œ ํŒ€๋…ธํŠธ์—๋„ ๋ชป์ ์–ด์™”๋‹คโ€™ ๊ณ  ๋งํ–ˆ์Šต๋‹ˆ๋‹ค. ์ด๋•Œ ๋˜ ์›ฐ๋…ธ์šด ๋‹นํ–ˆ๋‹ค๋Š” ์ƒ๊ฐ์— ๊ต‰์žฅํžˆ ํ™”๊ฐ€ ๋‚ฌ์Šต๋‹ˆ๋‹ค. ใ…‹ใ…‹โ€ฆ

Problem J : Ten

Solve : DHDroid
Code : DHDroid

์ˆซ์ž๊ฐ€ ๊ฐ€๋“ ์ฃผ์–ด์ง€๊ณ  ํ•ฉ์ด 10์ด ๋˜๋Š” ์ง์‚ฌ๊ฐํ˜•์˜ ๊ฐœ์ˆ˜๋ฅผ ์„ธ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์ผ๋ฐ˜์ ์œผ๋กœ๋Š” ๋ชจ๋“  ์ง์‚ฌ๊ฐํ˜•์„ ๋ณผ ์ˆ˜ ์—†์œผ๋‚˜, ์ด ๋ฌธ์ œ์—์„œ๋Š” ๊ฐ ์ˆซ์ž๊ฐ€ 1 ์ด์ƒ์ด๋‹ค๋ณด๋‹ˆ ํฌ๊ธฐ๊ฐ€ 10์„ ๋„˜๋Š” ์ง์‚ฌ๊ฐํ˜•๋“ค์„ ๋ณผ ํ•„์š”๊ฐ€ ์—†์–ด์„œ bruteforceํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. DHDroid๊ฐ€ 2์ฐจ์› ๋ถ€๋ถ„ํ•ฉ ์ž˜ ์งœ๋ƒ๊ณ  ๋ฌผ์–ด๋ด์„œ ๋ชปํ•œ๋‹ค๊ณ  ๋Œ€๋‹ตํ•˜๋‹ˆ๊นŒ ์•„๋‹ˆ;;; ์ด๋Ÿฌ๋ฉด์„œ ์•Œ์•„์„œ ์ž˜ ์งœ๋”๊ตฐ์š”โ€ฆใ…‹ใ…‹ใ…‹ 40๋ถ„ AC.

์ด์‹œ์  ์ €ํฌ์˜ ์ˆœ์œ„๋Š” ์ตœ์ƒ์œ„๊ถŒ์ด์—ˆ๊ธฐ ๋•Œ๋ฌธ์— (์ •ํ™•ํžˆ 40๋ถ„ ์‹œ์ ์— ์ €ํฌ๋Š” E, I, J๋ฅผ ํ’€์—ˆ๊ณ , 3์†” ํŒ€ ๋‹ค์„ฏ ํŒ€์ด ๊ฐ๊ฐ E, E, B, H, K๋ฅผ ํ’€์—ˆ์œผ๋ฉฐ 4์†” ์ด์ƒ ํŒ€์ด ์—†์–ด์„œ ์ €ํฌ๋Š” 5๋“ฑ์ด์—ˆ์Šต๋‹ˆ๋‹ค) ์Šค์ฝ”์–ด๋ณด๋“œ๋ฅผ ๋ณด๊ณ  ๋‹ค์Œ ํ’€ ๋ฌธ์ œ๋ฅผ ๋ฐ”๋กœ ์•Œ ์ˆ˜ ์—†์—ˆ๊ณ , B๋ฒˆ์˜ ์ผ€์ด์Šค๋ฅผ ์—ด์‹ฌํžˆ ๋‚˜๋ˆ„๋˜ coffeetea์™€ ์ œ๊ฐ€ ์ข€ ์–˜๊ธฐ๋ฅผ ํ•ด๋ณด๋‹ˆ๊นŒ H๋ฒˆ์„ ๊ธˆ๋ฐฉ ํ’€ ์ˆ˜ ์žˆ์„ ๊ฒƒ ๊ฐ™์•˜์Šต๋‹ˆ๋‹ค. ์ œ๊ฐ€ ํ’€์ด์˜ ํ™•์‹คํ•จ์„ ์ž ๊น ๊ณ ๋ฏผํ•˜๋Š” ๋™์•ˆ Coffeetea๊ฐ€ ํ•œ 7~8๋ถ„? ์ •๋„ ์ฝ”๋”ฉ์„ ์ข€ ํ•˜๋‹ค๊ฐ€, ์ œ๊ฐ€ H๋ฒˆ ํ’€ ์ˆ˜ ์žˆ๋‹ค๊ณ  ๋งํ•ด์„œ ๋ฐ”๋กœ ๋ฐ”๊ฟจ์Šต๋‹ˆ๋‹ค.

Problem H : Similarity

Solve : Gratus907, Coffeetea (B๋ฒˆ์— ๋Œ€ํ•ด ์ƒ๊ฐํ•˜๋Š๋ผ ๋งŽ์€ ์ฐธ์—ฌ๋Š” ๋ชปํ–ˆ์Šต๋‹ˆ๋‹ค)
Code : Gratus907

๋‘ ๋ฐฐ์—ด $P, Q$๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, $p_i < p_j < p_k$ ์ด๋ฉด์„œ $q_i < q_j < q_k$ ์ธ ์ธ๋ฑ์Šค $(i, j, k)$ ์˜ ๊ฐœ์ˆ˜๋ฅผ ์„ธ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

$i$๋ฒˆ์งธ ์ธ๋ฑ์Šค๋ฅผ ์  $(p_i, q_i)$๋กœ ํ‘œํ˜„ํ•ด ๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. ๊ทธ๋ ‡๋‹ค๋ฉด, 2์ฐจ์› ๋ฐฐ์—ด ์œ„์—์„œ, ์šฐ๋ฆฌ๊ฐ€ ์›ํ•˜๋Š” ์ธ๋ฑ์Šค๋“ค์€ ๋‚˜์˜ โ€˜์™ผ์ชฝ ์•„๋ž˜โ€™ ์ง์‚ฌ๊ฐํ˜•์— ์žˆ๋Š” ์ ๋“ค๊ณผ, โ€˜์˜ค๋ฅธ์ชฝ ์œ„โ€™ ์ง์‚ฌ๊ฐํ˜•์— ์žˆ๋Š” ์ ๋“ค์ž…๋‹ˆ๋‹ค. ์ฆ‰ 2์ฐจ์› ํ‰๋ฉด์—์„œ ์–ด๋–ค ์ง์‚ฌ๊ฐํ˜• ์•ˆ์— ์ ์ด ๋ช‡ ๊ฐœ ์žˆ๋Š”์ง€๋ฅผ ๋น ๋ฅด๊ฒŒ ์…€ ์ˆ˜ ์žˆ๋‹ค๋ฉด - ๊ตฌ์ฒด์ ์œผ๋กœ, ๋‚ด โ€˜์™ผ์ชฝ ์•„๋ž˜โ€™ ์™€ โ€˜์˜ค๋ฅธ์ชฝ ์œ„โ€™ ์ง์‚ฌ๊ฐํ˜• - ์ด ๋ฌธ์ œ๋ฅผ ํ’€ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์–ธ๋œป ์ƒ๊ฐํ•˜๋ฉด 2D segment tree ๊ฐ™์€๊ฒŒ ํ•„์š”ํ•  ๊ฒƒ ๊ฐ™์ง€๋งŒ, ์ž˜ ์•Œ๋ ค์ง„ ํ…Œํฌ๋‹‰์œผ๋กœ ์ด๋ฅผ 1D ์„ธ๊ทธ๋งŒ์œผ๋กœ ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ๋Š” ์—…๋ฐ์ดํŠธ ์ˆœ์„œ์— ์˜ํ–ฅ์„ ๋ฐ›๊ธฐ ๋•Œ๋ฌธ์—, ์ถ• ํ•˜๋‚˜์˜ ์ •๋ณด๋ฅผ โ€˜์—…๋ฐ์ดํŠธ ์ˆœ์„œโ€™ ๋ฅผ ์ด์šฉํ•ด์„œ ํ‘œํ˜„ํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. $x$์ขŒํ‘œ๋ฅผ ์ด์šฉํ•œ ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ๋ฅผ ๊ตฌํ˜„ํ•˜๋˜, $y$์ขŒํ‘œ๊ฐ€ ํฐ ์›์†Œ๋ถ€ํ„ฐ ์—…๋ฐ์ดํŠธํ•œ๋‹ค๊ณ  ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ์ด๋•Œ, ์–ด๋–ค ์ ์„ ์—…๋ฐ์ดํŠธํ•˜๊ธฐ ์ง์ „์— $[x+1, \infty]$ ์˜ ์ฟผ๋ฆฌ๋ฅผ ๋‚ ๋ ค์„œ ์ ์˜ ๊ฐœ์ˆ˜๋ฅผ ์„ธ๋ฉด, ์•„์ง ๋‚˜๋ณด๋‹ค ์•„๋ž˜ ์žˆ๋Š” ์ ์€ ์—…๋ฐ์ดํŠธ๋ฅผ ์•ˆ ํ–ˆ๊ธฐ ๋•Œ๋ฌธ์— ์‹ค์ œ๋กœ ๋ณด์ด๋Š” ๊ณต๊ฐ„์€ ๋‚ด ์˜ค๋ฅธ์ชฝ ๋ฐ˜ํ‰๋ฉด์ด ์•„๋‹ˆ๋ผ ๋‚ด ์˜ค๋ฅธ์ชฝ ์œ„ ์‚ฌ๋ถ„๋ฉด์ž…๋‹ˆ๋‹ค. ์ด๋ฅผ ๋‘๊ฐœ ์ด์šฉํ•ด์„œ ์šฐ์ƒ๋‹จ๊ณผ ์ขŒํ•˜๋‹จ์„ ๊ฐ๊ฐ ์„ธ๋ฉด ๋ฉ๋‹ˆ๋‹ค. ๊ฐ™์€ $y$์ขŒํ‘œ์ธ ๊ฒฝ์šฐ ๋ˆ„๊ฐ€ ๋ˆ„๊ตฌ๋ฅผ ๋ณผ ์ˆ˜ ์žˆ์–ด์•ผ ํ•˜๋Š”์ง€๋ฅผ ๊ณ ๋ คํ•˜๋ฉด ๋˜๋Š”๋ฐ ์—ฌ๊ธฐ์„œ๋Š” $x$์ขŒํ‘œ๊ฐ€ ์ž‘์€์ชฝ๋ถ€ํ„ฐ ์—…๋ฐ์ดํŠธํ•ด์ฃผ๋ฉด ๋ฉ๋‹ˆ๋‹ค. ์™ผ์ชฝ์— ์žˆ๋Š” ์›์†Œ๊ฐ€ ์˜ค๋ฅธ์ชฝ ์›์†Œ๋ฅผ ๋ณด๊ฒŒ๋˜๋ฉด โ€˜์˜ค๋ฅธ์ชฝ ์œ„โ€™ ๊ฐ€ ์•„๋‹ˆ๋ผ โ€˜์˜ค๋ฅธ์ชฝโ€™ ์ธ๋ฐ๋„ ํฌํ•จํ•˜๋Š” ๊ฒฝ์šฐ๊ฐ€ ์žˆ์–ด์„œ, ์™ผ์ชฝ ์›์†Œ๋Š” ์ž๊ธฐ๋ž‘ $y$์ขŒํ‘œ๊ฐ€ ๊ฐ™๊ณ  $x$์ขŒํ‘œ๊ฐ€ ํฐ ์›์†Œ๋ฅผ ๋ณผ ์ˆ˜ ์—†์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

์—ฌ๋ฆ„์— ๋‹ค๋ฅธํ•™๊ต ์ปด๊ณต๊ณผ์— ๋‹ค๋‹ˆ๋Š” ์—ฌ์ž์นœ๊ตฌ๋ž‘ ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ, DP, ๊ทธ๋ž˜ํ”„ ๊ฐ™์€ ์ฃผ์ œ ๋ช‡๊ฐœ๋กœ ํ”Œ๋ ˆ ๋ฌธ์ œ ์ผ์ฃผ์ผ์— 5-10๊ฐœ์”ฉ ๋ฐ€์—ˆ๋Š”๋ฐ 1, ๊ทธ๋•Œ ๋น„์Šทํ•œ ๋ฌธ์ œ๋ฅผ ํ’€์–ด ๋ดค์Šต๋‹ˆ๋‹ค. ๋งํฌ ์— ์žˆ๋Š” โ€˜๋ถ์„œํ’โ€™, โ€˜์—ฌ์šฐ๊ฐ€ ์ •๋ณด์„ฌ์— ์˜ฌ๋ผ์˜จ ์ด์œ โ€™ ๋“ฑ ๋ฌธ์ œ๋“ค์—์„œ ๋˜‘๊ฐ™์ด ์“ฐ์ž…๋‹ˆ๋‹ค. 72๋ถ„์— AC๋ฅผ ๋ฐ›์•˜์Šต๋‹ˆ๋‹ค.


๋Œ€ํšŒ์‹œ๊ฐ„์˜ ๋Œ€๋žต 40%๊ฐ€ ์ง€๋‚œ ์ง€๊ธˆ, ์ž ์‹œ ์ „์ฒด ์ƒํ™ฉ์„ ์กฐ๋งํ•ด๋ณด์ž๋ฉด

  • 4 Solve. 1๋“ฑ์€ 6์†”๋ธŒ, 2/3๋“ฑ์€ 5์†”๋ธŒ๋กœ ์ตœ์ƒ์œ„ํŒ€์ธ ์„œ์šธ๋Œ€ ํŒ€์€ ์ €ํฌ + B, C๋ฅผ ํ’€์—ˆ๊ณ , KAIST ํŒ€๊ณผ ๋‹ค๋ฅธ ์„œ์šธ๋Œ€ ํŒ€ ํ•˜๋‚˜๊ฐ€ ๊ฐ๊ฐ ์ €ํฌ๋ณด๋‹ค K๋ฅผ ์ถ”๊ฐ€ / (B, C) ๋ฅผ ํ’€๊ณ  H ๋ฏธํ•ด๊ฒฐ์ธ ์ƒํƒœ์˜€์Šต๋‹ˆ๋‹ค. ๋งŽ์ด ํ‹€๋ ค์„œ ํŽ˜๋„ํ‹ฐ๋ฅผ ์Œ“๊ธฐ๋Š” ํ–ˆ์ง€๋งŒ, ๋Œ€ํšŒ ์‹œ๊ฐ„ 40% ์‹œ์ ๊นŒ์ง€ ์ƒ์œ„๊ถŒ ์†”๋ธŒ์ˆ˜๋ฅผ ๋”ฐ๋ผ๋ถ™์„ ์ˆ˜ ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค.
  • B๋ฒˆ์€ Coffeetea๊ฐ€ โ€˜์ถฉ๋ถ„ํ•œ ์‹œ๊ฐ„์ด ์ฃผ์–ด์ง€๋ฉด ํ’€ ์ˆ˜ ์žˆ๋‹คโ€™ ๋Š” ์‹์œผ๋กœ ๋งํ–ˆ๋Š”๋ฐ, ์ด๊ฒŒ ์ฐธ ์–ด๋ ค์šด ๋ง์ž…๋‹ˆ๋‹ค. ๋ฐ˜๋Œ€๋กœ โ€˜์ถฉ๋ถ„ํ•œ ์‹œ๊ฐ„์ด ์ฃผ์–ด์ง€์ง€ ์•Š๋Š”โ€™ ๊ฒฝ์šฐ๋„ ๊ณ ๋ คํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.
  • K๋ฒˆ์€ DHDroid๊ฐ€ ๊ณ ๋ฏผ์„ ์ข€ ํ•ด๋ณด๊ณ  ์žˆ์—ˆ๋Š”๋ฐ, โ€˜๊ทธ๋ฆฌ๋””์ผํ…๋ฐโ€ฆ ๋ณต์žก๋„๊ฐ€โ€ฆโ€™ ์ •๋„ ์ƒํ™ฉ์ด์—ˆ์Šต๋‹ˆ๋‹ค.
  • ๋‹ค๋ฅธ ๋ฌธ์ œ์— ๋Œ€ํ•ด์„œ๋Š” ์†”์งํ•˜๊ฒŒ No clue. ์ €๋Š” C๋ฒˆ์„ ์ฝ์–ด๋ดค๊ธฐ์—, ์ตœ์ƒ์œ„๊ถŒ ํŒ€๋“ค์ด C๋ฅผ ํ’€์—ˆ๋‹ค๋Š” ์  + ์ผ๋ถ€ 4์†”ํŒ€๋“ค์ด H, ์‹ฌ์ง€์–ด E๋ณด๋‹ค๋„ C๋ฅผ ๋จผ์ € ํ’€์—ˆ๋‹ค๋Š” ์ ์ด ์ข€ ์‹ ๊ธฐํ–ˆ์Šต๋‹ˆ๋‹ค.
  • ๊ฐ๊ด€์ ์œผ๋กœ ์ด๋•Œ์˜ 4์†”ํŒ€๋“ค์ค‘์—๋Š” 2400๊ธ‰ ๊ฐ•ํŒ€๋“ค๋„ ์žˆ์ง€๋งŒ, 2019-2020 ์‹œ์ฆŒ Cafe mountain์ฒ˜๋Ÿผ ๋ง๋„์•ˆ๋˜๋Š” ํŒ€์€ ์—†๋Š” ๊ฒƒ์œผ๋กœ ์•Œ๊ธฐ ๋•Œ๋ฌธ์— ์ด๋“ค์˜ ์•ก์…˜์€ ์œ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.

์ด๊ฒƒ๋“ค์„ ๊ณ ๋ คํ•ด์„œ, ๋‹ค์‹œ Coffeetea๊ฐ€ ํ‚ค๋ณด๋“œ๋ฅผ ์žก์€์ฑ„๋กœ ์ €ํฌ๋Š” K๋ฅผ ํ’€๊ณ ์ž ํ–ˆ์Šต๋‹ˆ๋‹ค. ๋Œ€ํšŒ๊ฐ€ ๋๋‚  ๋•Œ๊นŒ์ง€ ์•„๋งˆ๋„ B, K๋Š” ํ’€ ์ˆ˜ ์žˆ์„๊ฒƒ ๊ฐ™์•˜๊ณ , ํ•˜๋‚˜ ๋” ํ’€๋ฉด ๊ดœ์ฐฎ์€ ๋“ฑ์ˆ˜๊ฐ€ ๋‚˜์˜ค์ง€ ์•Š๊ฒ ๋Š๋ƒ๋Š” ๋ง์„ ํ–ˆ์Šต๋‹ˆ๋‹ค.

Problem B : Carrot Field

Solve : Coffeetea
Code : Coffeetea

์ค‘ํ•™๊ต 1ํ•™๋…„ ์ˆ˜ํ•™ ๊ต์žฌ๋ฅผ ๋ณด๋ฉด, ๋ง ๊ฐ™์€๊ฑธ ์ง์‚ฌ๊ฐํ˜• ํ•œ ์ ์— ๊ธธ์ด๊ฐ€ $L$์ธ ์ค„๋กœ ๋ฌถ์–ด๋†“๊ณ  ๊ทธ ๋ง์ด ์›€์ง์ผ ์ˆ˜ ์žˆ๋Š” ๋ถ€๋ถ„์˜ ๋„“์ด๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ๊ฐ€ ๋งŽ์ด ๋‚˜์˜ต๋‹ˆ๋‹ค. ๊ทธ๊ฑฐ๋ž‘ ๋˜‘๊ฐ™์€๋ฐ, ๋Œ€์‹ ์— ๊ฒฉ์ž์ ์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. picture 2
์–ธ๋œป ๋ณด๋ฉด ์ถฉ๊ฒฉ์ ์œผ๋กœ ์‰ฌ์›Œ ๋ณด์ด์ง€๋งŒ, ์ด ๋ฌธ์ œ๊ฐ€ ๋”์ฐํ•œ ์ ์€ ๊ฒฝ์šฐ๋ฅผ ๋‚˜๋ˆ ์•ผ ํ•œ๋‹ค๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. ํŽธ์˜์ƒ $w \geq h$ ๋ฅผ ๊ฐ€์ •ํ•œ๋‹ค๊ณ  ํ•  ๋•Œ, ํฌ๊ฒŒ $L < h$ ์ธ ๊ฒฝ์šฐ (์›์˜ 3/4 ๋งŒํผ), $h < L < w$ ์ธ ๊ฒฝ์šฐ (์ด๋•Œ๋Š” ๊ฐ€๋กœ์ชฝ์œผ๋กœ๋Š” ๋”ฑ ์‚ฌ๋ถ„์›๋งŒํผ์„ ๋จน์„ ์ˆ˜ ์žˆ์ง€๋งŒ, ๊ทธ๋ ค๋ณด๋ฉด ์œ„์ชฝ์œผ๋กœ๋Š” ์ž‘์€ ๋ถ€์ฑ„๊ผด์„ ๋” ์ƒ๊ฐํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค), $w < L$ ์ธ ๊ฒฝ์šฐ๊ฐ€ ์žˆ์œผ๋ฉฐ, $w < L$ ์ธ ๊ฒฝ์šฐ์—๋Š” ๋‘ ์ ์—์„œ์˜ ๋ถ€์ฑ„๊ผด์ด ๊ฒน์น˜๋Š” ๋ถ€๋ถ„์„ ๋”ฐ๋กœ ์„ธ์„œ ๋นผ์•ผ ํ•ฉ๋‹ˆ๋‹ค.

Coffeetea๋Š” ์ด ๋ฌธ์ œ๋ฅผ ๊ฝค ์˜ค๋žœ ์‹œ๊ฐ„ ๋ถ™์žก์•˜๊ณ  (๊ตฌํ˜„์ด ์ฒด๊ณ„์ ์ด๋ ค๋ฉด ์–ด์ฉ” ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค), ๊ตฌํ˜„ํ•ด๋ณด์•˜์œผ๋‚˜ ํ‹€๋ ธ์Šต๋‹ˆ๋‹ค. ์•„๋งˆ๋„ sqrt์˜ ์ˆ˜์น˜์—๋Ÿฌ์ผ ๊ฒƒ์œผ๋กœ ๋ณด๊ณ  ๋‹ค๋ฅธ ๋‘ ์‚ฌ๋žŒ์ด epsilon์„ ๋”ํ•˜๊ฑฐ๋‚˜ ์ด๋ถ„ํƒ์ƒ‰์œผ๋กœ ์ง์ ‘ integer sqrt๋ฅผ ์งค ๊ฒƒ์„ ์ œ์•ˆํ–ˆ๊ณ , ๊ฒฐ๊ตญ ์ด๊ฒƒ ์™ธ์—๋„ ์—ฌ๋Ÿฌ ์ž์ž˜ํ•œ ๋ฒ„๊ทธ๋“ค์„ ๊ณ ์นœ ๋์— 4๋ฒˆ์งธ๋งŒ์— ๋งž์„ ์ˆ˜ ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค. 119๋ถ„ AC.

Problem K : Treasure Hunter

Solve : Gratus907, DHDroid (Coffeetea๋„ ์ž ๊น ์–˜๊ธฐ๋ฅผ ๋“ฃ๋Š”๊ฒƒ ๊ฐ™๋˜๋ฐ, ์—ฌ์ „ํžˆ B์— ๋น ์ ธ ์žˆ๋˜ ๊ฒƒ์œผ๋กœ ๊ธฐ์–ตํ•ฉ๋‹ˆ๋‹ค)
Code : Gratus907

2์ฐจ์› ๊ทธ๋ฆฌ๋“œ์—์„œ ์˜ค๋ฅธ์ชฝ ๋˜๋Š” ์•„๋ž˜๋กœ ๋‚ด๋ ค๊ฐ€๋ฉด์„œ ๋ณด๋ฌผ์„ ๋จน์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๊ทธ๋Ÿฐ๋ฐ ์™ผ์ชฝ ๋˜๋Š” ์œ„๋กœ ๋Œ์•„๊ฐˆ ์ˆ˜ ์—†์œผ๋ฏ€๋กœ ์ฒซ ๊ฒฝ๋กœ์—๋Š” ๋จน์ง€ ๋ชปํ•˜๋Š” ๋ณด๋ฌผ์ด ์žˆ์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋ชจ๋“  ๋ณด๋ฌผ์„ ๋จน๊ธฐ ์œ„ํ•ด ํ•„์š”ํ•œ ๊ฒฝ๋กœ์˜ ๊ฐœ์ˆ˜ ๊ตฌํ•˜๊ธฐ.

์ œ๊ฐ€ ์ด ๋ฌธ์ œ๋ฅผ ์žก์•˜์„๋•Œ๋Š” ์ด๋ฏธ DHDroid๊ฐ€ โ€˜๊ทธ๋ฆฌ๋””ํ•˜๊ฒŒโ€™ ๋ผ๋Š” ๋Œ€๋žต์ ์ธ ๊ฐ์€ ์žฌ ๋†จ์Šต๋‹ˆ๋‹ค. ์ฆ‰, ํ•œ์ชฝ์˜ convex hull์„ ๋”ฐ๋ผ ๊ฐ€๋ฉด์„œ ํ•˜๋‚˜ ๋จน๊ณ , ๋‹ค ์ง€์šด ๋‹ค์Œ ๋‹ค์‹œ ๋จน๊ณ .. ํ•˜๋Š” ์•„์ด๋””์–ด์ž…๋‹ˆ๋‹ค. ์ด ๋ฐฉ์‹์ด ๋‹ต์ด ๋œ๋‹ค๋Š” ๊ฒƒ์€ ์•ฝ๊ฐ„์˜ ๋…ผ์ฆ์„ ํ†ตํ•ด ์ฆ๋ช…ํ•  ์ˆ˜ ์žˆ์—ˆ์ง€๋งŒ, ์ด โ€˜์™ธ๊ณฝ์„  ๋”ฐ๋Š” ๊ฒฝ๋กœโ€™ ์˜ ๊ฐœ์ˆ˜๋ฅผ ๋น ๋ฅด๊ฒŒ ๊ตฌํ•˜๋Š” ๋ฐฉ๋ฒ•์— ๋Œ€ํ•ด์„œ๋Š” ์ข€ ์–ด๋ ค์›€์ด ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค.

ํ•œ์ฐธ ๋™์•ˆ์„ ์ƒ๊ฐํ•˜๋‹ค๊ฐ€, ์ œ๊ฐ€ โ€˜์ด ๋ณด๋ฌผ์„ ๋จน์œผ๋ฉด, ์ด ๋ณด๋ฌผ๋ณด๋‹ค ์˜ค๋ฅธ์ชฝ ์œ„์— ์žˆ๋Š” ๋ณด๋ฌผ์€ ๊ฐ™์€ ๊ฒฝ๋กœ์—์„œ๋Š” ๋จน์„ ์ˆ˜ ์—†๋‹คโ€™ ๋Š” ์‚ฌ์‹ค์„ ๊ด€์ฐฐํ–ˆ์Šต๋‹ˆ๋‹ค. ์ด์ œ ์ด๋ฅผ ์ด์šฉํ•˜๋ฉด, โ€˜๋งค๋ฒˆ upper convex hull์„ ๋”ฐ๋ฉด์„œ ๋จน๋Š”๋‹ค๊ณ  ํ•  ๋•Œ, ์ด ๋ณด๋ฌผ์„ ๋จน๊ธฐ ์œ„ํ•ด ํ•„์š”ํ•œ ์ตœ์†Œ ํšŸ์ˆ˜โ€™ ๋ฅผ ๊ตฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๊ตฌ์ฒด์ ์œผ๋กœ๋Š”, โ€˜๋‚˜๋ณด๋‹ค ์˜ค๋ฅธ์ชฝ ์œ„์— ์žˆ๋Š” ๋ณด๋ฌผ๋“ค์„ ๋จน๋Š” ๋ฐ ํ•„์š”ํ•œ ๊ฐœ์ˆ˜ + 1โ€™ ๋งŒํผ์ด ํ•„์š”ํ•ฉ๋‹ˆ๋‹ค.

์ด๋Š” ๋‹ค์‹œ ๋ญ”๊ฐ€ ์˜ค๋ฅธ์ชฝ ์œ„์— ๋Œ€ํ•œ max-2D query๋ฅผ ํ•˜๋Š” ์—ฐ์‚ฐ์ธ๋ฐ, ์ข€์•„๊นŒ ํ‘ผ H๋ฒˆ์—์„œ์ฒ˜๋Ÿผ 1D ์„ธ๊ทธ์—๋‹ค๊ฐ€ ์—…๋ฐ์ดํŠธ ์ˆœ์„œ๋ฅผ ์ž˜ ์ค˜์„œ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค! ํ•œ ๋Œ€ํšŒ์— ๊ฐ™์€ ์•„์ด๋””์–ด๋ฅผ ๋‘๊ฐœ ๋‚ธ๋‹ค๋Š” ์ ์ด ์ข€ ์˜์‹ฌ์Šค๋Ÿฌ์› ์ง€๋งŒ ์ด๊ฑธ ์ฝ”๋”ฉํ•˜๊ธฐ๋กœ ํ–ˆ์Šต๋‹ˆ๋‹ค. ์ฝ”๋”ฉ ๊ฒฐ๊ณผ WA๋ฅผ ๋ฐ›์•˜๋Š”๋ฐ, ์ด๊ฒŒ ๋ฌด์Šจ ์—๋Ÿฌ์ธ์ง€ ๋‹น์žฅ ์•Œ ์ˆ˜ ์—†์—ˆ๊ธฐ ๋•Œ๋ฌธ์—, 1ํ‹€ ํ•œ ํ›„ ์ €๋Š” ์ž ์‹œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ž์ฒด์— ๋Œ€ํ•ด ์ƒ๊ฐํ•ด๋ณด๊ฒ ๋‹ค๊ณ  ํ•˜๊ณ  ์ปดํ“จํ„ฐ๋ฅผ ๋„˜๊ฒจ์คฌ์Šต๋‹ˆ๋‹ค. ๋‹คํ–‰ํžˆ ์ œ๊ฐ€ K๋ฒˆ์„ ์ฝ”๋”ฉํ•˜๊ณ  ๋‚ด๋Š” ์‚ฌ์ด์— ๊ณ„์† ์ƒ๊ฐํ•˜๋˜ DHdroid์™€ B๋ฒˆ์„ ํ’€๊ณ  ์˜จ Coffeetea๊ฐ€ C๋ฒˆ์— ๋Œ€ํ•œ ๋ญ”๊ฐ€ ์œ ์˜๋ฏธํ•œ ๊ด€์ฐฐ๋“ค์„ ๋นŒ๋“œ์—…ํ–ˆ๊ณ , ์ž ์‹œ ๊ตฌํ˜„์„ ์‹œ๋„ํ•ด์„œ C๋ฒˆ์—์„œ WA๋ฅผ ๋ฐ›์•˜์Šต๋‹ˆ๋‹ค. C๋ฒˆ๋„ ๋‹ค์‹œ ์ƒ๊ฐํ•ด๋ณด๊ธฐ๋กœ ํ•˜๊ณ  ์ œ๊ฐ€ ๋‹ค์‹œ ์ปดํ“จํ„ฐ๋ฅผ ์žก์€ ํ›„, ๊ฐ„๋‹จํ•œ ์‹ค์ˆ˜์ž„์„ ๋ฐœ๊ฒฌํ•ด์„œ 148๋ถ„์— AC๋ฅผ ๋ฐ›์•˜์Šต๋‹ˆ๋‹ค.

Problem C : Colorful Tower of Hanoi

Solve : DHDroid, Coffeetea
Code : DHDroid

๋‚จ์€ 32๋ถ„๋™์•ˆ, Coffeetea์™€ DHDroid๋Š” C๋ฒˆ์— ๋Œ€ํ•œ ๊ธฐ์กด์˜ ํ’€์ด๊ฐ€ ํ•ด๊ฒฐํ•˜์ง€ ๋ชปํ•˜๋Š” ์ผ€์ด์Šค๋“ค์„ ์ฐพ์•„๋‚ด์„œ ์ด๋ฅผ ์žก๊ณ ์ž ํ–ˆ์Šต๋‹ˆ๋‹ค. ๊ฒฐ๊ณผ์ ์œผ๋กœ ํ’€์ด์˜ ํฐ ํ‹€์€ DhDroid๊ฐ€ ์ œ์‹œํ–ˆ๊ณ , ์—ฌ๋Ÿฌ edge case๋“ค์„ Coffeetea๊ฐ€ ๋ฐœ๊ฒฌํ•ด์„œ ๊ณ„์† ํ’€์ด์˜ ์‚ฌ์†Œํ•œ ์˜ค๋ฅ˜๋ฅผ ์ˆ˜์ •ํ–ˆ์Šต๋‹ˆ๋‹ค. ์ €๋Š” 30๋ถ„ ๋‚จ์€ ์‹œ๊ฐ„๋™์•ˆ ์ด ํ’€์ด๋ฅผ ์„ค๋ช…ํ•ด๋‹ฌ๋ผ๊ณ  ํ• ์ง€, ๋‹ค๋ฅธ ๋ญ˜ ํ• ์ง€ ๊ณ ๋ฏผํ•ด๋ดค์ง€๋งŒ ํ’€์ด ์„ค๋ช…์„ ๋“ฃ๋Š” ์‹œ๊ฐ„์ด ๋‘๋ช…์—๊ฒŒ ๊ต‰์žฅํžˆ ์•„๊นŒ์šธ ๊ฒƒ ๊ฐ™์•„์„œ ์ œ๊ฐ€ ์Šค์Šค๋กœ ์ข…์ด๋“ค์„ ๋ณด๋ฉด์„œ ์ดํ•ดํ•ด ๋ณด๋ ค๊ณ  ํ–ˆ๊ณ , ๊ฒฐ๊ตญ ๋ญ”๊ฐ€ ์žฌ๊ท€์ ์œผ๋กœ ์ž˜ ํ•œ๋‹ค๋Š” ์•„์ด๋””์–ด์ž„์€ ์ฃผ์›Œ๋“ค์–ด์„œ ๋‚ฉ๋“ํ–ˆ์ง€๋งŒ ๊ทธ ํ›„๋กœ๋Š” ์ž˜ ๋ชจ๋ฅด๊ฒ ์Šต๋‹ˆ๋‹ค.

์•„์ฃผ ๊ฐ„๋žตํ•œ ์•„์ด๋””์–ด๋Š”, ์ผ๋ฐ˜ ํ•˜๋…ธ์ดํƒ‘์ฒ˜๋Ÿผ ์›€์ง์ด๋Š”๋ฐ ํฌ๊ธฐ๊ฐ€ ๊ฐ™์€ ํŒ ๋‘๊ฐœ๊ฐ€ ์žˆ์œผ๋ฉด ์ผ๋ฐ˜ ํƒ‘์ฒ˜๋Ÿผ ์›€์ง์ด๋ฉด ๊ทธ ํŒ ๋‘๊ฐœ์˜ ์œ„์น˜๋Š” ์„œ๋กœ ๋ฐ”๋€๋‹ค๋Š” ์‚ฌ์‹ค์„ ๊ด€์ฐฐํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ดํ›„ ์ด๋ฅผ ๋ฐ”๋กœ์žก์•„์•ผ ํ•˜๋Š”์ง€ / ๊ทธ๋ ‡์ง€ ์•Š์€์ง€์— ๋”ฐ๋ผ์„œ ์ถ”๊ฐ€๋กœ ์–ผ๋งŒํผ ๋” ์›€์ง์—ฌ์•ผ ํ•˜๋Š”์ง€๋ฅผ ๊ณ„์‚ฐํ•ฉ๋‹ˆ๋‹ค. ์‹œ๊ฐ„์ด ๋  ๋•Œ DHDroid๊ฐ€ ์„ค๋ช…ํ•ด ์ฃผ๊ธฐ๋กœ ํ–ˆ์Šต๋‹ˆ๋‹ค. [ ํ’€์ด ๋“ค์–ด๊ฐˆ ์ž๋ฆฌ ]

๋งˆ์ง€๋ง‰์—๋Š” $n = 1, 2$ ๊ฐ™์€ ์ž‘์€ ์ผ€์ด์Šค๋“ค์ด ๊ณ„์† ๋ฌธ์ œ๊ฐ€ ๋˜์—ˆ์ง€๋งŒ, ์˜ํ˜ผ์„ ๋ฐ”์นœ 5ํ‹€ ๋์— 173๋ถ„์— AC๋ฅผ ๋ฐ›์„ ์ˆ˜ ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค.

Retrospect

์ €ํฌ๋Š” 7์†”๋ธŒ๋กœ 18๋“ฑ์˜ ์„ฑ์ ์„ ๊ฑฐ๋‘์—ˆ์Šต๋‹ˆ๋‹ค. 10์†” 2ํŒ€, 9์†” 2ํŒ€, 8์†” 2ํŒ€, 7์†” 12ํŒ€์ด๊ณ  ํŽ˜๋„ํ‹ฐ์‹ธ์›€์—์„œ ๋งจ ๋์œผ๋กœ ๋ฐ€๋ ธ๋„ค์š”.

์—ฌ๊ธฐ๋ถ€ํ„ฐ๋Š” ๋Œ€ํšŒ ์ž์ฒด์™€๋Š” ํฐ ์ƒ๊ด€ ์—†๋Š” ์–˜๊ธฐ๊ณ , ์ •ํ™•ํ•œ ์‚ฌ์‹ค์ด ์•„๋‹Œ ๊ฐœ์ธ์˜ ์˜๊ฒฌ (Factualํ•˜์ง€ ์•Š๋‹ค๋Š” ๋ง์ด ์•„๋‹™๋‹ˆ๋‹ค. Controversial / Personal์ด ๊ฐ€์žฅ ์ •ํ™•ํ•œ ๋ง์ผ ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค) ์— ํ•ด๋‹นํ•˜๋Š” ๋ง๋“ค์ด ๋งŽ์Šต๋‹ˆ๋‹ค. ๊ฑด์ „ํ•˜๊ณ  ๊ฑด์„ค์ ์ธ ๋น„ํŒ์€ ์–ธ์ œ๋“  ํ™˜์˜ํ•ฉ๋‹ˆ๋‹ค. ๋Œ€ํšŒ์™€ ์ƒ๊ด€์žˆ๋Š” ๋ง๋ถ€ํ„ฐ ์ƒ๊ด€์—†๋Š” ๋ง๋“ค ์ˆœ์„œ๋Œ€๋กœ ์ ์—ˆ์Šต๋‹ˆ๋‹ค.

About Problemset / Our result

  • ๋จผ์ €, ICPC์˜ ๋ฌธ์ œ๋“ค์€ OI์™€๋Š” ๋‹ค๋ฅด๊ฒŒ Syllabus๊ฐ€ ์—†์Šต๋‹ˆ๋‹ค. ์ •๋ง ๋…ผ๋ฌธ์— ๋‚˜์˜ค๋Š” ๋ฌธ์ œ๋“ค๋ถ€ํ„ฐ, ๋ณต์žกํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์—†์ด construction์œผ๋กœ ์Šน๋ถ€๋ณด๋Š” ๋ฌธ์ œ๊นŒ์ง€ widely ranged ์ž…๋‹ˆ๋‹ค. OI๊ฐ€ ์•„์ด๋””์–ด ์‹ธ์›€์ธ ๊ฒƒ๊ณผ๋Š” ์ข€ ๋‹ค๋ฆ…๋‹ˆ๋‹ค
  • ๊ทธ๋ž˜์„œ, ์ง„์ž… ์žฅ๋ฒฝ์ด ์ข€ ์žˆ์Šต๋‹ˆ๋‹ค. ํŠนํžˆ MO๋‚˜ ๋‹ค๋ฅธ ์ˆ˜ํ•™์  ์‚ฌ๊ณ ๋ ฅ์„ ์š”๊ตฌํ•˜๋Š” ๋ฐฑ๊ทธ๋ผ์šด๋“œ๋ฅผ ๊ฐ€์ง„ ์‚ฌ๋žŒ๋“ค์ด construction์€ ์ž˜ ํ• ์ˆ˜ ์žˆ์ง€๋งŒ, ๋งค๋…„ ์ธ์˜ˆ์—๋Š” FFT, LiChao Tree ๋“ฑ ํ•™๋ถ€ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ˆ˜์—…์—์„œ ๋‹ค๋ฃจ์ง€ ์•Š๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ํ•œ๋‘๊ฐœ๋ฅผ ๊ทธ๋ƒฅ ์•Œ๊ณ  ์žˆ๋Š”์ง€ ๋ฌป๋Š” ๋ฌธ์ œ๊ฐ€ ๋‚˜์˜ต๋‹ˆ๋‹ค. ์˜ฌํ•ด๋Š” A๋ฒˆ์ด ์ €๋Š” Moโ€™s algorithm์— ๋Œ€ํ•œ ๋น„์Šทํ•œ ์Šคํƒ€์ผ์˜ ๋ฌธ์ œ๋ผ๊ณ  ํŒ๋‹จํ–ˆ๊ณ , ๊ฒฐ๊ณผ์ ์œผ๋กœ Mo๋ฅผ ์“ฐ๋Š” ๊ฒƒ์€ ๋งž์ง€๋งŒ ๊ทธ๋ ‡๊ฒŒ๊นŒ์ง€ ๋‹จ์ˆœํ•œ ๋ฌธ์ œ๋Š” ์•„๋‹ˆ๋ผ๊ณ  (๋‹จ์ˆœํ•œ ๋ฐฉ๋ฒ•์€ $n \sqrt{n} \log{n}$ ์ด๊ณ  ํ†ต๊ณผํ•˜๊ธฐ ํž˜๋“ค๋‹ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค) ํ•˜๋‹ˆ ๋ฐ˜๋งŒ ๋งž์€ ๋ง์ž…๋‹ˆ๋‹ค.
  • L๋ฒˆ์ด USACO ๋ฌธ์ œ์™€ ๋น„์Šทํ•œ, ๋‚˜๋ฆ„ ์•„๋Š” ํŒ€๋“ค์€ ์•„๋Š” ๋ฌธ์ œ๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๊ทธ๋ž˜์„œ์ธ์ง€ ์ €๋Š” ํ”„๋ฆฌ์ฆˆํ›„ A๋ฒˆ์„ ์ œ์ถœํ•œ ํŒ€๋“ค์ด ๋Œ€๋ถ€๋ถ„ ๋งž์•˜์„ ๊ฒƒ์ด๋ผ๊ณ  ์ฃผ์žฅํ–ˆ๋Š”๋ฐ ๊ทธ๋Ÿฌ์ง€ ์•Š์•˜๊ณ , ๋Œ€์‹  L๋ฒˆ์ด ์ƒ๊ฐ๋ณด๋‹ค ๋งŽ์ด ํ’€๋ ธ์Šต๋‹ˆ๋‹ค.
  • ๊ทธ๋ฆฌ๊ณ  ์†”์งํžˆ H์™€ K๊ฐ€ ๊ฐ™์€ ์•„์ด๋””์–ด์ธ ๊ฒƒ์€ ์ถฉ๊ฒฉ์ด์—ˆ์Šต๋‹ˆ๋‹ค๋งŒ, K๋Š” LIS๋ฅผ ์ด์šฉํ•œ ๋” ์‰ฌ์šด ํ’€์ด๊ฐ€ ์žˆ๋‹ค๊ณ  ํ•˜๋ฏ€๋กœ ์ด๊ฒƒ๋„ ๋ฐ˜๋งŒ ๋งž๋Š” ๋ง์ธ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค.
  • ์›ฐ๋…ธ์šด์„ ์ถœ์ œํ•˜๋Š”๊ฒŒ ์–ด๋–ค ์˜๋ฏธ๊ฐ€ ์žˆ๋Š”์ง€๋Š” ์‚ฌ๋žŒ๋งˆ๋‹ค ์ƒ๊ฐ์ด ๋‹ค๋ฅผ ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ €๋Š” ๋”ฑํžˆ ์ง€์ง€ํ•˜์ง€๋„, ๋ฐ˜๋Œ€ํ•˜์ง€๋„ ์•Š์Šต๋‹ˆ๋‹ค. ๋ฌผ๋ก  ์ œ๊ฐ€ ๋ชจ๋ฅด๋Š” ์›ฐ๋…ธ์šด์ด ๋‚˜์˜ค๋ฉด ์š•ํ•˜๋Š”๊ฑด ๋‹น์—ฐํ•˜์ง€๋งŒ, ๊ทธ๊ฑด ์†”์งํžˆ ๋งํ•˜๋ฉด ์–ด์ฉ” ์ˆ˜ ์—†๋Š” ๊ฑฐ์ฃ .
  • ์ €ํฌ์˜ ์ด๋ฒˆ ๋Œ€ํšŒ๋Š” ํ˜„์žฌ ์‹ค๋ ฅ์— ๋น„์ถ”์–ด ๋ณผ ๋•Œ ์ž˜ ์น˜๋ฅธ๊ฒŒ ๋งž์Šต๋‹ˆ๋‹ค. ๋‹ค๋งŒ, Coffeetea๊ฐ€ ์‹ค๋ ฅ์„ ๋ฐœํœ˜ํ• ๋งŒํ•œ ์ง๊ด€์‹ธ์›€ ๋ฌธ์ œ๊ฐ€ ๋”ฑํžˆ ์—†์—ˆ๊ณ , ๊ฒฐ์ •์ ์œผ๋กœ ์ €ํฌํŒ€์˜ ์˜ค๋ž˜๋œ ์ „๋žต์ด์ง€๋งŒ ๊ฐœ์„ ์ ์ด ์žˆ๋Š” โ€˜๋ณต์žกํ•œ ๊ตฌํ˜„์ด ์žˆ์œผ๋ฉด, Coffeetea๋ฅผ ๋ฐ€์–ด ๋„ฃ๊ณ , ๋‚˜๋จธ์ง€ 2๋ช…์ด ๊ธฐ๋„ํ•˜๋ฉด์„œ ๋‹ค๋ฅธ ๋ฌธ์ œ๋ฅผ ํ‘ผ๋‹คโ€™ ๋Š” ์ „๋žต์„ ๋˜ ์จ์•ผ ํ–ˆ์Šต๋‹ˆ๋‹ค. B๋ฒˆ ํ•˜๋‚˜์— Coffeetea์˜ ์‹œ๊ฐ„์„ ๊ฑฐ์˜ ์ ˆ๋ฐ˜์ด๋‚˜ ๊ฐˆ์•„ ๋ฒ„๋ฆฐ ๊ฒƒ์€ ์ข‹์€ ์ „๋žต์€ ์•„๋‹™๋‹ˆ๋‹ค.
  • ๊ทธ๋Ÿผ์—๋„ ๋ถˆ๊ตฌํ•˜๊ณ , ๊ทธ๋Ÿฌ์ง€ ์•Š์•˜์œผ๋ฉด ์ €๋Š” B๋ฒˆ AC๋ฅผ ๋ชป ๋ฐ›์•˜์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค. DHDroid๋„ ๋”ฑํžˆ ์ด๋Ÿฐ ๋ฌธ์ œ๋ฅผ ์ €๋ณด๋‹ค ์ž˜ ํ•˜์ง„ ์•Š์Šต๋‹ˆ๋‹ค. ใ…‹ใ…‹โ€ฆ
  • ํŠน๋ณ„ํžˆ ์•„์‰ฌ์›€์ด ๋‚จ๋Š”๊ฑด ์—†์Šต๋‹ˆ๋‹ค. ์‚ฌ์†Œํ•œ ์‹ค์ˆ˜๋กœ ํŽ˜๋„ํ‹ฐ ์‹ธ์›€์„ ๋งŽ์ด ๋ฐ€๋ ธ๋‹ค๋Š”๊ฑด ์ข€ ์•„์‰ฝ์ง€๋งŒ, ์†”๋ธŒ์ˆ˜์—์„œ ์ƒ์œ„๊ถŒ ํŒ€๋“ค์„ ๋”ฐ๋ผ๋ถ™์—ˆ๋‹ค๋Š” ์˜์˜๋Š” ํ™•์‹คํžˆ ์žˆ์Šต๋‹ˆ๋‹ค.

About my ICPC

  • ์ €๋Š” ICPC์— ๋„ค ๋ฒˆ ๋‚˜๊ฐ€ ๋ดค๊ณ , ๋ชจ๋‘ ๋ณธ์„ ์—๋Š” ๋ชป ๊ฐ”์Šต๋‹ˆ๋‹ค. ์‚ฌ์‹ค ์˜ฌํ•ด๋Š” ์ €๋ฅผ ์ œ์™ธํ•œ ๋‘๋ช…์ด ํœดํ•™์ƒ์ด๊ธฐ ๋•Œ๋ฌธ์—, ์ €ํฌ๊ฐ€ ๋ช‡ ๋“ฑ์„ ํ–ˆ๋“  ์ €๋Š” ๋ณธ์„  ์ง„์ถœ๊ถŒ์ด ์—†์—ˆ์Šต๋‹ˆ๋‹ค.

  • ์†”์งํžˆ ๋งํ•˜์ž๋ฉด ์˜ˆ์„  ์„ฑ์ ์œผ๋กœ๋Š” ๋ณธ์„ ์— ์ง„์ถœํ•˜๊ณ ๋„ ๋‚จ์„ ๋งŒํ•œ ์„ฑ์ ์„ 2019๋…„๋ถ€ํ„ฐ ๋ฐ›์•„ ์™”์ง€๋งŒ, ICPC๋Š” ๋งŽ์€ ๋Œ€ํ•™์˜ ์ถœ์ „์„ ์œ„ํ•ด ์ƒ์œ„๊ถŒ ๋Œ€ํ•™์— ๋” ์—„๊ฒฉํ•œ ๊ธฐ์ค€์„ ์ ์šฉํ•˜์—ฌ ๋ณธ์„  ํŒ€์„ ์„ ๋ฐœํ•ฉ๋‹ˆ๋‹ค. ๊ตฌ์ฒด์ ์œผ๋กœ๋Š”, ๋จผ์ € $x$ ๋ฌธ์ œ๋ฅผ ํ‘ผ ํŒ€๋“ค์„ ๋ชจ๋‘ ์„ ๋ฐœํ•˜๊ณ , ์ดํ›„์—๋Š” $x-1$ ๋ฌธ์ œ๋ฅผ ํ‘ผ ํŒ€๋“ค ์ค‘ ๊ฐ ๋Œ€ํ•™์˜ $y_i$ ์œ„ ์ด์ƒ์ธ ํŒ€โ€ฆ ์„ ์„ ๋ฐœํ•˜๋Š” ์‹์ž…๋‹ˆ๋‹ค. ์ด ๋ฐฉ์‹์„ ์ ์šฉํ•˜๋Š” ๋ฐ ์žˆ์–ด, ์–ด๋–ค ํ•™๊ต๋„ ์ด ์ถœ์ „ํŒ€์˜ 50% ์ด์ƒ์„ ๋ณธ์„ ์— ๋ณด๋‚ด์ง€ ๋ชปํ•œ๋‹ค๋Š” (๊ณผ๊ฑฐ์—” explicitํ•˜๊ฒŒ ์ ํ˜€ ์žˆ์—ˆ๋‹ค๊ณ  ํ•˜์ง€๋งŒ, ์ง€๊ธˆ์€ ์ฐพ์„ ์ˆ˜ ์—†๊ณ , ๊ทธ๋Ÿผ์—๋„ ์•„์ง ์ ์šฉ๋˜๋Š” ๊ฒƒ์œผ๋กœ ๋ณด์ด๋Š”) ๋ฃฐ ์ด ์žˆ์Šต๋‹ˆ๋‹ค. ๋งจ ์œ„์˜ ์„ ๋ฐœ ๊ธฐ์ค€์€ ์‚ฌ์‹ค์ƒ ์„œ์šธ๋Œ€๋ฅผ ์œ„ํ•ด ๋งŒ๋“ค์–ด์กŒ์œผ๋ฉฐ (์„œ์šธ๋Œ€ 15ํŒ€ ์ค‘ 7ํŒ€ ์ดํ•˜๋ฅผ ์ž๋ฅด๋Š” ์ปท์„ ์ฐพ์Šต๋‹ˆ๋‹ค), ๋ณธ์„  ์ง„์ถœ ๊ฒฝ๊ณ„์„ ์ธ 60์œ„์— (์ž‘๋…„์—๋Š” 90์œ„์˜€์„ ๊ฑฐ๊ณ  ๊ทธ๋Ÿผ ์–˜๊ธฐ๊ฐ€ ๋‹ค๋ฆ…๋‹ˆ๋‹ค) 50% ์ด์ƒ์˜ ํŒ€์„ ๋ณด๋‚ผ ์ˆ˜ ์žˆ๋Š” ํ•™๊ต๋Š” ๋ช‡ ์—†๊ธฐ ๋•Œ๋ฌธ์— (์„œ์šธ๋Œ€, KAIST, ๊ณ ๋ ค๋Œ€ ์ •๋„. ์•„๋งˆ ํ•ด์— ๋”ฐ๋ผ ๋‹ค๋ฅธ ํ•™๊ต๋“ค๋„ ๊ฐ€๋Šฅํ•œ ํ•ด๊ฐ€ ์žˆ์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค) ์‚ฌ์‹ค์ƒ ์ €๊ฒฉ๋ฐด์ด ๋ฉ๋‹ˆ๋‹ค.

  • ์ œ๊ฐ€ ์ด๋ฒˆ์— ํœดํ•™์ƒ ํŒ€์œผ๋กœ ๋‚˜๊ฐ„ ์ด์œ ๋„ ์—ฌ๊ธฐ์— ์žˆ์Šต๋‹ˆ๋‹ค. ์ €๋ž‘ ๋น„์Šทํ•œ ์ˆ˜์ค€์˜ ํŒ€์› ๋‘๋ช…์„ ๋ชจ์œผ๋ฉด ๋ณธ์„  ์ง„์ถœ์ด ์–ด์ฐจํ”ผ ์–ด๋ ค์šธ ๊ฒƒ์ด๊ณ , ์ €๋ณด๋‹ค ์›”๋“ฑํžˆ ์ž˜ํ•˜๋Š” ํŒ€์›์„ ์ฐพ์œผ๋ฉด ์–ด๋–ป๊ฒŒ ๋‚˜๊ฐ€๋ณผ ์ˆ˜ ์žˆ์„์ง€๋Š” ๋ชจ๋ฅด๊ฒ ์ง€๋งŒ ์ฒซ์งธ๋กœ๋Š” ๊ทธ๋Ÿฐ ์‚ฌ๋žŒ์ด ์ €๋ž‘ ํŒ€์„ ํ•ด์ค„์ง€๋„ ์˜๋ฌธ์ด๊ณ  ๋‘๋ฒˆ์งธ๋กœ๋Š” ํ•ด์ค€๋‹ค๊ณ  ํ•ด๋„ ์ œ๊ฐ€ ๋Œ€ํšŒ๋ฅผ ์žฌ๋ฐŒ๊ฒŒ ์ฆ๊ธฐ์ง€ ๋ชปํ•  ๊ฒƒ ๊ฐ™์•˜์Šต๋‹ˆ๋‹ค. ๊ทธ๋ž˜์„œ ํœดํ•™์ƒ ํŒ€์ด์ง€๋งŒ, ๋Œ€ํšŒ ์ž์ฒด๋ฅผ ์ง„์‹ฌ์œผ๋กœ ์ฆ๊ธธ ์ˆ˜ ์žˆ๋Š” - ์ผ์ข…์˜ ์ฆ๊ฒœํŒ€์ด๋ผ๊ณ  ํ• ๊นŒ์š” - Little Piplup์— ๋‹ค์‹œ ํ•จ๊ป˜ํ–ˆ์Šต๋‹ˆ๋‹ค.

  • ์ด monotonicํ•˜์ง€ ์•Š์€ ์„ ๋ฐœ ๊ธฐ์ค€์— ๋Œ€ํ•ด ์–ด๋–ป๊ฒŒ ์ƒ๊ฐํ•˜๋Š”์ง€๋Š” ์‚ฌ๋žŒ๋งˆ๋‹ค ๋‹ค๋ฅธ ์˜์—ญ์ธ ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค. ์ €๋Š” ๋‹น์—ฐํžˆ ์ด ๊ธฐ์ค€์œผ๋กœ ๋ณธ์„  ๋ฌด๋Œ€๋ฅผ ๋ชป ๋ฐŸ์•˜์œผ๋ฏ€๋กœ ๊ต‰์žฅํžˆ ํ™”๊ฐ€ ๋‚˜์ง€๋งŒ, ๋Œ€ํ•™ ๋Œ€ํ•ญ์ „์ธ ICPC์—์„œ ์„œ์šธ๋Œ€ 15ํŒ€์ด ๋‚˜ํƒ€๋‚˜๋Š” ๊ฒƒ์ด ๊ทธ๋Ÿผ ๋งž๋Š๋ƒ? ๊ณ  ๋งํ•˜๋ฉด ๋ญ ๊ทธ๋ ‡๊ฒŒ ๋ณผ ์ˆ˜๋„ ์žˆ์Šต๋‹ˆ๋‹ค. ๋‹ค๋งŒ, ์ด ๋ถ€๋ถ„์€ ์กฐ๊ธˆ ๋‚˜์•„์งˆ ๊ธฐ๋ฏธ๊ฐ€ ๋ณด์ด๋Š”๋ฐ, PSํŒ์—์„œ ์„œ์šธ๋Œ€๊ฐ€ ๋ณด์—ฌ์คฌ๋˜ ๊ฐญ์ด ์ ์  ์ค„์–ด๋“œ๋Š”๊ฒŒ ๋ˆˆ์— ๋ณด์ด๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค. ์˜ฌํ•ด์˜ ์ธ์˜ˆ ์ˆœ์œ„์—์„œ ์†”๋ธŒ์ˆ˜๋กœ ๊ฒฉ์ฐจ๋ฅผ ๋‚ธ ์ตœ์ƒ์œ„๊ถŒ์€ ์„œ์šธ-์„œ์šธ-๊ณ ๋ ค-์นด์ด-์นด์ด-์œ ๋‹ˆ ์ž…๋‹ˆ๋‹ค. (7์†”์— ์ €ํฌ๋ฅผ ํฌํ•จ ๋ฌด๋ ค 12ํŒ€์ด ๋ฌผ๋ ค ์žˆ์Šต๋‹ˆ๋‹ค) ์ฐธ๊ณ ๋กœ, ์ž‘๋…„ ์ธ์˜ˆ๋Š” 9์†” ์ด์ƒ์ด 7ํŒ€์ด์—ˆ๋Š”๋ฐ, ์„œ์šธ-์„œ์šธ-์„œ์šธ-์„œ์šธ-์นด์ด-์„œ์šธ-์ˆญ์‹ค ์ด์—ˆ์Šต๋‹ˆ๋‹ค. PSํŒ์˜ ์ €๋ณ€์ด ๋„“์–ด์ ธ์„œ ๊ทธ๋Ÿฐ ๊ฒƒ์ธ์ง€, ์„œ์šธ๋Œ€์˜ ์ˆ˜๋งŽ์€ ๋ ˆ๋“œ๋“ค์ด PSํŒ์„ ๋– ๋‚˜๊ณ  ML ๊ฐ™์€ ๋ณด๋‹ค ์“ธ๋ชจ์žˆ๋Š” ๋ญ”๊ฐ€๋ฅผ ๊ณต๋ถ€ํ•˜๋Ÿฌ ๊ฐ”๊ธฐ ๋•Œ๋ฌธ์ธ์ง€, ์ตœ๊ทผ ์—ฌ๋Ÿฌ ํ•™๊ต์—์„œ ๋ ˆ๋“œ ์ด์ƒ์˜ CP-er๋ฅผ ๋ฐฐ์ถœํ•œ ๋ฐ ์–ด๋–ค ์š”์†Œ๋“ค์ด ์ž‘์šฉํ–ˆ๋Š”์ง€๋Š” ์ž˜ ๋ชจ๋ฅด๊ฒ ์ง€๋งŒ ์•„๋ฌดํŠผ ๊ทธ๋ ‡์Šต๋‹ˆ๋‹ค. ๋ ˆ๋“œ ํ•œ๋ช…์ด ์กธ์—…ํ• ๋•Œ๊นŒ์ง€ ๋›ธ์ˆ˜์žˆ๋Š” ICPCํŒ์„ ๋ณด๋‹ˆ ๋‚ด๋…„์—๋„ ์ด๋Ÿด ๊ฒƒ ๊ฐ™๊ณ , ์ž‘๋…„์ฒ˜๋Ÿผ ์„œ์šธ๋Œ€ ๋ฆฌ์ €๋„ 6ํŒ€์ธ๊ฐ€? ๋ณด๋‚ด ์คฌ๋”๋‹ˆ ๋ชจ๋“  ์ƒ์„ ์„œ์šธ๋Œ€๊ฐ€ ์“ธ์–ด๋ฒ„๋ฆฌ๋Š” ์ฐธ์‚ฌ๊ฐ€ ๋ฒŒ์–ด์ง€์ง€๋Š” ์•Š์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค.

์ €๋Š” ๋‚ด๋…„์ด ๋งˆ์ง€๋ง‰ ICPC๊ณ , ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ณต๋ถ€ํ•˜๋ฉด์„œ / PS๋ฅผ ์ฆ๊ธฐ๋ฉด์„œ ICPC ๋ณธ์„  ๋ฆฌ์ €๋„ ๋ฌด๋Œ€๋ฅผ ํ•œ๋ฒˆ๋„ ๊ฐ€๋ณด์ง€ ๋ชปํ–ˆ๋‹ค๋Š” ๊ฒƒ์ด ๊ฐœ์ธ์ ์œผ๋กœ ๊ต‰์žฅํžˆ ์•„์‰ฝ์Šต๋‹ˆ๋‹ค. ์–ด๋–ป๊ฒŒ ๋ณด๋ฉด ์•„์นด๋ฐ๋ฏนํ•˜๊ฒŒ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ณต๋ถ€ํ•˜๊ฒ ๋‹ค๋Š” ๋ชฉํ‘œ๋ฅผ ๊ฐ–๊ฒŒ ๋œ ์ง€๊ธˆ์€ PS ์ž์ฒด์— ํฐ ์˜๋ฏธ๋Š” ์—†๊ฒ ์ง€๋งŒ, ๊ฐœ์ธ์ ์œผ๋กœ ๋Š๋‚€ ๋ฐ”๊ฐ€ ๊ทธ๋ ‡์Šต๋‹ˆ๋‹ค. ๊ทธ๋ž˜์„œ, ๊ฒจ์šธ๋ฐฉํ•™์— ์ข€ ๋นก์„ธ๊ฒŒ ๋Œ๋ฉด์„œ ๋ ˆ๋“œ ์ •๋„ ์ˆ˜์ค€๊นŒ์ง€ ํผ์„ ๋งž์ถฐ๋†“๊ณ , ๋‚ด๋…„์—๋Š” ๋ ˆ๋“œ 3๋ช… ๋˜๋Š” ๊ทธ์— ๊ทผ์ ‘ํ•œ, ์ง„์ถœ์„ ๋…ธ๋ฆฌ๋Š” ํŒ€์„ ๋งŒ๋“ค์–ด ๋งˆ์ง€๋ง‰ ICPC์— ๋„์ „ํ•  ๊ณ„ํš์ž…๋‹ˆ๋‹ค. ์ข‹์€ ํŒ€์›์„ ๋ชจ์€๋‹ค๋ฉด 80% ์ด์ƒ ๊ฐ€๋Šฅํ•˜๋‹ค๊ณ  ํ™•์‹ ํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ํ˜น์‹œ ์ด ๋ธ”๋กœ๊ทธ๋ฅผ ๋ณด์‹  ์„œ์šธ๋Œ€ ์žฌํ•™์ƒ ์ค‘, ๋‚ด๋…„ 10์›”๊นŒ์ง€ CF 2300 ๋˜๋Š” Equivalentํ•œ ์‹ค๋ ฅ์„ ๊ฐ–์ถœ ์ˆ˜ ์žˆ์œผ๋ฉฐ, ํœดํ•™ ๊ณ„ํš์ด ์—†๊ณ , ๊ฐ™์ด ๊ณต๋ถ€ํ•˜๊ณ  ์‹ถ์€ ๋ถ„์€ ์—ฐ๋ฝ์ฃผ์‹œ๋ฉด ์ข‹์„๊ฒƒ ๊ฐ™๋„ค์š”. ใ…‹ใ…‹!!! (๋‹น์—ฐํ•œ ๋ง์ด์ง€๋งŒ ์ด๋Ÿฐ ํ—ˆ๊ณต์— ๋Œ๋˜์ง€๋Š” ์‹์œผ๋กœ ๋ชจ์„ ์ƒ๊ฐ์œผ๋กœ ์“ด ๋ง์€ ์•„๋‹™๋‹ˆ๋‹คโ€ฆ)

๋Œ€ํšŒ๋ฅผ ๋งˆ์น˜๋ฉฐ

ํ•ญ์ƒ PS ๋Œ€ํšŒ๋ฅผ ๋›ฐ๊ณ  ๋‚˜๋ฉด, PS๋ฅผ ์ฆ๊ธฐ๋Š” ๋งˆ์ธ๋“œ์™€ ๋Œ€ํšŒ ์„ฑ์ ์— ๋”ฐ๋ฅธ competitive ํ•œ ๋งˆ์ธ๋“œ๊ฐ€ ์„œ๋กœ ์ถฉ๋Œํ•˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ์ด๋ฒˆ ๋Œ€ํšŒ๋Š” ์ •๋ง ๊ฐ„๋งŒ์— ๊ทธ๋Ÿฐ ๊ฒƒ ์—†์ด ์ˆœ์ˆ˜ํ•˜๊ฒŒ ์ฆ๊ธธ ์ˆ˜ ์žˆ์—ˆ๋Š”๋ฐ, ๋Œ€ํšŒ๊ฐ€ ๋๋‚˜๊ณ  ๋‚˜๋‹ˆ competitive mind๊ฐ€ ์ž ๊น ์ง€๋ฐฐํ•˜๊ณ  ์žˆ์–ด์„œ ์œ„ 500๋‹จ์–ด ์ •๋„๋ฅผ rantingํ–ˆ์Šต๋‹ˆ๋‹ค. ํ•™๊ธฐ์ค‘์—๋Š” ์–ด์ฐจํ”ผ ๋งค์šฐ ๋ฐ”์˜๊ธฐ ๋•Œ๋ฌธ์—, ๊ฒจ์šธ๋ฐฉํ•™์—๋‚˜ ๋‹ค์‹œ ์†๋Œˆ ์ˆ˜ ์žˆ์ง€ ์•Š์„๊นŒ ์‹ถ์Šต๋‹ˆ๋‹ค.

๋๋‚˜๊ณ  ํŒ€์›๋“ค๊ณผ ์น˜ํ‚จ์„ ๋จน์œผ๋ฉด์„œ ๋Œ€ํšŒ์— ๋Œ€ํ•œ ์–˜๊ธฐ๋„ ํ•˜๊ณ , ์žฌ๋ฐŒ๊ฒŒ ๋†€๊ณ  ์™”์Šต๋‹ˆ๋‹ค.


  1. ๋„ค. ์ด ๋ฌธ์žฅ์€ ๊ธฐ๋งŒ์งˆ ์ž๋ž‘ํ•˜๋ ค๊ณ  ์ ์—ˆ์Šต๋‹ˆ๋‹ค. ใ…‹ใ…‹!!!ย โ†ฉ