HKG Time - 1915 to 2415
是 CTLi 強勢歸來的第二場 Team Training
8條題目 全清！
其它隊伍亦做出與 on site champion 同樣題數(5+)的成績
雖然今次做的同樣是日本 Site
全套題目仍是「暴力、硬做」的風格
但由於這已經是 8 年前的題目
就現今技術而言，難度不高
算法都很直接
亦不需要花很長時間 plan code （ 題B 及 題C 除外）
這次嘛... 本人開始的 題A 卡了相當多時間
吃了一下 TLE 及 一下 WA ...
實在太太太太抱歉...
還好在其後的 題C 及 題H 能分別 1A
不然真的非常拖累整體罰時...
題A - ICPC 2565 Calling Extraterrestrial Intelligence Again
解(Kn)： Prime Sieve + 二分
1st attempt：線性掃描每個 Prime number，定之為 height
再二分查找 最大的 height ── 結果是 TLE
這個很不明白... 明明複雜度只是 O(M lg M) per query... (M = # Prime's)
2nd attempt：後來降低了 Prime 的 upper bound ── WA
才發現上界想錯了... 最後用很緊的 upper bound = 100,000/2 ── 3.XX sec AC
題B - ICPC 2566 Equals are Equals
解1(Joe)：(Recursive) Parsing、就是做！
是 Training 期間最後做的一題
這題甚有日本風格...
還好多項式項數不多，可以稍為暴力地做
憑藉 Joe Parsing 熟練的手術
非常快地 Code 好，可惜 WA
在 Training 末段我們三人一起 Debug
不算太辛苦地 AC 了
解2(Leo)：Randomized Algorithm - PIT (Polynomial Identity Testing)
一個有名的算法：
隨機生成一個大數，分別代入兩條多項式，計算函數值是否相等
False ⇒ 2條多項式不恒等
True ⇒ (有極之大的機率) 2條多項式不恒等
為防止 Overflow，implement 時可以用 mod arithmetic 除代 大數 arithmetic
此算法較算法1簡單，但仍需要 Parsing 的步驟
題C - ICPC 2567 GIGA Universe Cup
解(Kn)：暴力窮舉、Data Processing、Recursion
亦是甚具日本風格的一題
數據規模小，明顯是暴力做
不過這條題目單單看題花了相當時間...
題目最難的地方在於 Sorting 的部份...
要動用 Recursion
Coding 過程犯了數個低級錯誤（variable打錯）
最後一個錯誤非常低級 ── 看錯題... 以為只第1名出線！
（Gagguy說，他當初也以為是）
全賴 CTLi 指正...
第一個 Submission... WA?!
非常 Frustrated...
第一個反應是到 Live Archive 的網頁...
果然... 沒有 Special Judge...
把輸出精度調節至 6個小數位便 AC
題D - ICPC 2568 Life Line
解(CTLi)：？
CTLi 聲稱 10分鐘便能 KO 的題目
卻搞了很久
最後的 bug 是 Macro 打錯：漏了括號...
被 Joe 調教一番後，似乎開始有所覺悟...
題E - ICPC 2569 Map of Ninja House
解(CTLi)：？
？
題F - ICPC 2570 Shredding Company
解(Joe)：？
？
題G - ICPC 2571 True Liars
解(Joe)：DP
沒有參與討論
聽說是簡單題？
但需要 Backtracking
題H - ICPC 2572 True Liars
解(Kn + CTLi)：2D Geometry、Circle/Circle Intersection、Point in Circle Query
Joe 提出算法大方向
CTLi refine 算法，指出精度要小心處理... epsilon = 1e-15
Kn 幫忙處理精度，用最小誤差的方法 Code
而最後一兩個統計用途的 For-loop 由 CTLi 操刀
Coding → Compile → 本機 Compile Error (忘了 #include <cmath>) → Pass Sample → Submit → Accepted
相當漂亮的 1A ！
檢討：
- 就過往幾次 Training，看來準繩是一大問題...
例如 我主攻的 Simulation
題目往往會給很多細節規則等等
有時候 一兩條 Rule 的優先順序
會直接影響能否替 coding 進行簡化...
嗯... 要判斷那些時候值得投放少部份時間跟隊友討論 - 我和 Joe 在今次分別有看錯／漏題目...
題目 (尤其是長題目) 還是最好能有 ≥2 人閱覽...
沒有留言:
發佈留言