Back to : ps-weekly

July 29 - August 07, 2021

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

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

Recent Updates

  • SCPC Round 2μ—μ„œ κ°œκ³ μƒν–ˆμŠ΅λ‹ˆλ‹€. γ…‹γ…‹!


Samsung SCPC Round 2

Codeforces Educational Round 112

  • Div2 κΈ°μ€€ 274λ“±, Rating 1947 -> 1995 (+48)
  • Performance 2096
  • λͺ‡λ‹¬λ§Œμ˜ Codeforces 볡귀전.
  • Div2μ§€λ§Œ Eλ²ˆκΉŒμ§€ ν’€μ–΄μ„œ ꡉμž₯히 기뢄이 μ’‹μ•˜μŠ΅λ‹ˆλ‹€. λ³΅κ·€μ „μΈκ²ƒμΉ˜κ³ λŠ” λ ˆμ΄νŒ…λ„ 많이 μ˜¬λžκ³ β€¦

Codeforces Round 736 (Div 1)

  • Div1 κΈ°μ€€ 466λ“±, Rating 1995 -> 2055 (+60)
  • Performance 2200
  • UCPC도 λͺ»λ‚˜κ°€κ³  ν•˜λ‹€λ³΄λ‹ˆ κ·Έλƒ₯ CPκ°€ ν•˜κ³ μ‹Άμ–΄μ Έμ„œ μ’€ 자주 돌기둜 ν–ˆμŠ΅λ‹ˆλ‹€. μ˜€λ Œμ§€ νŒŒν‚Ήν•˜κ³  ICPC νŒ€ μ°Ύμ•„μ•Όμ£ .
  • Cλ²ˆμ— λΉ„ν•΄ D1번이 많이 μ‰¬μ› μŠ΅λ‹ˆλ‹€.


CF Edu112 E - Boring Segments

  • λ‚œμ΄λ„ 2100
  • μ–΄λ–€ subset을 κ³¨λΌμ„œ 전체λ₯Ό μ»€λ²„ν•˜λ˜, κ°€μ€‘μΉ˜μ˜ μ΅œλŒ€-μ΅œμ†Œ 값을 μ΅œμ†Œν™”ν•΄μ•Ό ν•©λ‹ˆλ‹€.
  • μ΄λŸ¬ν•œ 문제λ₯Ό Two pointerλΌλŠ” λ°©λ²•μœΌλ‘œ 잘 ν•΄κ²°ν•  수 μžˆμŠ΅λ‹ˆλ‹€. λ˜λŠ”, 각 μ‹œμž‘μ μ— λŒ€ν•΄ κ°€λŠ₯ν•œ 끝점을 이뢄 탐색해도 λ©λ‹ˆλ‹€.
  • λ‹€λ§Œ, 두 경우의 μ°¨μ΄λŠ”, $a-b$ λ₯Ό μ“°λ‹€κ°€ $a-(b+1)$ 을 μ“°λŠ”κ±Έλ‘œ μ „ν™˜ν•˜λŠ”κ²Œ λΉ λ₯΄λ©΄ νˆ¬ν¬μΈν„°λ₯Ό μ“°κ³ , μž„μ˜μ˜ $a-b$λ₯Ό μ‹œλ„ν•˜λŠ” 쿼리가 λΉ λ₯΄λ©΄ 이뢄탐색도 μ“Έ 수 μžˆμŠ΅λ‹ˆλ‹€.
  • 이 λ¬Έμ œλŠ”, ν›„μžμ˜ 쿼리가 μ–΄λ ΅κΈ° λ•Œλ¬Έμ— (κ°€λŠ₯ν• κ±°κ°™κΈ΄ν•œλ° 사싀 잘 λͺ¨λ₯΄κ² μŠ΅λ‹ˆλ‹€) νˆ¬ν¬μΈν„°λ₯Ό μ”λ‹ˆλ‹€. λ”°λΌμ„œ κ³ λ₯Έ $[l_i, r_i]$ λ“€μ˜ 집합이 ν•œκ°œλ§ŒνΌ λ°”λ€”λ•Œ 쿼리당 μ‹œκ°„μ΄ 짧아야 ν•©λ‹ˆλ‹€.
  • ν•˜λ‚˜λ₯Ό κ³ λ₯Ό λ•Œλ§ˆλ‹€ $[l_i, r_i]$ 에 1을 λ”ν•˜κ³  (골랐던걸 λΊ„λ•ŒλŠ” λ‹Ήμ—°νžˆ -1), λ§ˆμ§€λ§‰μ— $[1, n]$ 의 μ΅œμ†Œκ°’μ΄ 0인지 (μ»€λ²„ν•˜μ§€ λͺ»ν•¨), 0보닀 큰지 (컀버함) νŒμ •ν•  수 μžˆμŠ΅λ‹ˆλ‹€. 이 두 μ—°μ‚° λͺ¨λ‘ Lazy propagation이 적용된 segment tree둜 잘 ν• μˆ˜ μžˆμŒμ„ μ•Œκ³  μžˆμŠ΅λ‹ˆλ‹€. 이경우 ꡬ간 ν•˜λ‚˜λ₯Ό μΆ”κ°€ν•˜κ±°λ‚˜ λΉΌλŠ”λ° κ±Έλ¦¬λŠ” μ‹œκ°„μ΄ $O(\log n)$, νŒμ • μ‹œκ°„λ„ $O(\log n)$ μž…λ‹ˆλ‹€.
  • 이제, λ§ˆμ§€λ§‰μœΌλ‘œ 생각할 것은 μ›λž˜ λ¬Έμ œμ—μ„œλŠ” $[1, 3], [4, 5]$ κ°€ κ²ΉμΉ˜λŠ” κ²ƒμœΌλ‘œ μΈμ •λ˜μ§€ μ•Šμ§€λ§Œ μ„Έκ·ΈνŠΈλ¦¬λ‘œ λ°”κΏ€λ•ŒλŠ” 전체λ₯Ό μ»€λ²„ν•œλ‹€λŠ” False positive의 κ°€λŠ₯μ„±μž…λ‹ˆλ‹€. $[l_i, r_i]$ 듀을 세그에 λ”ν• λ•ŒλŠ” $[l_i, r_i)$ 둜 λ°”κΏ”μ„œ λ”ν•˜λ©΄ λ©λ‹ˆλ‹€.
  • μ—¬λ‹΄μœΌλ‘œ, μ €λŠ” $m, n$ 의 λ²”μœ„λ₯Ό ν—·κ°ˆλ €μ„œ μ‚½μ§ˆν•˜λ‹€κ°€ 1μ‹œκ°„ 59λΆ„ 51μ΄ˆμ— λŒ€νšŒμ’…λ£Œ 9초λ₯Ό 남겨두고 ACλ₯Ό λ°›μ•˜μŠ΅λ‹ˆλ‹€. γ…‹γ…‹!

CF R736 Div1 B - Integers have friends

  • κ°„λ‹¨ν•˜κ²Œ 생각할 수 μžˆλŠ” 것은, 주어진 μˆ˜λ“€μ˜ μΈμ ‘ν•œ μˆ˜λ“€ κ°„μ˜ μ°¨λ₯Ό μƒˆλ‘œμš΄ λ°°μ—΄λ‘œ λ§Œλ“€κ³  λ‚˜λ©΄, 이 λ°°μ—΄μ—μ„œ μ–΄λ–€ sub-arrayλ₯Ό λ½‘μ•„μ„œ κ·Έ gcdκ°€ 1보닀 크면 λœλ‹€λŠ” κ²ƒμž…λ‹ˆλ‹€.
  • GCDκ°€ 1이 μ•„λ‹Œ κ°€μž₯ κΈ΄ subarrayλ₯Ό μ°ΎλŠ” 것은 μ—­μ‹œ μœ„ λ¬Έμ œμ™€ λ˜‘κ°™μ΄, νˆ¬ν¬μΈν„° λ˜λŠ” 각 μ‹œμž‘μ μ—μ„œμ˜ μ΄λΆ„νƒμƒ‰μœΌλ‘œ ν•΄κ²°κ°€λŠ₯ν•©λ‹ˆλ‹€.
  • μ–΄λ–€ λΆ€λΆ„κ΅¬κ°„μ˜ GCDκ°€ 1인지 μ•„λ‹Œμ§€ λΉ λ₯΄κ²Œ νŒμ •ν•˜κΈ° μœ„ν•΄μ„œλŠ”, λ…Έλ“œμ— gcd값을 μ €μž₯ν•˜λŠ” μ„Έκ·Έλ¨ΌνŠΈ 트리λ₯Ό μ‚¬μš©ν•˜λ©΄ λ©λ‹ˆλ‹€.
  • μœ„ λ¬Έμ œμ™€ 거의 같은 μ„Έκ·Έ + (νˆ¬ν¬μΈν„° or 이뢄탐색) λ¬Έμ œμž…λ‹ˆλ‹€. μ €λŠ” μœ„λ¬Έμ œλŠ” νˆ¬ν¬μΈν„°λ₯Ό, 이 λ¬Έμ œλŠ” 이뢄 탐색을 μΌμŠ΅λ‹ˆλ‹€.
  • νˆ¬ν¬μΈν„° μ‚¬μš©μ‹œ $O(n \log A)$, 이뢄탐색은 $O(n \log n \log A)$인데, 이뢄탐색도 λ„‰λ„‰ν•©λ‹ˆλ‹€. GCDλŠ” 생각보닀 λΉ¨λΌμ„œμš”.

CF R736 Div1 D1 - Gregor and the Odd Cows (Easy)

  • ν”½μ˜ 정리에 μ˜ν•˜λ©΄, λ³Όλ‘λ‹€κ°ν˜•μ˜ 넓이 $A$, 경계면에 μžˆλŠ” 격자점의 수 $B$, μ•ˆμͺ½μ— λ“€μ–΄μžˆλŠ” 격자점의 수 $C$에 λŒ€ν•΄ $A = B/2 + C - 1$ 이 μ„±λ¦½ν•©λ‹ˆλ‹€.
  • 즉, $A$ 와 $B/2$의 홀짝성이 κ°™λ‹€λ©΄ $C$κ°€ ν™€μˆ˜κ°€ 될 κ²ƒμž…λ‹ˆλ‹€.
  • κ³ λ₯Ό 수 μžˆλŠ” λͺ¨λ“  μ •μˆ˜μ μ΄ μ§μˆ˜μ’Œν‘œλ₯Ό κ°–λŠ” μƒν™©μ—μ„œ, $A$와 $B/2$의 홀짝성에 λŒ€ν•΄ 생각해 λ³΄κ² μŠ΅λ‹ˆλ‹€.
  • $A$, 즉 λ„“μ΄λŠ” 외적곡식을 톡해 ꡬ할 수 μžˆλŠ”λ°, μ–΄μ°¨ν”Ό mod 4 μœ„μ—μ„œ ꡬ할 κ²ƒμ΄λ―€λ‘œ μ›λž˜ 점의 μ’Œν‘œμ˜ mod 4 κ°’λ“€λ§Œ μ•Œμ•„λ„ μΆ©λΆ„ν•©λ‹ˆλ‹€.
  • $B$ λ₯Ό mod 4ν•œ 값을 μ•Œμ•„μ•Ό ν•˜λŠ”λ°, 잘 생각해 보면 $(x_1, y_1)$ μ—μ„œ $(x_2, y_2)$κΉŒμ§€ 선뢄을 이을 λ•Œ κ·Έ μœ„μ˜ μ •μˆ˜ 격자점의 κ°œμˆ˜λŠ” $\gcd(x_2 - x_1, y_2 - y_1)$ 이 4의 λ°°μˆ˜μΈμ§€ 여뢀에 따라 κ²°μ •λ©λ‹ˆλ‹€.
  • λ”°λΌμ„œ, μž„μ˜μ˜ μ„Έ 점 $p_i, p_j, p_k$에 λŒ€ν•΄, 각 점의 $x, y$ μ’Œν‘œμ˜ mod 4ν•œ λ‚˜λ¨Έμ§€κ°’λ§Œ μ•ˆλ‹€λ©΄, 이 점듀은 사싀 $A$와 $B/2$의 λΆ€ν˜Έ λ©΄μ—μ„œλŠ” λ˜‘κ°™μŠ΅λ‹ˆλ‹€.
  • 점을 λ„€κ°€μ§€λ‘œ κ΅¬λΆ„ν•˜κ³  ($x$와 $y$ μ’Œν‘œλ₯Ό 0 λ˜λŠ” 2둜), 클래슀 0-3의 점듀 쀑 3개λ₯Ό κ³ λ₯΄λŠ” 경우의 수 64가지λ₯Ό 생각해 μ€λ‹ˆλ‹€. 같은 클래슀의 점을 2개 κ³ λ₯Ό λ•Œ 경우의 μˆ˜λŠ” μ΄ν•­κ³„μˆ˜λ‘œ ꡬ해야 함을 κΈ°μ–΅ν•©μ‹œλ‹€.
  • μ½”λ“œλŠ” κ°„λ‹¨ν•˜μ§€λ§Œ Caseworkκ°€ μ’€ μžˆμŠ΅λ‹ˆλ‹€.
  • μ΄λ¬Έμ œλ„ λλ‚˜κΈ° 10뢄정도 전에 ACλ₯Ό λ°›μ•˜μŠ΅λ‹ˆλ‹€.

USACO 2018 February Platinum Problem 3 - Cow Gymnasts (BOJ 15744)

  • λ‚œμ΄λ„ Diamond 3.
  • 별도 ν¬μŠ€νŒ…ν•©λ‹ˆλ‹€. 링크