Codeforces Round #159 (Div. 2) 題解筆記

比賽題目速解

A 題：題意閱讀困難，直接從樣本推導邏輯

屬於「觀察樣本逆向工程」類型，比賽中常見技巧。

B 題：直接輸出

無需計算，根據規律直接列印答案。

C 題：極角排序 + 最大相鄰角度

• 給定 n 條射線（向量），求能涵蓋所有射線的最小扇形角度。
• 解法：計算所有向量極角 → 排序 → 求相鄰角度差（含首尾跨 360°）→ 答案 = 360 - max_gap。
• 注意精度：用 atan2 求角度，double 足夠。

D 題：遞推差分 + 括號化

• 序列 a₁, a₂, ..., aₙ，操作：相鄰兩數相減（大減小），重複至剩一數。
• 關鍵觀察：最後一項減倒數第二項 ≤ 倒數第二項；繼續遞推，等價於不斷加括號，最後從左往右消括號。
• 證明大綱：設最後三項 a, a+d₁, a+d₁+d₂，則 d₂ ≤ a+d₁。若 d₂ ≥ a 則 0 ≤ d₂-a ≤ d₁ ≤ a；否則 0 ≤ a-d₂ ≤ a。大減小保證結果在 [0, a] 區間，符合條件。

E 題：未完成（標記為 gaoing）

比賽心得

• 幾何題（C）掌握極角排序模板至關重要。
• 構造/證明題（D）需從小規模案例發現不變量，再嚴謹證明。
• 讀題困難時，樣本是最佳說明書（A）。