π λ¬Έμ
koosagaμ cubeloverκ° "νλ²"λ₯Ό νκ³ μλ€. νλ²λ λ κ²μμ κ·μΉμ μΆκ°ν κ²μμ΄λ€. νλ²λ λμ 차곑 차곑 μλ‘ μμμ¬λ¦° λ λλ―Έ kκ°λ₯Ό μ΄μ©νλ€. κ°κ°μ λ λλ―Έμλ ν κ° μ΄μμ λμ΄ μλ€. λ μ¬λμ μλ‘ ν΄μ λ²κ°μκ°λ©΄μ νλ²λ₯Ό μ§ννλ€. κ° μ¬λμ ν΄μ΄ λλ©΄, λ λλ―Έ νλλ₯Ό μ νν΄ λμ μ κ±°νλ€. μ κ±°ν λμ κ°μλ νΌλ³΄λμΉ μμ¬μΌ νλ€. μ 체 λ λλ―Έμμ λ§μ§λ§ λμ μ κ±°νλ μ¬λμ΄ κ²μμ μ΄κΈ°κ² λλ€. κ²μμ koosagaκ° λ¨Όμ μμνλ€. λ μ¬λμ΄ μ΅μ μ λ°©λ²μΌλ‘ κ²μμ μ§ννμ λ, μ΄κΈ°λ μ¬λμ μΆλ ₯νλ€.
πμ λ ₯
첫째 μ€μ λ λλ―Έμ κ°μ $N$ $(1 ≤ N ≤ 10^5)$μ΄ μ£Όμ΄μ§λ€. λμ§Έ μ€μ κ° λ λλ―Έμ μμ¬μλ λμ κ°μ $P_i$ $(1 ≤ P_i ≤ 3×10^6)$κ° μ£Όμ΄μ§λ€.
πμΆλ ₯
koosagaκ° μ΄κΈ°λ κ²½μ°μλ "koosaga"λ₯Ό, cubeloverκ° μ΄κΈ°λ κ²½μ°μλ "cubelover"λ₯Ό μΆλ ₯νλ€.
π λ¬Έμ νμ΄
μ€νλΌκ·Έ κ·Έλ°λ λ¬Έμ μλ€. (λμ€μ μκ°μ΄ λλ€λ©΄ μ€νλΌκ·Έ κ·Έλ°λ κΈλ μ¨λ³΄λ κ±Έλ‘,,,)
μμΌλ‘ μ±μΉ 20κΉμ§μ κ·Έλ°λ λλ²λ₯Ό κ³μ°νμ λ, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5 μ΄ λ°λ³΅λλ κ·μΉμ΄ λ³΄μ¬ μ£ΌκΈ°κ° 10μΈ κ·Έλ°λ λλ²μΈμ€ μμλ€. νμ§λ§ μ΄ κ·μΉμ 40 μ΄μλΆν° κΉ¨μ‘λ€. π
κ²°κ΅ Pμ μ΅λκ°μΈ $3 * 10 ^ 6$ κΉμ§μ λͺ¨λ κ·Έλ°λ λλ²λ₯Ό μ°Ύκ³ xor ν©μ μ·¨νλ λ¬Έμ μλ€. μ΄κ² μ΄ λ¬Έμ μ ν΅μ¬μΈλ°, κ·Έλ°λ λλ²λ₯Ό μ°ΎκΈ° μν΄μ mex ν¨μλ₯Ό λ릴 λ μ΄κ²μ κ² ν΄λ³΄λ©΄μ μ€ν μλλ₯Ό μ€μ΄κΈ° μν κ³Όμ μ λ¨κ²¨λ³΄κ³ μ νλ€.
244ms
μ²μμΌλ‘ μ λ΅ νμ μ λ°μ μ½λμ΄λ€.
μ£Όμ λΆλΆλ§ μ΄ν΄λ³΄μλ©΄, μ°μ μ νλ‘κ·Έλ¨μΌλ‘ λλ €λ³΄μμ λ κ·Έλ°λ μ«μκ° μ΅λ 15κΉμ§λΌλ κ²μ νμ νλ€. νμμλ μ€λ³΅ μ κ±°λ₯Ό μν΄ κ·Έλ°λ λλ²λ₯Ό μ μ₯ν λ HashSetμ μ¬μ©νμλλ°, μ¬κΈ°μλ κΈΈμ΄16μ§λ¦¬ bool λ°°μ΄μ λ§λ€μ΄μ νμΈνλ κ²μ΄ λ ν¨μ¨μ μ΄λΌκ³ νλ¨μ νλ€.
216 ms
첫 μ λ΅μ½λλ³΄λ€ 30ms κ° μ€μλλ°, λ μ½λμ μ°¨μ΄μ μ μ μ λ³μλ‘ μ μΈλ FIBOλ₯Ό λ‘컬 λ³μλ‘ λ³κ²½ν κ²μ΄λ€. κ·Έλ¬λλ μμ κ² κ°μΌλ©΄μλ ν° 30msκ° μ€μλ€.
112 ms
κ±°μ λλ°° κ°κΉμ΄ μ€μλ€. μ΄λλ λ°°μ΄μ μ μ₯νλ λ°©λ²μ΄ μλ, λΉνΈλ§μ€νΉμ μ¬μ©ν΄ mex ν¨μλ₯Ό λ체νλ€. μμ λ§νλ€μνΌ κ·Έλ°λ λλ²κ° μ΅λ 15λ₯Ό λμ§ μλλ€. κ·Έλ κΈ° λλ¬Έμ κ΅³μ΄ 16μ§λ¦¬μ bool λ°°μ΄μ μ μΈνλ κ²μ΄ μλ 16λΉνΈμ μ«μ νλλ‘λ λͺ¨λ κ²μ ννν μ μλ€! (κ΅μ₯ν μ°κ»νμ§ μλνκ°)
λΉνΈλ§μ€νΉμ κ°λ¨νκ² μ€λͺ ν΄λ³΄μλ©΄, bool λ‘ μ μΈνμ λλ μλ₯Ό λ€μ΄ visited[3] κ° true μΈμ§ falseμΈμ§ νλ¨μ ν΄μ ν΄λΉ κ°μ΄ μ‘΄μ¬νλμ§ νμ νλ€. κ·Έλ°λ° λΉνΈλ§μ€νΉμ μ¬μ©νλ€λ©΄ λ°°μ΄μ μΈλ±μ€λ‘ μ κ·Όνλ κ²μ΄ μλλΌ μ«μμ νΉμ λΉνΈκ° 0μΈμ§ 1μΈμ§ νλ¨ νλ κ²μ΄λ€.
μ΄λλ λ°λ‘ mex ν¨μλ₯Ό λ§λ€μ§ μκ³ , λ¬μ€νΈμ trailing_ones ν¨μλ₯Ό μ¬μ©νμλ€. trailing_ones ν¨μλ κ°μ₯ μ€λ₯Έμͺ½(least significant bit, LSB)λΆν° μ°μλ 1μ κ°μλ₯Ό λ°ννλ ν¨μλ€.
68ms
λΉνΈλ§μ€νΉ μ μ©μν¨ κ²μ λ©μΆμ§ μκ³ ν λ° λ λμκ° λλΉλκ³ μλ λΉνΈλ₯Ό μ μ½νμλ€.
μ¬λ¬ μ°¨λ‘ μΈκΈνκ³ μλλ° κ·Έλ°λ μλ μ΅λ 15μ΄λ€. κ·Έλμ κ΅³μ΄ u32 (32λΉνΈ μμ΄ μλ μ μ) λ₯Ό μ¬μ©ν νμκ° μκ³ u8(8λΉνΈ μμ΄ μλ μ μ)λ₯Ό μ¬μ©ν΄λ μΆ©λΆνλ€. κ·Έλμ μ¬μ©νλ μλ£νμ λ³κ²½ν΄μ£Όμλλ μκ°μ΄ 50ms μ λ κ°μνμλ€.
π» μ΅μ’ μ½λ
π μνμ°©μ€
λ§ν μ¬λ μ 체μμλ μΌλ±μ λ¨Ήκ³ μλ€.π (2025.3.30 κΈ°μ€)
π λ¬Έμ λ§ν¬ νλ²
'Problem Solving > λ°±μ€' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[λ°±μ€] 5015λ²: ls (1) | 2024.11.16 |
---|---|
[λ°±μ€] 15944λ²: μ±κ³΅ (0) | 2024.11.07 |
[λ°±μ€] 28357λ²: μ¬ν λλ μ£ΌκΈ° (1) | 2023.10.08 |
[λ°±μ€] 5942λ²: Big Macs Around the World (0) | 2023.09.18 |
[λ°±μ€] 20560λ²: λ§μ§ νλ°© (1) | 2023.09.01 |