A | B | C | D | E | F | G |
---|---|---|---|---|---|---|
AC | AC | AC | AC | AC | AC | AC |
Div 4๊ธด ํ์ง๋ง, ์ฒ์ ํด๋ณด๋ All Solve! ํ ํด์ ๋ง์ง๋ง ์ฝํฌ๋ก ์ฌ๋ฐ๊ฒ ์ฐธ๊ฐํ๊ณ , ๋ฟ๋ฏํ๋ค.
๋ช๋ฒ ๋์๋ A ^ B ^ C
๊ตฌํ๊ธฐ ๋ฌธ์ . ๊ฐ์ ์๋ ๋๋ฒ XOR
ํ๋ฉด ์ฌ๋ผ์ง๋ค!
๋จ์ ๊ตฌํ ๋ฌธ์ . ์๋ ๋ฌธ์๋ฅผ ์ฐพ์ผ๋ฉด ๋๋ค.
๋๋ ๊ทธ๋ฅ ์ซ์ ๋ค ๋ํ ๋ค์์ sqrt
๋๋ฆฐ ํ ์ ๊ณฑํด์ ์๋ ์ซ์๊ฐ ๋์ค๋์ง๋ก ๋ดค๋ค. ์ ์์ sqrt
๋ ์ ํํ๊ฒ ๊ณ์ฐ๋๋ค. (์ ๊ณฑ์๊ฐ ๋ง์ ๊ฒฝ์ฐ)
C
, V
๊ฐ ์ ์๋๊ณ , greedy
ํ๊ฒ ๋จ์ด๋ฅผ ๋์ด์ฃผ๋ฉด ๋๋ ๋ฌธ์ . ์์ธ์ฒ๋ฆฌ ํ ๊ฒ ๋ณ๋ก ์์๋ค.
๋๋ ์ด๊ฒ F๋ณด๋ค ์ฌ์ ๋ค. F ํ๊ณ E๋ฅผ ํ์๋ค. ๊ทธ๋ฅ ์์์ ๋ณด๊ณ ์์๋ฉด ๋ฒ์ ์์ ํฉ์ ์ด๋ป๊ฒ ๋นจ๋ฆฌ ๊ตฌํ์ง? ํ ์ ์์ง๋ง, ์ฝํฌ ๋ฌธ์ ๊ฐ ๋ ๊ทธ๋ ๋ฏ ์ง์ & ํ์๋ฅผ ๋๋ ์๊ฐํด๋ณด๋ฉด ๋ต์ด ๊ธ๋ฐฉ ๋์จ๋ค. ์ฐจ์ด๋ฅผ ์์ํ ์ ์๋๋๊ฐ ํฌ์ธํธ.
์ฐ๋
ผ์ธ ๊ฒ๊ณผ๋ ๋ณ๊ฐ๋ก, solved tier ๊ธฐ์ค ์ด๋ฐ ์ธ๊ทธ๋จผํธ ํธ๋ฆฌ ๊ธฐ์ด ํ์ฉ ์ ํ์ P5
ํฐ์ด๋ฅผ ๋ฐ๋๋ค. ์
๋ ฅ์ ์ ๋ถ์ผ๋ก ์๊ฐํ๊ณ , ์์์ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํด์ ๋ฃจํ๋ฅผ ์์ํ๋ค. ๊ทธ๋ฆฌ๊ณ ๋ฃจํ๋ ๋์ ๊ธฐ์ค์ผ๋ก ์ง์ด๋ฃ์ผ๋ฉด์(๊ทธ๋ฆฌ๋ ๋ฌธ์ ๋ํ ์ ํ์ธ Job Scheduling ๋ฌธ์ ์์ ์ฐ๋ ๋ฐฉ์์ด๋ค.), ๊ธฐ์กด์ ์ ๋ถ์ ๋ช๊ฐ ๊ต์ฐจํ๋์ง ์ธ๋ฉด ๋๋ค. ์ด ๊ณผ์ ์์ Segment Tree
๋ PBDS
๊ฐ ํ์ํ๋ฐ, ๋๋ PBDS
๋ก ํ์๋ค. PBDS
์ order_of_key
๋ฉ์๋๋ฅผ ์ฌ์ฉํ๋ฉด ์ฝ๊ฒ ์ฟผ๋ฆฌ๋น ์ผ๋ก ์ฒ๋ฆฌ๊ฐ ๊ฐ๋ฅํด์ ํธํ๋ค.
๋ฐฑ์ค์ ์ ํํ๊ฒ ๊ฐ์ ๋ฌธ์ ๊ฐ ์๊ณ , P5
๋ฅผ ๋ฐ์๋ค.
์ ํด๋ ์์ ๊ฑฐ ์ต์ ๊ฐ๊ฒฉ ๊ธฐ์ค์ผ๋ก ๋ค์ต์คํธ๋ผ์ ์ฐ์ด๋ ๋ฐฐ์ด์ ํ์ฅํด์, dp[1001]
๋ฐฐ์ด์ ๋ง๋ค์ด์ ๋ค์ต์คํธ๋ผ๋ฅผ ์ฌ์ฉํ๋ ๊ฒ์ด๋ค. ๊ทธ๋์ ๋น์ฉ์ด 1000๊น์ง๋ก ์ ํ๋์ด ์๊ณ , ์ด๊ฒ์ด ์ถ์ ์๋๋ก ๋ณด์ธ๋ค.
๋ค๋ง, ์์ ๊ฑฐ ๊ฐ๊ฒฉ์ด ์ ์ด๋ 1์ด๋ผ๋ ์ ์ ์ด์ฉํด์, ๋ฐฑํธ๋ํน์ ๋นก์ธ๊ฒ ์ ์ฉํ๋ฉด ์ด ์ญ์๋ AC
๋ฅผ ๋ฐ๋๋ค. ์๋๋ ์ด ์ ์ ํ์ฉํ ํ์ด์ด๋ค. ์ฃผ์ ์ ๋ฌธ์ ๋ ๋์ผํ ๋ฐฉ์์ผ๋ก ํ๋ฆฐ๋ค. ์ ํด๋ฅผ ๋ชฐ๋์ด์ 12ํ ํ๊ฒ์ ์ ๋น๋ฐ์ด๋ค.