Back to : ps-weekly

August 09 - August 15, 2021

이 글에 κ΅¬ν˜„μ½”λ“œ 링크가 없더라도 PS 레포 링크 에 κ°€μ„œ λŒ€νšŒ λ‹¨μœ„λ‘œ λ“€μ–΄κ°€λ©΄ 보톡 μ˜¬λ €λ†“μ€ μ½”λ“œλ₯Ό λ³Ό 수 μžˆμŠ΅λ‹ˆλ‹€.

μ½λŠ” μ‚¬λžŒμ΄ 문제λ₯Ό 읽고 쑰금 생각해봀닀고 κ°€μ •ν•˜κ³ , λŒ€λž΅μ μΈ μ•„μ΄λ””μ–΄λ§Œ κ°„λ‹¨νžˆ 적을 μƒκ°μž…λ‹ˆλ‹€ γ…Žγ…Ž

Recent Updates

  • SCPC Round 2μ—μ„œ νƒˆλ½ν–ˆμŠ΅λ‹ˆλ‹€.
  • Codeforces 3λ²ˆλ§Œμ— μ˜€λ Œμ§€ 볡귀에 μ„±κ³΅ν–ˆμŠ΅λ‹ˆλ‹€.


Codeforces Round 738 (Div. 2)

  • Div.2 136λ“±, Rating 2055->2117
  • Performance 2271
  • Eλ²ˆμ—μ„œ mod 10μ–΅ 7인쀄 μ•Œκ³  (998,244,353μž…λ‹ˆλ‹€) 문제λ₯Ό μ œλŒ€λ‘œ μ•ˆμ½μ–΄μ„œ 25λΆ„μ˜ 디버깅 μ‹œκ°„κ³Ό 1틀을 ν—Œλ‚©ν–ˆμŠ΅λ‹ˆλ‹€. 그게 μ•„λ‹ˆμ—ˆλ‹€λ©΄ μ•„λ§ˆ 100λ“± 정도 ν–ˆμ„ν…λ° μ•„μ‰½λ„€μš”.
  • κ·Έμ™Έμ—λŠ” λΌμš΄λ“œ μžμ²΄λŠ” ꡉμž₯히 μž¬λ°Œμ—ˆμŠ΅λ‹ˆλ‹€. λΌμš΄λ“œ 전체에 λŒ€ν•œ 풀이글은 D2λ₯Ό μ—…μ†”λΉ™ν•œ 후에 μž‘μ„±ν•  μ˜ˆμ •μž…λ‹ˆλ‹€.

Codeforces Round 730 (Div. 2), Virtual

  • Virtual Round
  • κ·ΈλŸ­μ €λŸ­ μž¬λ°Œμ—ˆμŠ΅λ‹ˆλ‹€. Cλ²ˆμ€ μ‹€μˆ˜μ˜€μ°¨ μ΄μŠˆκ°€ μžˆμ—ˆλ‹€λŠ”λ° μ €λŠ” κ²½ν—˜ν•˜μ§€ μ•Šμ•˜μŠ΅λ‹ˆλ‹€.
  • Interactive λ¬Έμ œλŠ” μ—¬μ „νžˆ μ½”λ”© 이후 확인이 λ„ˆλ¬΄ λ”μ°ν•©λ‹ˆλ‹€.


κΈ°ν•˜ μ—°μŠ΅μ…‹μ„ λ§Œλ“€μ–΄μ„œ λŒμ•˜μŠ΅λ‹ˆλ‹€.

2016 μ„œμšΈλŒ€ν•™κ΅ ν”„λ‘œκ·Έλž˜λ° κ²½μ‹œλŒ€νšŒ D번, BOJ 13202 ν”Όμž 배치

  • λ‚œμ΄λ„ Gold II
  • κΈ°ν•˜λ₯Ό μ—΄μ‹¬νžˆ ν•˜λ©΄ ν’€ 수 μžˆμŠ΅λ‹ˆλ‹€.
  • κ°€μš΄λ° 원은 넓이와 λ‘˜λ ˆμ˜ 관계λ₯Ό 톡해 ꡬ할 수 있고, λ‚˜λ¨Έμ§€λŠ” μΉ¨μ°©ν•˜κ²Œ 삼각비λ₯Ό μ΄μš©ν•˜μ—¬ λͺ¨λ“  값을 κ³„μ‚°ν•˜λ©΄ λ©λ‹ˆλ‹€.
  • 맀번, μ„Έ λ°©ν–₯으둜 원을 그릴 수 μžˆμŠ΅λ‹ˆλ‹€. μ„Έ λ°©ν–₯ 쀑 κ°€μž₯ 큰 원 μͺ½μ— 원을 그리고, κ·Έμͺ½ λ°©ν–₯의 원 크기λ₯Ό μ€„μ΄λŠ” μ‹μœΌλ‘œ κ΅¬ν˜„ν•˜λ©΄ λ©λ‹ˆλ‹€.
  • 쒅이에 삼각비λ₯Ό μ—΄μ‹¬νžˆ κ³„μ‚°ν•˜λ©΄ 문제 μžμ²΄λŠ” 어렡지 μ•ŠμŠ΅λ‹ˆλ‹€.

2012 ICPC Daejeon Regional J, BOJ 9015 μ •μ‚¬κ°ν˜•

  • λ‚œμ΄λ„ Platinum V
  • $n$개의 μ μ—μ„œ, κ°€μž₯ 큰 μ •μ‚¬κ°ν˜•μ˜ 넓이λ₯Ό κ΅¬ν•˜λŠ” 문제.
  • κ°€μž₯ μ‰¬μš΄ 방법은 점 $p$ λ₯Ό κ³ μ •ν•˜κ³ , λ‹€λ₯Έ 점 $x, y$ 둜 변을 κ·Έμ–΄μ„œ (직각인 경우), $p, x, y$ 와 ν•¨κ»˜ μ •μ‚¬κ°ν˜•μ„ μ΄λ£¨λŠ” $q$κ°€ μ‘΄μž¬ν•˜λŠ”μ§€ 확인해볼 수 μžˆκ² μŠ΅λ‹ˆλ‹€. μ΄λŠ” 각 $p$에 λŒ€ν•΄ $n^2$ 번의 확인이 ν•„μš”ν•˜λ―€λ‘œ $O(n^3)$ μ•Œκ³ λ¦¬μ¦˜μž…λ‹ˆλ‹€.
  • 이 λ°©λ²•μœΌλ‘œλŠ” 해결이 λΆˆκ°€λŠ₯ν•©λ‹ˆλ‹€. 쒀더 λ³΅μž‘λ„λ₯Ό 쀄이기 μœ„ν•΄, λŒ€κ°μ„ μ„ κ³ μ •ν•˜κ² μŠ΅λ‹ˆλ‹€.
  • λŒ€κ°μ„ μ„ ν•˜λ‚˜ κ³ μ •ν•˜λ©΄, λ‹€λ₯Έ λŒ€κ°μ„ μ„ κ·Έμ–΄μ„œ λ‚˜λ¨Έμ§€ 두 점의 μœ„μΉ˜λ₯Ό νŠΉμ •ν•  수 μžˆμŠ΅λ‹ˆλ‹€. λ‚˜λ¨Έμ§€ 두 점이 $n$개의 점쀑에 μžˆλŠ”μ§€ ν™•μΈν•˜λ©΄ 되고, μ΄λŠ” set같은걸 μ“°λ©΄ $O(n^2 \log n)$ 에 ν•  수 μžˆμŠ΅λ‹ˆλ‹€.
  • μ œν•œ μ‹œκ°„μ΄ 무렀 10μ΄ˆμž„μ—λ„ λΆˆκ΅¬ν•˜κ³  μ‹œκ°„μ΄ μƒλ‹Ήνžˆ λΉ‘λΉ‘ν•©λ‹ˆλ‹€. μ €λŠ” set에 pointλ₯Ό λ„£λŠ” 것이 λŠλ¦°κ±΄κ°€ μ‹Άμ–΄μ„œ 점의 $x, y$ μ’Œν‘œλ₯Ό 잘 λ•Œλ €λ„£μ–΄μ„œ long long int ν•˜λ‚˜λ‘œ λ°”κΏ¨λ”λ‹ˆ κ°„λ‹Ήκ°„λ‹Ήν•˜κ²Œ ν†΅κ³Όν–ˆμŠ΅λ‹ˆλ‹€.
  • 팁으둜, λŒ€κ°μ„ μ— λŒ€ν•΄ λ‹€λ₯Έ 두 점의 μœ„μΉ˜λ₯Ό κ΅¬ν•˜λŠ” 방법쀑 ν•˜λ‚˜λŠ” 벑터연산을 잘 ν•˜λ©΄ λ˜λŠ”λ° κ·Έ κ³Όμ •μ—μ„œ 벑터에 1/2λ°°λ₯Ό ν•΄μ•Ό ν•©λ‹ˆλ‹€. 이런 문제λ₯Ό ν•΄κ²°ν•  λ•ŒλŠ” λͺ¨λ“  μ’Œν‘œλ₯Ό 2배둜 λŠ˜λ €μ„œ κ΅¬ν˜„ν•˜λ©΄ 쑰금 μ‰¬μ›Œμ§‘λ‹ˆλ‹€.

2019 μˆ­κ³ ν•œ Algorithm Camp Contest P, BOJ 17403 κ°€μž₯ λ†’κ³  넓은 μ„±

  • λ‚œμ΄λ„ Platinum IV
  • Convex Hull 을 ꡬ할 수 μžˆλŠ” 만큼 계속 κ΅¬ν•˜λ©΄ λ©λ‹ˆλ‹€.
  • 쒋은 κΈ°ν•˜ 라이브러리λ₯Ό 가지고 μžˆλ‹€λ©΄ μ‰½μŠ΅λ‹ˆλ‹€.

2009 Baltic Olympiad of Informatics, BOJ 2415 μ§μ‚¬κ°ν˜•

  • λ‚œμ΄λ„ Platinum I
  • λ°”λ‘œ μœ„ μœ„ 문제인 9015와 거의 λΉ„μŠ·ν•œλ°, μ§μ‚¬κ°ν˜• λ²„μ „μž…λ‹ˆλ‹€.
  • λ‹€μ–‘ν•œ λ°©λ²•μœΌλ‘œ λ³΅μž‘λ„λ₯Ό 쀄일 수 μžˆμŠ΅λ‹ˆλ‹€. μ €λŠ” λͺ¨λ“  $n^2$ 개의 μŒμ— λŒ€ν•΄ 두 점 μ‚¬μ΄μ—μ„œ 였λ₯Έμͺ½ λ°©ν–₯으둜 κ°€λŠ” 벑터λ₯Ό μ €μž₯ν•˜λ˜ ($x$μ’Œν‘œκ°€ κ°™μœΌλ©΄ μœ„ λ°©ν–₯)
  • map을 μ΄μš©ν•˜μ—¬ <였λ₯Έμͺ½μœΌλ‘œ κ°€λŠ” 벑터 : {μ‹œμž‘μ λ“€μ˜ 리슀트}> λ₯Ό μ €μž₯ν–ˆμŠ΅λ‹ˆλ‹€. 이제, μ–΄λ–€ 였λ₯Έμͺ½ λ°©ν–₯의 벑터 $p$에 λŒ€ν•΄, 두 μ‹œμž‘μ  $x, y$ κ°€ μžˆλ‹€λ©΄, $x$ 와 $x+p$, $y$, $y+p$ κ°€ λͺ¨λ‘ $n$개의 점듀 쀑에 μžˆμ—ˆλ‹€λŠ” λ§μ΄λ―€λ‘œ, 벑터 $r = y - x$ λ₯Ό κ³„μ‚°ν•˜μ—¬ $r$κ³Ό $p$κ°€ μˆ˜μ§ν•œμ§€ κ΄€μ°°ν•˜λ©΄ λ©λ‹ˆλ‹€.
  • λ³΅μž‘λ„λŠ” $n^2 \log n$ 인데, μ—¬μ „νžˆ key와 valueκ°€ point와 point list 인 맡이 λ„ˆλ¬΄ λŠλ¦½λ‹ˆλ‹€. 9015번처럼, 점을 잘 숫자둜 μΈμ½”λ”©ν•˜λ©΄ κ°„λ‹Ήκ°„λ‹Ήν•˜κ²Œ 톡과 κ°€λŠ₯ν–ˆμŠ΅λ‹ˆλ‹€. λ²”μœ„λ₯Ό 잘 보고 μ΄λ ‡κ²Œ ν•˜λ©΄ λ©λ‹ˆλ‹€.
    const int B = (int) 1e9;
    const int M = (int) 1e8;
    inline int ptoi (P p) {
      return (p.x + M)*B+(p.y+M);
    inline P itop(int x) {
      return P((x/B - M),((x%B)-M));