Back to : cp-rounds
Contents

  • ๋ณธ๋ฌธ์—์„œ ์–ธ๊ธ‰๋˜๋Š” ๋‚œ์ด๋„ ํ‹ฐ์–ด (๋ธŒ/์‹ค/๊ณจ/ํ”Œ/๋‹ค/๋ฃจ) ๋Š” Solved.ac ๊ธฐ์ค€์ž…๋‹ˆ๋‹ค.

  • ํŒ€์— ๊ด€ํ•ด์„œ๋Š” ์˜ˆ์„ ํ›„๊ธฐ ์—๋„ ์ ์–ด๋‘์—ˆ์Šต๋‹ˆ๋‹ค :)

ํŒ€์—ฐ์Šต

UCPC ๋ณธ์„ ์€ ICPC์™€ ๋˜‘๊ฐ™์€ 5์‹œ๊ฐ„ 3์ธ 1PC ๋Œ€ํšŒ์ž…๋‹ˆ๋‹ค. ๊ณ ๋ ค๋Œ€ Hongjun7๋‹˜ ๋“ฑ ํŒ€๋Œ€ํšŒ๋ฅผ ์ฆ๊ธฐ๋ฉด์„œ ์ž˜ํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” ์ด ๋Œ€ํšŒ ํ”„๋ ˆ์ž„์— ๋งž๋Š” ์ค€๋น„๊ฐ€ ํ•„์š”ํ•ฉ๋‹ˆ๋‹ค. 3์‹œ๊ฐ„ 3PC ๋Œ€ํšŒ์— ๋น„ํ•ด, 5์‹œ๊ฐ„ 1PC ๋Œ€ํšŒ๋Š” ํฌ๊ฒŒ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ˆˆ์— ๋„๋Š” ์ฐจ์ด๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค

  • ์ค‘์œ„๊ถŒ ์ด์ƒ์˜ ํŒ€ ๋Œ€๋ถ€๋ถ„์€ ๊ตฌํ˜„์ด bottleneck์ž…๋‹ˆ๋‹ค.
  • PC ์•ž์— ํ•ญ์ƒ 1๋ช…์ด ์•‰์•„์žˆ๋‹ค๋Š” ๋ง์€, ๋ฐ˜๋Œ€๋กœ 2๋ช…์ด ํ•ญ์ƒ ์ปดํ“จํ„ฐ์—์„œ ์†์„ ๋–ผ๊ณ  ์žˆ๋‹ค๋Š” ์˜๋ฏธ๊ฐ€ ๋ฉ๋‹ˆ๋‹ค. ์ฆ‰, ํ‘ธ๋Š” ์‚ฌ๋žŒ์€ 2๋ช…์ด๊ธฐ ๋•Œ๋ฌธ์— ๋ฌธ์ œ๋ฅผ ๋™์‹œ์— 2๊ฐœ tackleํ•˜๊ฑฐ๋‚˜, ๋‘˜์ด ๋…ผ์˜๋ฅผ ํ†ตํ•ด ์†”๋ฃจ์…˜์„ ๊ตฌ์ƒํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค
  • ๊ฐ€์žฅ ์œ„ํ—˜ํ•œ ๊ฒƒ์€ ์•„ ๋งž๋Š”์ค„ ์•Œ์•˜๋Š”๋ฐ ์งœ๋‹ค๋ณด๋‹ˆ๊นŒ ์•„๋‹ˆ๋‹ค ์ž…๋‹ˆ๋‹ค. 3PC ๋Œ€ํšŒ์—์„œ 30๋ถ„๋™์•ˆ ๋ง๋ฆฌ๋Š” ๊ฒƒ์€ ํŒ€์˜ ์‹œ๊ฐ„์„ 30๋ถ„ ์†Œ๋ชจํ•œ ๊ฒƒ์ด์ง€๋งŒ, 1PC ๋Œ€ํšŒ๋Š” โ€œPC-์‹œ๊ฐ„โ€ ์ด 3๋ฐฐ ๊ท€ํ•œ ์ž์›์ด๊ธฐ ๋•Œ๋ฌธ์— ์ปดํ“จํ„ฐ ์•ž์—์„œ ๋‚ ๋ฆฐ 20๋ถ„์€ ์ปดํ“จํ„ฐ ๋ฐ–์—์„œ ๋‚ ๋ฆฐ ์ตœ์†Œ 40๋ถ„~1์‹œ๊ฐ„ ๊ฐ€๋Ÿ‰์˜ ๊ฐ€์น˜๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค.

๊ทธ๋ž˜์„œ ๋Œ€ํšŒ์˜ ํฌ๋งท์— ๋งž๊ฒŒ 2๋ฒˆ์˜ ํŒ€์—ฐ์Šต์„ ๋” ํ–ˆ์Šต๋‹ˆ๋‹ค.

  • 2021 ์„œ์šธ ๋ฆฌ์ €๋„ ํŒ€์—ฐ์Šต : ์ž‘๋…„ ICPC์˜ ๋ฌธ์ œ๋ฅผ ์•„๋ฌด๋„ ๋ณธ์ ์ด ์—†๋‹ค๋Š”๊ฒŒ ์ด๋ฏธ ์ €ํฌ๊ฐ€ ์–ผ๋งˆ๋‚˜ PS๋ฅผ ๋– ๋‚˜์žˆ์—ˆ๋Š”์ง€ ๋ณด์—ฌ์ฃผ๋Š”๊ฒŒ ์•„๋‹๊นŒ์š”? K๋ฒˆ์„ ์‹œ๊ฐ„๋‚ด์— ๊ตฌํ˜„ํ•ด๋‚ด์ง€ ๋ชปํ–ˆ๋‹ค๋Š” ์  ์™ธ์—๋Š” ๊ฒฐ๊ณผ ์ž์ฒด๋Š” ํฌ๊ฒŒ ๋ฌธ์ œ๋Š” ์—†์—ˆ์ง€๋งŒ, Stet-stet๊ณผ ์ œ๊ฐ€ ํ•œ๋ฌธ์ œ์”ฉ ์žก๊ณ  ๊ฐ๊ฐ ์ผ€์ด์Šค์ •๋ฆฌ์™€ ๊ตฌํ˜„์ด์Šˆ๋กœ ํ•„์š” ์ด์ƒ์œผ๋กœ ๊ณ ํ†ต๋ฐ›์œผ๋ฉฐ PC-์‹œ๊ฐ„์„ ์†Œ๋ชจํ–ˆ์Šต๋‹ˆ๋‹ค.
  • 2020 ์ž์นด๋ฅดํƒ€ ๋ฆฌ์ €๋„ ํŒ€์—ฐ์Šต : ๋””๋‹‰ ์ฝ”๋“œ๋ฅผ ๋‹ค ์งœ๋†“๊ณ  ์–ด์ด์—†๋Š” DFS ๊ตฌํ˜„์‹ค์ˆ˜๋ฅผ ํ•ด์„œ (โ€ฆ) ์ œ๊ฐ€ PC-์‹œ๊ฐ„์„ ํ˜ผ์ž 1์‹œ๊ฐ„ ๊ฐ€๊นŒ์ด ๋‚ ๋ฆฐ ์ค‘์ฃ„๋ฅผ ์ €์งˆ๋ €์Šต๋‹ˆ๋‹ค. ์ „๋ฐ˜์ ์œผ๋กœ ๋งŽ์ด ๋ง๋ ธ๋˜๋“ฏ ํ•ฉ๋‹ˆ๋‹ค.

์„ธ๋ช… ๋ชจ๋‘ ๊ตฌํ˜„์ด ๋”ฑํžˆ ๊ฐ•ํ•œ๊ฒƒ์€ ์•„๋‹ˆ๋ผ๋Š” ์ ์„ ์žฌํ™•์ธํ–ˆ์Šต๋‹ˆ๋‹ค. ๋ฌ˜ํ•˜๊ฒŒ ์ปจ์…‰์ด ๊ฒน์น˜๋Š” ์ €ํฌ ํŒ€์€ ์•„๋งˆ๋„ ์—ฌ๊ฑด์ด ๊ฐ–์ถ”์–ด์ง€๋ฉด ๋‹ค์ด์•„ ์ˆ˜ํ•™/DP ๋ฌธ์ œ๋ฅผ ๊ฒฉ์ถ”ํ•  ์ˆ˜ ์žˆ๋Š” ๋Œ€์‹  (ํŠนํžˆ ์„ธ๋ช…์ด ์ˆ˜ํ•™์„ ์ข€ ์ข‹์•„ํ•˜๋Š” ๊ตฌ์„ฑ์ด๊ณ , DHDroid์™€ Stet-stet์€ DP/Construction์— ๊ต‰์žฅํžˆ ๊ฐ•ํ•ฉ๋‹ˆ๋‹ค. ์ €๋Š” ์ƒ๋Œ€์ ์œผ๋กœ ์ •์ˆ˜๋ก  ๋ฅ˜ ๋ฌธ์ œ๋ฅผ ์ข‹์•„ํ•˜๊ณ โ€ฆ) UCPC 2019 ํƒ์‹œ ๊ฐ™์€ ๋ฌธ์ œ๊ฐ€ ๋‚˜์˜จ๋‹ค๋ฉด ๊ทธ๋Œ€๋กœ ๋งํ• ์ˆ˜๋„ ์žˆ๊ฒ ๋‹ค๋Š” ์ƒ๊ฐ์ด ๋“ค์—ˆ์Šต๋‹ˆ๋‹ค.

๋ณธ ๋Œ€ํšŒ

3๋…„๋งŒ์˜ ์˜คํ”„๋ผ์ธ ๋Œ€ํšŒ๋ผ์„œ ์„ค๋ ˆ๋Š” ๋งˆ์Œ์œผ๋กœ(?) ์ฐพ์•„๊ฐ„ ๋Œ€ํšŒ์žฅ์€ ์ฝ”์—‘์Šค ๊ทผ์ฒ˜๋ผ์„œ, ์ €๋Š” ๊ต‰์žฅํžˆ ๊ฐ€๊นŒ์› ์Šต๋‹ˆ๋‹ค.

2019๋…„ UCPC๋Š” ๊ณ ๋ ค๋Œ€์˜€๊ณ  ๊ต‰์žฅํžˆ ํ™˜๊ฒฝ์ด ์ข‹์•˜๋Š”๋ฐ, ์ด๋ฒˆ์—๋Š” ๋‹ค์†Œ ํ˜‘์†Œํ•œ ๊ฐ์ด ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค. ํ•™๊ต ๋Œ€๊ด€์ด ์•ˆ๋˜๋ฉด ์‚ฌ์‹ค ์–ด์ฉ”์ˆ˜ ์—†์—ˆ๊ฒ ์ง€๋งŒโ€ฆ

Competitive Programming์˜ ์ƒ์ง•๊ฐ™์€ ๋ฌธ์ œ๋ณ„ ํ’์„ ์„ ๋ณด๋‹ˆ ๋ฌ˜ํ•˜๊ฒŒ ๋“ค๋–ด๋˜ ๊ธฐ์–ต์ด ์žˆ์Šต๋‹ˆ๋‹ค. ใ…‹ใ…‹

Phase 1 : WTF?

์ดˆ๋ฐ˜์ „๋žต์€ ABCD(Gratus)/EFGH(Stet-stet)/IJKL(DHDroid) ๋กœ ๋‚˜๋ˆ  ์ฝ๊ณ , ์‰ฌ์šด๊ฑธ ๋จผ์ € ์ฐพ์€๋‹ค์Œ scoreboard-drivenํ•˜๊ธฐ๋กœ ํ–ˆ์Šต๋‹ˆ๋‹ค. ์ด ๊ณผ์ •์—์„œ ์ค‘์š”ํ•œ๊ฑด ๋ชจ๋“  ๋ฌธ์ œ๋ฅผ ์ฝ๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.

์—ฐ์Šตํ–ˆ๋˜ ๋Œ€๋กœ ๋ฌธ์ œ๋ฅผ ๋‚˜๋ˆ„์–ด ์ฝ์—ˆ์Šต๋‹ˆ๋‹ค. ์ €๋Š” ABCD๋ฅผ ์žก์•˜๊ณ , ๋ณดํ†ต ์•ž์— ์‰ฌ์šด๊ฒŒ ํ•˜๋‚˜ ์„ž์—ฌ์žˆ๊ณ  ์ œ๊ฐ€ ์ œ์ผ ์ฝ”๋”ฉ์ด ๋นจ๋ผ์„œ ์ด๋ ‡๊ฒŒ ํ•˜๋Š”๋ฐ ์‚ฌ์‹ค UCPC๋ณธ์„ ๊ฐ™์€ ํ”Œ๋ ˆ ์ด์ƒ ๋ฌธ์ œ๋กœ ๋นก๋นกํ•˜๊ฒŒ ์ฑ„์›Œ์ง„ ๋Œ€ํšŒ์—์„œ๋Š” ํฐ ์˜๋ฏธ๋Š” ์—†์Šต๋‹ˆ๋‹ค.

  • A : ๋ญ”๊ฐ€ ํ•˜๋‚˜์”ฉ ์ฑ„์›Œ๋‚˜๊ฐ€๋ฉด์„œ ์ž‘์€ ๋ฌธ์ œ๊ฐ€ ๋˜๋Š”๊ฒŒ DP๊ฐ™์€ ๋Š๋‚Œ. DHDroid์—๊ฒŒ ๋„˜๊ฒจ์•ผ ํ•˜๋‚˜? ๋ฅผ ์ƒ๊ฐํ•˜๊ณ  ์ผ๋‹จ ์ œ๊ผˆ์Šต๋‹ˆ๋‹ค.
  • B : Backus-Naur Form, ์ปดํŒŒ์ผ๋Ÿฌ๊ฐ™์€๊ฒŒ ๋‚˜์˜ค๋Š”๊ฑธ ๋ณด๊ณ  ์ฆ‰์‹œ ๋ฒ„๋ฆฌ๊ธฐ๋กœ ํ–ˆ์Šต๋‹ˆ๋‹ค.
  • C : ๋น„๊ต์  ํ• ๋งŒ ํ•ด ๋ณด์˜€์Šต๋‹ˆ๋‹ค. ์ข€ ์ƒ๊ฐํ•ด ๋ณด๊ธฐ๋กœ ํ•˜๊ณ โ€ฆ
  • D : ์ „ํ˜•์ ์ธ ์ˆ˜์—ด๊ณผ ์ฟผ๋ฆฌ ๋ฌธ์ œ์—๋‹ค๊ฐ€, ๋ญ”๊ฐ€ ํ•ฉ์˜ ํ•ฉ์˜ ํ•ฉ์˜ ํ•ฉ์„ ํ•ด์•ผํ• ๊ฑฐ๊ฐ™์€ ๋Š๋‚Œ์— ์ผ๋‹จ C๋ณด๋‹ค๋Š” ์–ด๋ ค์›Œ ๋ณด์˜€์Šต๋‹ˆ๋‹ค.

์ €๋Š” ์—ฌ๊ธฐ๊นŒ์ง€ ์ฝ๊ณ , C๋ฅผ ์ƒ๊ฐํ•˜๋ฉด์„œ ์‰ฌ์šด ๋ฌธ์ œ๋ฅผ ๋’ค์—์„œ identify ํ•ด์ฃผ๊ธธ ๊ธฐ๋‹ค๋ ธ์Šต๋‹ˆ๋‹ค. ๋’ค ๋ฌธ์ œ๋ฅผ ์ฝ์€ ๋‘์‚ฌ๋žŒ๋„ ๊ณ ํ†ต๋ฐ›๊ณ  ์žˆ๋Š”๊ฑฐ ๊ฐ™์•˜๋Š”๋ฐ, ์—ฌ๊ธฐ๊นŒ์ง„ ๋‚˜๋ฆ„ PSํ•˜๋Š” ์„ค๋ ˜์— ๊ธฐ๋ถ„ ์ข‹์•˜๋˜ ๊ธฐ์–ต์ด ์žˆ์Šต๋‹ˆ๋‹ค.

๋’ค์—์„œ J๋ฒˆ์ด ๋น„๊ต์  ์‰ฌ์šด ๋ฌธ์ œ์ž„์„ ํŒŒ์•…ํ•ด์™”๊ณ , ๋ฐ”๋กœ ํ’€์–ด์„œ ๋งž์•˜์Šต๋‹ˆ๋‹ค.

J - ๊ต์ง‘ํ•ฉ ๋งŒ๋“ค๊ธฐ

๋‚œ์ด๋„ : S1             AC Time : 00:20
solve : DHDroid
code : Gratus907

1๊ฐœ ๊ตฌ๊ฐ„์œผ๋กœ ๊ฐ€๋Šฅํ•œ ๊ฒฝ์šฐ, 2๊ฐœ ๊ตฌ๊ฐ„์œผ๋กœ ๊ฐ€๋Šฅํ•œ ๊ฒฝ์šฐ, ๋ถˆ๊ฐ€๋Šฅํ•œ ๊ฒฝ์šฐ๊ฐ€ ์žˆ์Œ์„ ํŒŒ์•…ํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค. 1๊ฐœ๋Š” ์ž๋ช…ํ•˜๋ฏ€๋กœ ๋ถˆ๊ฐ€๋Šฅ๊ณผ 2๊ฐœ๋ฅผ ๊ตฌ๋ถ„ํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.

๋งŒ์•ฝ 3๊ฐœ ์ด์ƒ์˜ ๊ตฌ๊ฐ„์˜ ๊ต์ง‘ํ•ฉ์ด $[l, r]$ ์ด๋ผ๋ฉด, ์ด๋“ค ์ค‘ $l$์—์„œ ์‹œ์ž‘ํ•ด์„œ $r$๋ณด๋‹ค ์˜ค๋ฅธ์ชฝ๊นŒ์ง€๋ฅผ ์ปค๋ฒ„ํ•˜๋Š” ๊ตฌ๊ฐ„์ด ์žˆ๊ณ , $r$์—์„œ ๋๋‚˜๋ฉด์„œ $l$๋ณด๋‹ค ์™ผ์ชฝ์—์„œ ์ถœ๋ฐœํ•˜๋Š” ๊ตฌ๊ฐ„์ด ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ๋‘๊ฐœ๋ฅผ ํƒํ•˜๋ฉด 2๊ฐœ๋กœ ์ค„์ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์—ญ์œผ๋กœ, 2๊ฐœ์˜ ๊ตฌ๊ฐ„์„ ์ด์šฉํ•ด์„œ $[l, r]$์„ ์ปค๋ฒ„ํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” $l$์—์„œ ์ถœ๋ฐœํ•ด์„œ ๊ฐ€์žฅ ๋ฉ€๋ฆฌ๊นŒ์ง€ ๋‹ฟ๋Š” ๊ตฌ๊ฐ„๊ณผ, $r$์—์„œ ๋๋‚˜๋ฉด์„œ ๊ฐ€์žฅ ์™ผ์ชฝ์—์„œ ์ถœ๋ฐœํ•˜๋Š” ๊ตฌ๊ฐ„์„ ์ด์šฉํ•ด์„œ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋ฉด ์ถฉ๋ถ„ํ•ฉ๋‹ˆ๋‹ค.

์•„๋งˆ DHDroid๊ฐ€ ๋ฌธ์ œ๋ž‘ ๊ฑฐ์˜ ๊ฐ™์ด ํ’€์ด๋ฅผ ์ „๋‹ฌํ–ˆ๋˜๊ฑฐ ๊ฐ™์€๋ฐ ์ •ํ™•ํžˆ๋Š” ๊ธฐ์–ต์ด ์•ˆ๋‚˜๋„ค์š”.

H - ํŠน๋ณ„์ƒ

๋‚œ์ด๋„ : S1             AC Time : 00:28
solve : Stet-stet
code : Gratus907

๋งˆ์ฐฌ๊ฐ€์ง€๋กœ Stet-stet์ด ๋ฌธ์ œ์™€ ๋‹ต์„ ๋™์‹œ์— ์ „๋‹ฌํ–ˆ์Šต๋‹ˆ๋‹ค.

์‹ฌํŒ์˜ ์ ์ˆ˜๊ฐ€ ๋†’์€ $K$๋ช…์€ ์–ด์ฐจํ”ผ ๋ฌด์Šจ ์ƒ์ด๋“  ๋ฐ›์„์ˆ˜๋ฐ–์— ์—†์œผ๋ฏ€๋กœ, ๊ทธ๊ฑธ ๋จผ์ € ๊ทธ๋ƒฅ ์‹ฌํŒ์ƒ์„ ์ค˜๋ฒ„๋ฆฌ๊ณ  ๋‚จ์€์‚ฌ๋žŒ์ค‘ ์ฃผ์ตœ์ž ์ ์ˆ˜๊ฐ€ ๋†’์€ ์‚ฌ๋žŒ $M$๋ช…ํ•œํ…Œ ์ฃผ์ตœ์ƒ์„ ์ฃผ๋ฉด ์ฃผ์ตœ์ž ์ž…์žฅ์—์„œ ์ตœ์„ ์˜ ๊ฒฐ๊ณผ๋ฅผ ์–ป์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ •๋ ฌ ๋‘๋ฒˆํ•˜๋Š” ๊ทธ๋ฆฌ๋”” ๋ฌธ์ œ.

L - ์ปค๋„ฅํ‹ฐ๋“œ ์นด ์‹คํ—˜

๋‚œ์ด๋„ : G4             AC Time : 00:48
solve : DHDroid, Gratus907
code : Gratus907

์ œ๊ฐ€ ์ฒ˜์Œ์— ์‹œ์ž‘์ ์—์„œ ์–‘์ชฝ์œผ๋กœ ๋๊นŒ์ง€ ๊ฐ€๋ณด๋Š” ๊ฐ„๋‹จํ•œ ๊ทธ๋ฆฌ๋””๋กœ ๋œ๋‹ค๊ณ  ์ƒ๊ฐํ•˜๊ณ  Stet-stet๊ณผ ์ž ๊น ์–˜๊ธฐํ–ˆ์ง€๋งŒ, ๋‘˜๋‹ค ๊ฐ™์€ ์ฐฉ๊ฐ์„ ํ•ด์„œ ์‹ค์ˆ˜๋ฅผ ์ฐพ์ง€ ๋ชปํ–ˆ์Šต๋‹ˆ๋‹ค. ๊ตฌํ˜„ํ•ด์„œ ํ•œ๋ฒˆ ํ‹€๋ฆฌ๊ณ  DHDroid๊ฐ€ ์ฐพ์•„์คฌ์Šต๋‹ˆ๋‹ค :fan:

๋งค ์‹œ์ ์—, โ€œ์ง€๊ธˆ ๋จน์€ ์ฐจ๋ณด๋‹ค ํ•˜๋‚˜ ์™ผ์ชฝ/์˜ค๋ฅธ์ชฝ์˜ ์ฐจ๋ฅผ ๋จน์„ ์ˆ˜ ์žˆ๋Š”์ง€โ€ ๋ฅผ ํˆฌํฌ์ธํ„ฐ์ฒ˜๋Ÿผ ํŒ๋‹จํ•ฉ๋‹ˆ๋‹ค. ํˆฌํฌ์ธํ„ฐ ๊ตฌํ˜„์€ ๋ณ„๋กœ ์–ด๋ ต์ง€ ์•Š๊ณ , โ€œ์ตœ๋Œ€ํ•œ ๋งŽ์€ ์—ฐ๋ฃŒ๋ฅผ ๋‚จ๊ธฐ๋ฉดโ€ ์ตœ๋Œ€ํ•œ ๋ฉ€๋ฆฌ ๊ฐˆ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ ๋งค ์‹œ์ ์—๋Š” ๊ทธ๋ฆฌ๋””ํ•˜๊ฒŒ ์„ ํƒ์ด ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.

Phase 2 : TLE (K - ์ „๋Œ€ํ”„์—ฐ ํ† ๋„ˆ๋จผํŠธ)

์—ฌ๊ธฐ๊นŒ์ง€ ๋Œ€ํšŒ๊ฐ€ ์ƒ๋‹นํžˆ ์ž˜ ๊ตด๋Ÿฌ์™”์Šต๋‹ˆ๋‹ค. ๊ฒฐ์ •์ ์œผ๋กœ, ์ œ๊ฐ€ L์„ ๊ตฌํ˜„ํ•˜๋Š” ๋™์•ˆ K๋ฅผ DHDroid์™€ Stet-stet์ด ๊ฑฐ์˜ ๋‹ค ํ’€์—ˆ์—ˆ๊ณ  ๊ฑฐ์˜ ๋ฐ”๋กœ ๊ตฌํ˜„์— ๋“ค์–ด๊ฐˆ ์ˆ˜ ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค.

์ด K๊ฐ€ ์–ด๋–ค ๋”์ฐํ•œ ๊ฒฐ๊ณผ๋ฅผ ๊ฐ€์ ธ์˜ฌ์ง€๋Š” ์ƒ๊ฐ์ง€ ๋ชปํ–ˆ์Šต๋‹ˆ๋‹ค. :rage:

๋‚œ์ด๋„ : P2             AC Time : 02:15 (+8)
solve : DHDroid, Stet-Stet
code : DHDroid

๋ฌธ์ œ๋ฅผ ์š”์•ฝํ•˜์ž๋ฉด, ํ† ๋„ˆ๋จผํŠธ์—์„œ 1๊ฐœ์˜ ๊ฒฝ๊ธฐ ๊ฒฐ๊ณผ๊ฐ€ ์œ ์‹ค๋˜์—ˆ์„ ๋•Œ ๊ทธ ์œ ์‹ค๋œ ๊ฒฐ๊ณผ๋ฅผ ๋ณต์›ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

์ €๋Š” ํ’€์ด๋ฅผ ๊ฐ„๋‹จํžˆ๋งŒ ๋“ค์—ˆ๋Š”๋ฐ, ์ผ์ข…์˜ ์žฌ๊ท€์ ์ธ ์…‹์—…์„ ํ†ตํ•ด ๋งค๋ฒˆ ๊นŠ์ด๋ฅผ 1์”ฉ ์ค„์ธ ํ† ๋„ˆ๋จผํŠธ๋ฅผ ๊ตฌ์ถ•ํ•  ์ˆ˜ ์žˆ์œผ๋ฉฐ ๊ตฌํ˜„์ด ๊ท€์ฐฎ์ง€๋งŒ ๊ทธ๋ ‡๊ฒŒ๊นŒ์ง€ ์–ด๋ ต์ง€๋Š” ์•Š๋‹ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๊ณต์‹ ํ’€์ด์— ๋‚˜์˜จ ๋‘๋ฒˆ์งธ ๋ฐฉ๋ฒ• (์ถœ์ œ์ž์˜ ํ’€์ด) ์™€ ๋น„์Šทํ•˜๋‹ค๊ณ  ๋“ค์—ˆ์Šต๋‹ˆ๋‹ค.

L์„ ํ’€๊ณ  ๋‚˜์„œ, ์ƒˆ๋กœ ํ’€ ๋ฌธ์ œ๋ฅผ ์ฐพ๋˜ ์ค‘ DHDroid๊ฐ€ ๋ฌด์Šจ ์žฌ๊ท€์ ์œผ๋กœ ํ’€๋ฉด... ๊ฐ™์€ ๋ง์„ ํ•˜๊ธธ๋ž˜ ๋ฐ”๋กœ ๋„˜๊ฒผ์Šต๋‹ˆ๋‹ค. DHDroid๊ฐ€ ํ‰์†Œ constructiveํ•œ ๋ฌธ์ œ์— ๋น„์ƒํ•œ ์‹ค๋ ฅ์„ ๋ณด์—ฌ์ฃผ๋ฏ€๋กœ ๋ณ„ ์–ด๋ ค์›€ ์—†์ด ๋งž์•„์˜ค๊ฒ ์ง€ ํ•˜๊ณ  ์ €๋Š” M, F, C, D ๋“ฑ๋“ฑ์„ Stet-stet๊ณผ ์ž ๊น์”ฉ ํƒ๋ฐฉํ•˜๋ฉฐ ๋‹ค์Œ ํ’€ ๋ฌธ์ œ๋ฅผ ์ฐพ์œผ๋Ÿฌ ๊ฐ”์Šต๋‹ˆ๋‹ค.

์ดํ›„๋กœ WA์™€ TLE๋ฅผ ํ•ฉ์ณ ๋ฌด๋ ค 8๋ฒˆ์˜ ํŽ˜๋„ํ‹ฐ๋ฅผ ๋ฐ›์•˜๊ณ , ๊ทธ์ค‘์—์„œ๋„ โ€œ์ฝ”๋“œ๊ฐ€ ํ‹€๋ฆฐ๊ฑฐ๊ฐ™์ง€๋Š” ์•Š์€๋ฐ ์™œ TLE์ธ์ง€ ๋ชจ๋ฅด๊ฒ ๋‹ค. ๋ณต์žก๋„์—๋Š” ์ด์ƒ์ด ์—†๋‹คโ€๋Š” ๋ง์„ ๋“ฃ๊ณ  ์ƒ์ˆ˜ ์ตœ์ ํ™” ๋ฌธ์ œ์ธ๊ฐ€? ๋ผ๋Š” ์ƒ๊ฐ์„ ํ–ˆ์Šต๋‹ˆ๋‹ค. ์•„๋ž˜๋Š” TLE์˜ ๊ธฐ๋ก์ž…๋‹ˆ๋‹ค. ใ…‹ใ…‹โ€ฆ

  • ์ฝ”๋“œ ์‚ฌ๋ฐฉ์— std::map<int, int>์„ ๋–ก์น ํ•ด์„œ ๋Š๋ฆฐ๊ฒƒ์œผ๋กœ ์ƒ๊ฐํ•˜๊ณ , Stet-stet๊ณผ ์ œ๊ฐ€ ์ •๋ ฌ์„ฑ์ด ํ•„์š”์—†๋‹ค๋ฉด std::unordered_map ์œผ๋กœ ๋ฐ”๊ฟ€๊ฒƒ์„ ์ œ์•ˆํ–ˆ์Šต๋‹ˆ๋‹ค.
  • ๊ทธ๋ž˜๋„ TLE๋ฅผ ๋ฐ›์•„์„œ, ๋„๋Œ€์ฒด ๋ฌด์Šจ ๋ฌธ์ œ์ธ์ง€ ์ฐพ๊ธฐ ์œ„ํ•ด ๋กœ์ปฌ์—์„œ ๋ฌด๋ ค max test๋ฅผ ๋งŒ๋“ค๊ธฐ๋กœ ํ–ˆ์Šต๋‹ˆ๋‹ค. ๋žœ๋ค ํŽ˜์–ด๋ง์œผ๋กœ ํ† ๋„ˆ๋จผํŠธ๋ฅผ ๋งŒ๋“ค๊ณ  ํ•˜๋‚˜๋ฅผ ๋ฒ„๋ฆฌ๋Š” ๊ฒƒ์€ 5๋ถ„์ด๋ฉด ์งค ์ˆ˜ ์žˆ์œผ๋‹ˆโ€ฆ
  • ๋†€๋ž๊ฒŒ๋„ DHDroid์˜ ์ฝ”๋“œ๋Š” ๋กœ์ปฌ (์ œ M1 Pro ๋งฅ๋ถ) ์—์„œ max case์— ๋Œ€ํ•œ ๋‹ต์„ 1์ดˆ ์ด๋‚ด์— ์ฐพ๊ณ  ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค. ์ œํ•œ ์‹œ๊ฐ„์€ 2์ดˆ์˜€์œผ๋ฏ€๋กœ ์ด๋Š” ์ƒ๋‹นํžˆ ์ˆ˜์ƒํ–ˆ์Šต๋‹ˆ๋‹ค.
  • M1์ด ๋ฏธ์นœ ์นฉ์ด๋ผ ๊ทธ๋Ÿฐ๊ฑฐ ์•„๋‹ˆ๋ƒ? ๋Š” ์–˜๊ธฐ๋ฅผ ํ•˜๊ณ , ์ผ๋‹จ ์‹œ๊ฐ„์„ ๋” ์ค„์ด๊ธฐ๋กœ ํ–ˆ์Šต๋‹ˆ๋‹ค. ์ด๊ฒƒ์ €๊ฒƒ ์ปคํŒ…์„ ์ข€ ํ•˜๋‹ˆ ์‹œ๊ฐ„์ด ๋กœ์ปฌ์—์„œ 0.7์ดˆ๋Œ€๋กœ ์ค„์–ด๋“ค์—ˆ๊ณ , ์—ฌ์ „ํžˆ TLE๋ฅผ ๋ฐ›์•˜์Šต๋‹ˆ๋‹ค.
  • ๊ฒฐ๊ตญ ์ œ๊ฐ€ โ€œ์ด๋ ‡๊ฒŒ๋œ๊ฑฐ FAST IO๋ฅผ ์งœ๊ฒ ๋‹คโ€๋ผ๊ณ  ์ปดํ“จํ„ฐ๋ฅผ ์žก์•˜๋Š”๋ฐ, ํŒ€๋…ธํŠธ์— Fast hash table ์ด ์žˆ์Œ์„ ๋– ์˜ฌ๋ฆฌ๊ณ  ๊ทธ๊ฑธ ์ง‘์–ด๋„ฃ์—ˆ์Šต๋‹ˆ๋‹ค.
  • ๋กœ์ปฌ์—์„œ๋Š” 0.4์ดˆ๋Œ€, ์„œ๋ฒ„์—์„œ 1.32์ดˆ๋กœ ํ†ต๊ณผํ–ˆ์Šต๋‹ˆ๋‹ค.

์ฐธ๊ณ  : Fast hash table์€ Codeforces Link ์— ์žˆ๋Š” __gnu__pdbs::gp_hash_table ์ด๋ฉฐ, GCC ์ปดํŒŒ์ผ๋Ÿฌ์˜ ํ™•์žฅ ์ž๋ฃŒ๊ตฌ์กฐ ์ค‘ ํ•˜๋‚˜์ž…๋‹ˆ๋‹ค. ์ผ๋ฐ˜์ ์œผ๋กœ unordered_map๋ณด๋‹ค ์ˆ˜ ๋ฐฐ ๊ฐ€๊นŒ์ด ๋น ๋ฅด๋‹ค๊ณ  ์•Œ๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค.

์ด๋Ÿฐ ๋ฌธ์ œ๋ฅผ ์ง€์–‘ํ•˜๋Š” ๊ฒƒ์œผ๋กœ ์•Œ๋ ค์ง„ UCPC์— ์™œ ์šฐ๋ฆฌ๋Š” ์ด๋Ÿฐ ์ฐธ์‚ฌ๊ฐ€ ๋ฒŒ์–ด์กŒ๋Š”์ง€๋Š” ์•Œ ์ˆ˜ ์—†์œผ๋‚˜, ์•„๋งˆ๋„ ์ •ํ•ด๊ฐ€ ํ•ด์‹œํ…Œ์ด๋ธ”์„ ์“ฐ๋Š”๊ฒŒ ์•„๋‹ˆ์ง€ ์•Š์„๊นŒ ์‹ถ์Šต๋‹ˆ๋‹ค. ์Šฌ๋ผ์ด๋“œ์—๋„ ์–ธ๊ธ‰๋˜์ง€ ์•Š์€๊ฑธ๋ณด๋‹ˆ ์ €ํฌ๊ฐ€ ์ด์ƒํ•˜๊ฒŒ ํ‘ผ๊ฒƒ ๊ฐ™๊ธด ํ•œ๋ฐ, ์•„๋ฌดํŠผ ์ด ๋ฌธ์ œ์— ๋ฌด๋ ค 1.5์‹œ๊ฐ„์ด ๋“ค์–ด๊ฐ”์Šต๋‹ˆ๋‹ค.

Phase 3 : Segment Tree (D - ์ „๋Œ€ํ”„์—ฐ ํ† ๋„ˆ๋จผํŠธ, F - ๋Œ€์ถฉ~๋ชฌ์Šคํ„ฐ~๊ฒŒ์ž„)

๊ทธ๋™์•ˆ ์ €๋ž‘ stet-stet์€ ๋’ค ๋ช‡๋ฌธ์ œ๋ฅผ ๊ณ ๋ฏผํ–ˆ์Šต๋‹ˆ๋‹ค. C๋ฒˆ์€ ์˜ˆ์ œ๋ฅผ ๋ณด๊ณ  ๋„ˆ๋ฌด ์–ด๋ ค์šด๊ฑฐ ๊ฐ™๋‹ค ๊ณ  ๋ฒ„๋ ธ๊ณ , D๋Š” stet-stet์ด, F๋Š” ์ œ๊ฐ€ ์žก๊ณ  ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค. ์ €ํฌ ๋‘˜๋‹ค M๊ฐ™์€ ๋ฅ˜์˜ ์ˆ˜ํ•™๋ฌธ์ œ๋ฅผ ์ข‹์•„ํ•ด์„œ ์ข€ ๊ณ ๋ฏผํ•ด๋ณด์•˜๋Š”๋ฐ ๋‹คํ•ญ์‹๋“ค์„ ๋น ๋ฅด๊ฒŒ ๊ด€๋ฆฌํ•œ๋‹ค๋Š” ์ ์—์„œ FFT๋ฅผ ์ž˜ ์“ด๋‹ค๋Š”๊ฑด ์•Œ๊ฒ ์ง€๋งŒ ๊ทธ์ด์ƒ์€ ์–ป์ง€ ๋ชปํ–ˆ์Šต๋‹ˆ๋‹ค.

D๋Š” stet-stet์ด Lazy seg๋กœ ํ’€ ์ˆ˜ ์žˆ๋‹ค ๊ณ  ํ–ˆ๊ณ , ์ €๋Š” ์ˆ˜์ฟผ๋ฅ˜ ๋ฌธ์ œ๋ฅผ ์ž˜ ๋ชจ๋ฅด๊ธฐ ๋•Œ๋ฌธ์— ๊ทธ๋Ÿฐ๊ฐ€๋ณด๋‹ค ํ•˜๊ณ  ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค. ์—ฌ๊ธฐ์„œ๋ถ€ํ„ฐ segment tree ๋Œ€์ฐธ์‚ฌ ๊ฐ€ ๋ฒŒ์–ด์กŒ์Šต๋‹ˆ๋‹ค

  • ๋•Œ๋Š” ๋‘๋ฒˆ์งธ ํŒ€์—ฐ์Šต (Jakarta 2019) ์ดํ›„, stet-stet์ด ํ˜„์žฌ ์žˆ๋Š” ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ ๊ตฌํ˜„์„1 ๋งค์šฐ genericํ•œ ๊ตฌํ˜„์œผ๋กœ ๊ต์ฒดํ•  ๊ฒƒ ์„ ์ œ์•ˆํ–ˆ์Šต๋‹ˆ๋‹ค
  • ์ด ์ƒˆ๋กœ์šด ๊ตฌํ˜„์ฒด๋Š” template ํ•จ์ˆ˜๋ฅผ ๊ต‰์žฅํžˆ extensiveํ•˜๊ฒŒ ํ™œ์šฉํ•ด์„œ, ํ•ฉ์„ธ๊ทธ๋ฅผ xor์„ธ๊ทธ๋‚˜ ๊ณฑ์„ธ๊ทธ๋กœ ๊ต์ฒดํ•˜๋Š” ๊ฒƒ์ด ํ•จ์ˆ˜ ํ•˜๋‚˜๋ฅผ ๊ฐˆ์•„๋ผ์›€์œผ๋กœ์จ ๊ฐ€๋Šฅํ•˜๊ณ  ์ „์ฒด์— mod P ๋“ฑ์„ enforceํ•˜๋Š”๊ฒƒ์ด ๋งค์šฐ ์‰ฝ๋‹ค๋Š” ์žฅ์ ์ด ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค.
  • ์ผ๋ถ€ ์ด ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ์— ์šฐ๋ฆฌ๊ฐ€ ์ƒ๋Œ€์ ์œผ๋กœ ์ต์ˆ™ํ•˜์ง€ ๋ชปํ•˜๊ณ , ํƒ€์ดํ•‘๋Ÿ‰์ด ์ข€ ๋Š˜์–ด๋‚œ๋‹ค๋Š” ์  ๋“ฑ์ด ์กฐ๊ธˆ ๊ฑฑ์ •์Šค๋Ÿฌ์šด ๊ฒƒ์€ ์‚ฌ์‹ค์ด์—ˆ์œผ๋‚˜, ์‹ ๊ธฐํ•œ ์„ธ๊ทธ ์“ฐ๋Š” ๋ฌธ์ œ๊ฐ€ ์ƒ๊ฐ๋ณด๋‹ค ์žฆ๊ณ  ์ด๊ฑธ ์ž˜ ์ด์šฉํ•˜๋ฉด ๊ธฐ๋ณธ๋ฌธ์ œ๋ถ€ํ„ฐ ๊ธˆ๊ด‘์„ธ๊ทธ๊นŒ์ง€ ์ž˜ ์ปค๋ฒ„ํ• ์ˆ˜์žˆ๋‹ค๋Š” ์ ์ด ๊ต‰์žฅํžˆ ๋งค๋ ฅ์ ์œผ๋กœ ๋‹ค๊ฐ€์™€์„œ ์ด ๋ณ€๊ฒฝ์„ approveํ–ˆ์Šต๋‹ˆ๋‹ค.
  • ๋‹ค๋งŒ ์ œ๋„ค๋ฆญํ•œ ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ ๊ตฌํ˜„์ฒด๋Š” ๋ช‡๊ฐ€์ง€ ๊ธฐ๋ณธ์ ์ธ ๊ฐ€์ •์— ๊ธฐ๋ฐ˜ํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ์ •ํ™•ํ•œ ๊ฐ€์ •์˜ ์ง‘ํ•ฉ์€ ๋ชจ๋ฅด๊ฒ ์ง€๋งŒ ์ฒ˜์Œ ์„ค๋ช…์„ ๋“ฃ๊ณ  ์ฝ”๋“œ๋ฅผ ๋ดค์„๋•Œ๋Š” ์ถฉ๋ถ„ํ•ด ๋ณด์˜€์Šต๋‹ˆ๋‹ค
  • ์ฝ”๋“œ๋ฅผ ์ˆ™์ง€ํ•ด์•ผ๊ฐ€์•ผํ•œ๋‹ค๋Š” ์ƒ๊ฐ์€ ํ–ˆ์ง€๋งŒ, ๋ฐ˜๋Œ€๋กœ ํ…œํ”Œ๋ฆฟ์ด ์—„์ฒญ ์ œ๋„ค๋ฆญํ•˜๋‹ˆ๊นŒ ์ง„์งœ ๊ฐˆ์•„ ๋ผ์šฐ๊ธฐ๋งŒ ํ•˜๋ฉด ์‚ฌ์‹ค S.modify ์™€ S.query๋งŒ ์จ์„œ ํ’€์ˆ˜์žˆ์ง€ ์•Š์„๊นŒ? ๋ผ๋Š” ์ƒ๊ฐ์ด ๋“ค์–ด์„œ ๊ทธ๋ƒฅ ๋‚จ์€ ์‹œ๊ฐ„๋™์•ˆ ์ ‘๋ฏธ์‚ฌ ๋ฐฐ์—ด ๊ฐ™์€ ์ฃผ์ œ๋“ค์„ ๊ณต๋ถ€ํ•˜๋Š”๋ฐ ํˆฌ์žํ–ˆ์Šต๋‹ˆ๋‹ค

๊ฒฐ๊ตญ, ํ˜„์žฅ์—์„œ๋Š” ์ด๋Ÿฐ ๋ฌธ์ œ๋“ค์ด ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค.

  • Stet-stet์€ D์— ๋Œ€ํ•œ ๊ทธ๋Ÿด์‹ธํ•œ ํ’€์ด์— ๋„๋‹ฌํ–ˆ๊ณ , ์ €๋Š” 100%๋ฅผ ์ดํ•ดํ•˜์ง€๋Š” ๋ชปํ–ˆ์œผ๋‚˜ ๋Œ€์ถฉ ๋งž๋Š” ๋ฐฉํ–ฅ ์ด๋ผ๋Š” ์ƒ๊ฐ์€ ๋“ค์—ˆ์Šต๋‹ˆ๋‹ค. DHDroid๋„ ๋น„์Šทํ•˜๊ฒŒ ํŒ๋‹จํ–ˆ์Šต๋‹ˆ๋‹ค.
  • D๋Š” ์ƒ๋‹นํžˆ ๋ณต์žกํ•œ ํ˜•ํƒœ์˜ segtree ํ™œ์šฉ์„ ์š”๊ตฌํ–ˆ๊ณ , ์†”๋ฃจ์…˜์„ ๋– ์˜ฌ๋ฆฐ Stet-stet์€ ์ด ๋ฌธ์ œ๋ฅผ ํ’€ ํฌ๋ง์ด ์žˆ๋Š” ์œ ์ผํ•œ ํŒ€์›์ด์—ˆ๊ธฐ์— PC๋ฅผ ๋„˜๊ฒผ์Šต๋‹ˆ๋‹ค.
  • ์ด ๊ตฌํ˜„์€ ๊ฒฐ๊ตญ ๋Œ€ํšŒ๊ฐ€ ๋๋‚ ๋•Œ๊นŒ์ง€ ์™„๋ฃŒ๋˜์ง€ ๋ชปํ–ˆ์Šต๋‹ˆ๋‹ค. ๋‚˜์ค‘์— ๋“ฃ๊ณ  ๋ณด๋‹ˆ, ์•ž์„œ์˜ ์ œ๋„ค๋ฆญํ•œ ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ ๊ฐ€ ๊ฐ–๋Š” ๊ธฐ๋ณธ์  ๊ฐ€์ • ์—์„œ ๋ฒ—์–ด๋‚œ ๊ตฌํ˜„์ด ํ•„์š”ํ–ˆ๋‹ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

F๋ฒˆ (๋Œ€์ถฉ~๋ชฌ์Šคํ„ฐ~๊ฒŒ์ž„) ์€ ์ €์™€ DHDroid๊ฐ€ ์žก์•˜์Šต๋‹ˆ๋‹ค. ๋Œ€์ถฉ ์–˜๊ธฐํ–ˆ๋˜ ๊ฒƒ๋“ค์„ ๊ธฐ์–ต์„ ๋˜์งš์–ด ๋ณด๋ฉดโ€ฆ

F - ๋Œ€์ถฉ ์นด๋“œ๋กœ ๋ชฌ์Šคํ„ฐ ์žก๋Š” ๊ฒŒ์ž„

๋‚œ์ด๋„ : P1             AC Time : After freeze
solve : DHDroid, Gratus907
code : DHDroid, Gratus907
  • ๋งŒ์•ฝ, ํ˜„์žฌ ์–ด๋–ค ๋ชฌ์Šคํ„ฐ๊ฐ€ ์žˆ๊ณ  ๋‚ด ์†์— ๊ทธ ๋ชฌ์Šคํ„ฐ๋ฅผ ์žก์„ ์ˆ˜ ์žˆ๋Š” ๋งค์นญ๋˜๋Š” ์นด๋“œ๊ฐ€ ์žˆ๋‹ค๋ฉด, ๋ฐ˜๋“œ์‹œ ์žก๋Š” ๊ฒƒ์ด ์ž๋ช…ํ•˜๊ฒŒ ์ตœ์ ์ž…๋‹ˆ๋‹ค.
  • ์•ฝ๊ฐ„ ๋ฐ˜๋Œ€๋กœ ์ƒ๊ฐํ•ด์„œโ€ฆ โ€œ๋ฆฌํ•„์‹œ์ โ€ ์„ ๋ฏธ๋ฆฌ ๊ณ ์ •ํ•œ๋‹ค๊ณ  ์ƒ๊ฐํ•˜๋ฉด
    • ๋ฆฌํ•„์‹œ์ ์ด $t_1, t_2$๋ผ๊ณ  ํ•  ๋•Œ, $t_1$๋ถ€ํ„ฐ $t_2$ ๊นŒ์ง€์˜ ๋ชฌ์Šคํ„ฐ๋“ค ์ค‘ ๋ช‡๋งˆ๋ฆฌ๋‚˜ ์žก์„ ์ˆ˜ ์žˆ์„๊นŒ์š”?
    • ๊ทธ ๋‚ด๋ถ€์— ์žˆ๋Š” ๋ชฌ์Šคํ„ฐ์˜ ์ข…๋ฅ˜ ๋งŒํผ์„ ์žก์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด๋ฅผ score ๋ผ ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.
    • ๋‚˜๋จธ์ง€ ์นด๋“œ๋“ค์€ ๋Œ€์ถฉ ์•„๋ฌด๋ ‡๊ฒŒ๋‚˜ ๋ฒ„๋ฆฌ๋ฉด ๋ฉ๋‹ˆ๋‹ค.
    • $t_1$ ๋ถ€ํ„ฐ $t_2$ ์‚ฌ์ด์— ๋ฆฌํ•„์ด ๊ฐ€๋Šฅํ•˜๋ ค๋ฉด, ๊ทธ ์‚ฌ์ด ๊ฐ„๊ฒฉ์ด $\ceil{K/2}$ ๋ณด๋‹ค ์ปค์•ผ ํ•ฉ๋‹ˆ๋‹ค.

๋ฆฌํ•„ ์‹œ์ ์„ ๊ณ ์ •ํ•˜๊ณ  ๋ฌธ์ œ๋ฅผ ํ’€์ž (์–ด์ฐจํ”ผ ๋ฆฌํ•„ ์‹œ์ ์ด ๊ณ ์ •๋˜์–ด ์žˆ๋‹ค๋ฉด ์ „๋žต์ด ์œ ์ผ) ํ•˜๋‹ค๋Š” ์–˜๊ธฐ๋ฅผ DHDroid์™€ ๋‚˜๋ˆด์Šต๋‹ˆ๋‹ค. ๋ญ”๊ฐ€ DP์‹ ์ ‘๊ทผ๊นŒ์ง€๋Š” ์‰ฝ์Šต๋‹ˆ๋‹ค.

  • ์ฆ‰โ€ฆ๋‹ค์Œ๊ณผ ๊ฐ™์€ DP๋ฅผ ํ’€ ์ˆ˜ ์žˆ์œผ๋ฉด ๋ฉ๋‹ˆ๋‹ค. \(D[i] = \max \{ D[j] + \text{score}(j+1, i) \mid 1 \leq j \leq i - \ceil{K / 2}\}\)

์ด DP๋ฅผ ๊ฝค ์˜ค๋ž˜ ๊ณ ๋ฏผํ•˜๋‹ค๊ฐ€, ์ €๋Š” ๋‹ค๋ฅธ ๋ฌธ์ œ๋ฅผ ์ž ์‹œ ๋ณด๋˜ ๋„์ค‘ DHDroid๊ฐ€ โ€œ$D[j] + \text{score}(j+1, i)$ ๋ฅผ ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ๋กœ ๊ด€๋ฆฌโ€ ํ•˜๋Š” ํ’€์ด๋ฅผ ์ œ์•ˆํ–ˆ๊ณ , ๊ฑฐ์˜ ํŽ˜์–ด์ฝ”๋”ฉ์— ๊ฐ€๊น๊ฒŒ ๊ตฌํ˜„ํ–ˆ์Šต๋‹ˆ๋‹ค. ์ด ๊ณผ์ •์—์„œ D๋ฒˆ์—์„œ ์“ด ๋ ˆ์ด์ง€์„ธ๊ทธ ๊ตฌํ˜„์„ ์‚ฌ์šฉํ–ˆ๋Š”๋ฐ, ํŒ€๋…ธํŠธ๋ฅผ ํƒ€์ดํ•‘ํ•˜๋‹ค๊ฐ€ ์˜คํƒ€๊ฐ€ ์žˆ์—ˆ์Œ์„ ๋ชจ๋ฅด๊ณ  ๊ณ„์† ์ œ์ถœํ•˜๋ฉฐ ํ‹€๋ฆฌ๋Š” ๋“ฑ(โ€ฆ) ๋Œ€์ฐธ์‚ฌ๊ฐ€ ๋ฐœ์ƒํ–ˆ์Šต๋‹ˆ๋‹ค.

์ด ๋ฌธ์ œ๋Š” ๋‚œ์ด๋„๊ฐ€ P1์ด๊ธฐ๋Š” ํ•˜์ง€๋งŒ, ์†”์งํžˆ ๊ทธ๋ ‡๊ฒŒ๊นŒ์ง€ ๊ณ ์ „ํ–ˆ์–ด์•ผ ํ•  ๋ฌธ์ œ์˜€๋‹ค๋Š” ์ƒ๊ฐ์ด ๋“ค์ง€๋Š” ์•Š์Šต๋‹ˆ๋‹ค. ๊ตฌํ˜„์ƒ์˜ ์‹ค์ˆ˜๊ฐ€ ๋ผˆ์•„ํ”•๋‹ˆ๋‹ค.


F๋ฅผ ๋งž์ถ”๊ณ  ๋‚˜์„œ๋Š”, Stet-Stet์ด D๋ฒˆ๊ณผ ๊ณ„์† ์‹ธ์šฐ๋Š” ๋™์•ˆ I (์‚ฌ๊ฑด์˜ ์ง€ํ‰์„ ), M(x+ +x) ๋“ฑ์„ ์ฝ์—ˆ์Šต๋‹ˆ๋‹ค. DHDroid์™€ ์ œ๊ฐ€ (์‚ฌ์‹ค DHDroid๊ฐ€ ๊ฑฐ์˜ ํ˜ผ์ž) I๋ฒˆ ํ’€์ด๋„ ๋…ผ์˜๋์— ์™„์„ฑํ–ˆ๋Š”๋ฐ, ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ๋ฅผ ๋งŒ๋“ ๋‹ค์Œ ๊ทธ ๋…ธ๋“œ๋“ค์—์„œ SCC๋ฅผ ๋Œ๋ฆฌ๋Š” ๋ฌธ์ œ๋กœ ์ƒ๋‹นํžˆ ๊ตฌํ˜„์ด ๋นก์„ธ์ง€๋งŒ ์‹œ๊ฐ„๋งŒ ๋งŽ์•˜๋‹ค๋ฉด (๊ณผ์—ฐโ€ฆ?) ํ• ๋งŒํ•ด ๋ณด์˜€์Šต๋‹ˆ๋‹ค. :(

Post Mortem

UCPC๋Š” ํ•ญ์ƒ PS์˜ ์ฆ๊ฑฐ์›€๊ณผ ์šฐ๋ฆฌ ์‹ค๋ ฅ์˜ ๋ฏธ์ง„ํ•จ์„ ๊นจ์šฐ์ณ์ฃผ๋Š” ๋Œ€ํšŒ์ž…๋‹ˆ๋‹ค. ICPC์— ๋น„ํ•ด ์ข€๋” OI-ํ‹ฑํ•œ ๋ฌธ์ œ๊ฐ€ ๋‚˜์™€์„œ ๋” ๊ทธ๋Ÿฐ๊ฒƒ ๊ฐ™๊ธฐ๋„ ํ•ฉ๋‹ˆ๋‹ค.

์˜ฌํ•ด์˜ ์ƒˆ๋กœ์šด ํŒ€์› Stet-Stet์€ ๊ฝค ๋†’์€ ํ™•๋ฅ ๋กœ ์ €๋ž‘ ๊ฐ™์ด ์ œ ๋งˆ์ง€๋ง‰ ICPC๋ฅผ ๋›ธ๊ฑฐ ๊ฐ™์€๋ฐ, ์ด์ œ ๋”ฑํžˆ CP ์„ฑ์ ์—๋Š” ๋ฏธ๋ จ์€ ์—†์ง€๋งŒ ์ด๋ฒˆ ๋Œ€ํšŒ์—์„œ ๋Š๋‚€๊ฑธ ๋Œ€์ถฉ ์ ์–ด๋ณด์ž๋ฉดโ€ฆ.

  • ํŒ€๋…ธํŠธ์˜ ๊ตฌํ˜„์ฒด๋ฅผ Black-box๋กœ ํ™œ์šฉํ•˜๋Š” ๊ฒƒ์€ ์ƒ๋‹นํžˆ ์œ„ํ—˜ํ•จ์„ ๊นจ๋‹ฌ์•˜์Šต๋‹ˆ๋‹ค. ๋งŒ์•ฝ ์ œ๋„ค๋ฆญํ•œ ๊ตฌํ˜„์ฒด๋ฅผ ์ €๋‚˜ DHDroid๊ฐ€ ์ดํ•ดํ•˜๊ณ  ์žˆ์—ˆ์œผ๋ฉด ํ›จ์”ฌ ํŽธํ–ˆ์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ดํ•ดํ•˜๊ธฐ ์–ด๋ ต๊ฑฐ๋‚˜ ์‹œ๊ฐ„์ด ๋งŽ์ด ๋“œ๋Š” ๊ตฌํ˜„์ฒด๋ผ๋ฉด ์ฐจ๋ผ๋ฆฌ ๊ฐ„๊ฒฐํ•œ ๊ฒƒ์„ ๊ฐ€์ ธ๊ฐ€๋Š” ๊ฒƒ์ด ๋‚˜์„ ์ˆ˜๋„ ์žˆ์—ˆ๊ฒ ์Šต๋‹ˆ๋‹ค.
  • ๋ฐ˜๋ฉด์—, ์ €ํฌ์ฒ˜๋Ÿผ ๊ตฌํ˜„๋ ฅ์ด thinking์— ๋น„ํ•ด ๋งŽ์ด ๋”ธ๋ฆฌ๋Š” ํŒ€์€ ํŒ€๋…ธํŠธ์— ์ตœ๋Œ€ํ•œ ๋งŽ์€ ๊ฒƒ์„ packingํ•ด๊ฐ€๋Š” ๊ฒƒ์ด ์œ ํšจํ•ฉ๋‹ˆ๋‹ค. ๋‹น์žฅ ์ €ํฌ๊ฐ€ ๋ชปํ’€๊ธฐ๋Š” ํ–ˆ์ง€๋งŒ E(LR-Flow), M(FFT) ๋“ฑ ๋– ์˜ฌ๋ ธ๋”๋ผ๋„ ํŒ€๋…ธํŠธ๊ฐ€ ์—†์—ˆ๋”๋ผ๋ฉด ์†์„ ๋ชป๋Œ”์„ ๋ฌธ์ œ๋“ค์ด ๊ฝค ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค.

๋Œ€ํšŒ๊ฐ€ ๋๋‚˜๊ณ ๋Š” ์˜ˆ์ „๋ถ€ํ„ฐ Hashcode ๋“ฑ์œผ๋กœ ํ•จ๊ป˜ํ–ˆ๋˜ Coffeetea, Dlwocks31์ด ์ƒˆ๋กœ ํ•™๊ณผ ๋™๊ธฐ์ธ Nevivurn์„ ์˜์ž…ํ•ด์„œ ๊ฒฐ์„ฑํ•œ Industrial Function Agent2 ์™€ ๊ณ ๊ธฐ๋ฅผ ๋จน์œผ๋Ÿฌ ๊ฐ”์Šต๋‹ˆ๋‹ค. :blobaww: ์ด์ชฝํŒ€๋„ ์ƒ๋‹นํžˆ ์žฌ๋ฐŒ๋Š”๋ฐ, ์—ฌ๊ธฐ๋Š” F๋ฅผ ํ’€์ง€ ๋ชปํ•œ ๋Œ€์‹  C๋ฅผ ํ•ด๊ฒฐํ–ˆ์Šต๋‹ˆ๋‹ค. ์ €ํฌ๋ž‘ ๋น„๊ตํ–ˆ์„ ๋•Œ ์—„๋ฐ€ํ•œ ๋…ผ์ฆ๋ณด๋‹ค๋Š” ์ง๊ด€๋ ฅ์ด ๋›ฐ์–ด๋‚œ ํŒ€์› ๊ตฌ์„ฑ์ด ํฐ ์˜ํ–ฅ์ด ์žˆ์ง€ ์•Š์€๊ฐ€ ์‹ถ์Šต๋‹ˆ๋‹ค.

์ด๊ธฐํšŒ์— ๋‚ด๋ ค๋†จ๋˜ algorithmic thinking์„ ๋˜์ฐพ๊ธฐ ์œ„ํ•ด Dlwocks31๊ณผ (+ ๋‘ ํŒ€์˜ ํŒ€์›๋“ค ํ•จ๊ป˜) weekly rehab ์Šคํ„ฐ๋””๋ฅผ ๊ฒฐ์„ฑํ•˜๊ธฐ๋กœ ์–˜๊ธฐํ–ˆ์Šต๋‹ˆ๋‹ค.

์˜ค๋žœ๋งŒ์˜ ์˜คํ”„๋ผ์ธ ๋Œ€ํšŒ์น˜๊ณ ๋Š” ์ƒ๋‹นํžˆ frustratingํ–ˆ์Šต๋‹ˆ๋‹ค. Competition์„ ๋‚ด๋ ค๋†“์•„์•ผ ๋” ์ฆ๊ธธ ์ˆ˜ ์žˆ์„ํ…๋ฐ ํ•˜๋Š” ์ƒ๊ฐ๋„ ๋“ค๊ณ โ€ฆ ๊ทธ๋ž˜๋„ ๊ฐœ์ธ๋Œ€ํšŒ์˜€๋‹ค๋ฉด 5์‹œ๊ฐ„์— ์ €๋Ÿฐ ๊ตฌํ˜„์‹ค์ˆ˜๋‚˜๋ฉด ์ง‘์ค‘ํ•˜์ง€ ๋ชปํ–ˆ์„ํ…๋ฐ, ํŒ€๋Œ€ํšŒ๋ผ์„œ ์ข€๋” ์žฌ๋ฐŒ๊ฒŒ ์น˜๋ฅผ ์ˆ˜ ์žˆ์ง€ ์•Š์•˜๋‚˜ ์‹ถ์Šต๋‹ˆ๋‹ค.

Kudos to my dear teammates - Stet-stet & DHDroid :)


  1. ์ €ํฌ (3ํผํ”Œ ๊ทผ์ฒ˜) ๋ ˆ์ดํŒ…๋Œ€์˜ ํŒ€์ด ํŒ€๋…ธํŠธ์— ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ๋ฅผ ์ ์–ด๊ฐ€์•ผํ•œ๋‹ค๋Š”๊ฒŒ ์‚ฌ์‹ค ์กฐ๊ธˆ ์˜์•„ํ•˜์ง€๋งŒ, PS๋ฅผ ์—ฐ ๋‹จ์œ„๋กœ ์‰ฐ ์ €๋Š” ์†”์งํžˆ ์•‰์•„์„œ ์„ธ๊ทธํŠธ๋ฆฌ๋ฅผ ์‹ค์ˆ˜์—†์ด ๊ตฌํ˜„ํ•ด์˜ฌ ์ž์‹ ์ด ๋ณ„๋กœ ์—†์Šต๋‹ˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์ƒ๊ฐ๋ณด๋‹ค 25ํŽ˜์ด์ง€๊ฐ€ ๋งŽ์•„์„œ ๋„ฃ์„์ˆ˜์žˆ๋Š”๊ฒŒ ๋งŽ๋”๊ตฐ์š”โ€ฆย โ†ฉ

  2. ์ด๊ณณ์˜ ํŒ€์› ์ด๋ฆ„์€ ์š”์›1, ์š”์›2, ์š”์›3์ธ๋ฐ, ๋ˆ„๊ฐ€ 1/2/3์ธ์ง€์˜ ๊ตฌ๋ถ„์€ ์—†๊ณ  ๊ทธ์ž๋ฆฌ์—์„œ ๋žœ๋คํ•˜๊ฒŒ ์ด๋ฆ„ํ‘œ๋ฅผ ๋‚˜๋ˆ ๊ฐ€์ง„๋“ฏ ํ–ˆ์Šต๋‹ˆ๋‹ค. ใ…‹ใ…‹โ€ฆย โ†ฉ