HKG Time - 0000 to 0200
終於... 在一次 individual contest 做到少人完成的難題目了...!
- 題目
- 排名 (12th)
- 官方 Analysis
題解概要：
Problem A - 簡單要麼戳式，要麼直接建圖
想了好一陣子，最終決定建圖
Problem B - 簡單 + 閱讀理解
題目有點1999，閱讀了數分鐘終於明白
但過了sample 後連續 WA，繼而心灰
悲劇地卡了40分鐘... 才發現
原因：題目要求 output 單一個數值 - Query之和，而不是列出逐個 Query
Problem C - Counting
從數據規模上知道不能直接DP
腦中出現第一個念頭：
先暴力DP列出頭幾項，再在 Google/OEIS 找 closed form
但愚認為這樣便失掉做題的意義了... 所以堅持尋找 pattern / 推導公式
最終發現把某個 DP 表格打斜看其實就是 Pascal Triangle
(順帶一提，這題比 Problem B 還要早 Pass Pretest...)
(DP[N][K] := 長度為 N 並以 K 為結尾的 Type 1) 數列個數)
Problem D - Ad-hoc(?)、Counting/Probability (?)
讀完題目便很敏銳地想起 Linearity of Expectation
把 x- 和 y-距離分開考慮
靈感來源：在前幾天的 SRM 494 的 500 被殺了 (*)
能通過 Sample 以及 Pre-Test 的 Trial 1：
兩兩 entry 的 y-距離 等於 | y_i - y_j |
── 除了位於同一行，而被 obstacle 阻隔的 entry pair [紅→綠]
.......
...X...
.......
y-距離要額外+2
但再畫了多幾個 sample 發現這是不對的，例如：
.X.....
...X...
.....X.
如是者勉強構作了 Trial 2
某些 entry對的 x- / y- 距離依舊 額外 +2
(參考題目對 obstacle 的額外 constraint)
最後實踐用了 swap row/column 及 reflection 進行簡化
Pre-Test 很陰人呀...
以今場表現而言，能解決四題差不多是極限了
(其實再給我多3個小時大概還是不能解決E)
最後半小時沒事幹便 hack 人...
叉人的方法依舊是
有點無聊...
(*) 在 SRM 494 我悲劇地 0分了...
難度洞悉出 500 的 observation
卻沒能把 DP 寫出
為了 individual contest...
WF 以後要把個人修煉重點放在 DP 上.....!
沒有留言:
發佈留言