2015年2月28日 星期六

SRM651

又是cgy4ever的題目!他題目產量好多喔!不過這場不僅 Unrated ,而且賽中 也不能 submit 了有點難過,不過還是來寫寫我看完題目後想到了什麼吧。

作者的 short editorial

250 --- RobotOnMoon

題意:有一個 $n * m$ 地圖,有些格子被障礙物擋住了,有一個機器人並給你他初始位置,你可以設計一些指令讓他行走,若指令叫他往某個方向走,那個方向卻被障礙物擋住,那機器人不會移動。若執行那個指令會走出地圖外,那他就走出地圖外了 0.0 這機器人壞壞的,所以每個指令他都有可能會不小心 miss,現在我們要設計最長的上下左右的指令讓機器人無論 miss 了任何 subsequence 都一定不會走出地圖外。

數據範圍:小小的

tag : [ adhoc ]

- - - - - - - - - - - - - - -

看完題目後立刻想到若上下左右的某個方向直直走會被擋住,那就可以設計一個無限長的那個方向的指令。並且很容易相信這是僅有的答案為 -1 的 case,至於答案不是 -1 的 case 嘛...,其實我最剛開始猜的是上下左右最長的長度,可是看了一下 Sample,發現所有 Sample 都會對而且都是以這個做法來說很極端的 case... (要碼答案是 -1 要碼四個方向長度非 0 的只有至多一個方向)。就覺得答案一定不是這樣,在花幾秒後就想到正解而且發現可以輕易證明它了。不過說真的 ...這種題目若測資太強就太容易猜答案結果就不好玩了 XD


500 --- FoxConnection3

題意:平面座標上有 $n$ 個點,要上下左右移動它們,使得它們變為連通,並且這 $n$ 個點的移動步數和最小。每次移動都只能上下左右選其一移動一格,並且 always 不能有兩個點重疊。

數據範圍: $n \leq 6$,座標絕對值不超過 $10^9$。

tag:[ 枚舉 ] [ 數學 ]

- - - - - - - - - - - - - - -

類似題其實蠻常見的,最常見的就是在一維空間上做同樣的事,二維空間的類題我也立刻想到一題 HOJ84。不能重疊的什麼根本不用管這個條件,我以前思考過類似的事情了。最後再看到 $n$ 最大只有 $6$。顯然可以暴力枚舉所有連通圖的點塊的樣子。所以說這題我讀完題目瞬間就知道這麼做了,只是 code 似乎不夠好寫就是了。但 Petr 好厲害寫好快 0.0 到底怎麼辦到的 ...

1100 --- FoxAndSouvenir

題意:有 $n * m$ 的矩陣,有些位置有值有些沒有,有 $q$ 組詢問,第 $i$ 個詢問給你一個矩形,問你這個矩形內有幾種選數值的方法使得這些數值的總和為 $v_i$,答案 mod $10^9 + 9$

數據範圍: $1 \leq n, m \leq 50$, 矩陣內數值總和 $\leq 2500$。

tag:[ 傅立葉 ]

- - - - - - - - - - - - - - -

SRM 久違的傅立葉題...,但這題我看完第一個想到的是這題:Good Bye 2014 --- New Year Shopping,把它變成 2D版,所以我就一直往 D & Q 加 根號類算法下去想了 ...然後還自以為想到但後來發現某個地方複雜度搞錯了。

其實我應該要特別注意到 $10^9 + 9$ 這個數字的,向來當題目不 mod $10^9 + 7$,而是 mod $10^9 + 9$,通常都有特殊用意,所以看到這個數字就可以先往很數學的方向想少陷入些坑坑洞洞,不過我對傅立葉還不熟就是了,過高級的應用不太可能在一兩個小時內想到...。

- - - - - - - - - - - - - - -

下一場 SRM 要等到 3/9 了 ...,不要一直壞掉啦 OAQ