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

2015年2月24日 星期二

Codeforces Round #293 (Div. 2)

這場思考題目的時間非常稀少(根本是0),閱讀題目的時間比較多

應該算是比較簡單的 Div 2 的 Round

P.S. 一直寫下去後發現變成我在抱怨題目太簡單 XD

CF 293 Editorial 連結

Problem A --- Vitaly and Strings

題意:給兩個同長度的字串 $s$ 和 $t$ ,已知 $s$ 字典序小於 $t$,請給出一個長度和 $s$ 一樣的字串且字典序大於 $s$ 且字典序小於 $t$,無解請輸出 No such String

數據範圍:小小的

tag:[ 字典序 ]

= = = = = = = = = = = = = = = = = = = =

這題比我想像的還要多人寫假解,我寫完第三題後才看 score board 觀察有沒有題目可以 hack,並發現這題非常多人被 hack,但是我這個 room 已經被 hack 光了。

 我看到有一個人用python寫,直接把 s 和 t 轉成 26 進位的整數,再看看是否為相鄰兩個整數來判斷有沒有解 XD 若題目變成給兩個整數問他們之間有沒有整數應該是國小程度的東西?

Problem B --- Tanya and Postcard

題意:給兩個由大小寫字母構成的字串 $s$ 和 $t$,$t$ 的長度 $\geq s$。請從 $t$ 中取出一些字母重新排列組合成和 $s$ 長度一樣的字串,使得 1. 相同字母且相同大小寫的位置盡可能多 2. 若前者一樣多,再使相同字母但大小寫可以不同的位置盡量多。只要輸出兩種情況相同的字母數即可。

數據範圍:字串長度不超過 $2*10^5$

tag : [ greedy ]

= = = = = = = = = = = = = = = = = = = =

直覺想法就是有完全一樣的字母就先擺上去,都擺完後,再繼續把大小寫不一樣的相同字母擺上去,剩下的就隨便亂擺。很巧的這一定是對的。

Problem C --- Anya and Smartphone

題意:有個手機有 $n$ 個 icon,每個 page 有 $k$ 個 icon,若要使用第 $x$ page 的 icon,就必須滑 $x$ 次,每次滑完後,該 icon 的位置就會和位置在他前面的相鄰 icon 互換 (若沒有比他此 icon 則位置維持原樣),給原本所有 icon 的位置,以及一序列的操作,問總工必須滑幾次?

數據範圍:所有數字不超過 $10^5$

tag:[ 模擬 ]

= = = = = = = = = = = = = = = = = = = =

我非常懷疑這題放在第三題只是因為他比較難讀懂 ...?有沒有人可以告訴我這題的特別要注意的地方在哪,有哪裡可以想歪?還是說交換位置的實作對初學者來說可能有困難?(嗯...若是第一次使用陣列大概有困難吧?)

Problem D --- Ilya and Escalator

題意:有 $n$ 個人在排隊等電梯,每一秒有 $p$ 的機率有一個人進去,另外 $1-p$ 的機率會沒有動靜,問 $t$ 秒後進去電梯裡的人數的期望值?(電梯容量無限大,進去的人就永遠在裡面)

數據範圍:$1 \leq n, t \leq 2,000$, $0 \leq p \leq 1$

tag:[ DP ]

= = = = = = = = = = = = = = = = = = = =

DP狀態很直覺,現在經過幾秒以及進去了多少人,轉移就如題目所述只有兩種。這提竟然值兩千分 =口=,我覺得是 rating 爆漲的現在,使得 Div. 2 的難度變更低了...?

Problem E --- Arthur and Questions

題意:給 $n$ 個數的數列,有些數尚未決定,用問號來表示,現在要把問號都填入數字,使得每連續 $k$ 個數的和所形成的數列為嚴格遞增數列,並且所有數的絕對值總和最小,要輸出解,若多組解,輸出任一組皆可。

數據範圍:$1 \leq k \leq n \leq 10^5$

tag:[ 數學 ] [ greedy ]

= = = = = = = = = = = = = = = = = = = =

把不等式列出來就會發現,嚴格數列的那個條件其實等價於,在原數列中取出任意間隔恰為 $k$ 的子數列,也都為嚴格遞增。把每個子序列分開作後,我們就把問題簡化為:給一個有些位置值還位給定的數列,請給定值使得絕對值總和最小,至於要怎麼給值呢?愈靠近零總是愈好吧?剩下的就是從貪心的角度切入加上一點點數學證明了。

Problem F --- Pasha and Pipe

題意:給一個 $n * m$的盤面,要在上面放一條至多轉兩次九十度的管子,並且不能碰到某些格子(詳細條件請看原題),問有多少種可能

數據範圍:$1 \leq n, m \leq 2,000$

tag:[ dp ]

= = = = = = = = = = = = = = = = = = = =
我讀完題目的直覺就是不轉彎,轉一次彎,轉兩次彎這三種情況分開討論。其中只有轉兩次彎的情況要稍為複雜一點點的 dp (但其實也只是很常見的手法)。

雖然這樣說 ...,但轉兩次彎的情況我寫爆了 XD。把他想的太簡單了,沒有去考慮轉兩次彎的中間那部分有沒有通過不可以走個格子 ...

2015年2月2日 星期一

Codeforces Round #290 (Div. 1)

Codeforces 的比賽其實幾乎都有詳細的題解了,不足的部分通常也都會在 comment 裡由其他人補充,只可惜目前的Codeforces comment裡的雜訊時在太多了...,有礙於大家尋找演算法相關的東西。應該要建議Codeforces對每則訊息除了正評或負評的選項外,多一個"你覺得這則訊息是否和演算法或解題相關"的選項,然後再加個 filter 讓想知道演算法相關的 comment 的人能只看到這些訊息。

恩...我講這些是要說... 我不放棄寫那麼多和 Editorial 重複的內容了,除非我能寫的比 Editorial 還早,不然我就只大略的講一下我的心得(?),否則這個網誌根本意圖使大家英文變差 XD

CF 290 Editorial 連結

Problem --- A Fox and Name

題意:給 $n$ 個字串請決定小寫字母的大小關係使得所有字串會恰好是由小到大

數據範圍:小小的

tag:[ 拓樸排序 ]

= = = = = = = = = = = = = = = = = = = = =

一模一樣的題目我一定在其他地方看過...,雖然如此但我還是寫炸了 XD。

介紹一下 scoreboard debug 法 XD --- 偶爾看看 score board 是否有哪題有些人大量challenge成功,如果有的話代表那題有個潛在的你很可能犯的bug。 雖然我曾經覺得這種 debug 法很顯而易見,不過很多人不知道。

我寫完 pB 後看了看 scoreboard,發現有些人 pA challenge 成功很多份 code。我就先回來重新想想 pA 我是否漏掉什麼 ...,結果就發現如下測資我會壞掉!

2
hacked
hack

於是我就趕緊加個幾行若遇到這樣的測資直接輸出Impossible,並重 submit 且 lock 住。這時我犯了一個錯誤...,我沒有重新 compile 並測這樣的測資,要不然就會發現我輸出Impossible後並沒有return...。而且我們這個 room 犯這個 bug 的人比我想像中的還要少好多 0.0,我只靠了 challenge 拿到 150 而已,浪費好多時間,就結論來說是賠的...。

介紹一個亂來的拓墣排序方法:

先用 floyed warshall 找出所有元素的大小關係,之後按照比該元素大的元素個數由小到大排序。這是我在這場比賽內寫的高複雜度的拓墣排序法 XD

Problem B --- Fox And Jump


題意:在某個遊戲,若你希望你往後能跳長度為 $l_i$ 的距離(向左或右皆可),就必須花費 $c_i$ 元,請問至少要花多少錢在能跳到所有距離為整數的位置。( $0 \le i \lt n$)

數據範圍: $1 \le l_i \le 10^9$, $ 1 \le c_i \le 10^5$,$1 \le n \le 300$

tag:[數學][數論]

= = = = = = = = = = = = = = = = = = = = =

對數論熟悉的人應該能立刻知道為了滿足題目條件就是選一些 $l_i$ 使得最大公因數是 $1$ 。然後解題經驗豐富的人應該都會知道有不少題目都會利用因數個數其實並不多這個性質。實際上不超過 $10^9$ 的數因數個數最多的數是931170240,只有1344個因數。有了這兩個適時合就可以得到一個計算量至多約 300*300*1344的 dp 方法了。

雖然我看完題目就知道怎麼做,可是不知道怎麼搞的我寫了個比較複雜的求所有因數的方法...,可是實際上只要從 $1$ ~ $\sqrt{n}$ 去測試看看能否整除 $n$ 就行了@@,我因此花了比就久的時間寫它 ...

Problem C --- Fox And Dinner

題意:有 $n$ 之狐狸,每隻狐狸的年紀至少為 $2$,要讓分派它們坐在一些圓桌,每張圓桌至少坐三人,並且任相鄰的兩人年齡加起來必須是質數。若有解請輸出解。

數據範圍: $3 \le n \le 200$

tag:[ flow ][二分圗匹配]

= = = = = = = = = = = = = = = = = = = = =

看完題目立刻就知道它是某種經典 flow 題了,還記得六年前在台大培訓班時坐過某個題目如下:

給一個有向圗,請找出所有一些沒有共點的 cycle 使得每個點都恰在一個 cycle裡。

但若是第一次看到這類的題目應該會覺得很巧妙 ~

Problem D --- Fox And Travelling

題意:有個 $n$ 個點的 graph,每次可以移除一個當前 degree 不超過 $1$ 的點,請問若要移除 $k$ 個點,有多少種不同順序?$k$ 從 $0$ 至 $n$ 都要回答。

數據範圍: $1 \le n \le 100$

tag:[ 數學 ][ dp ][ tree dp ]

= = = = = = = = = = = = = = = = = = = = =

這題是以下某個常見題型的強化版:

給一個 rooted tree,每次可以拔當前的某個葉子,請問把所有點都拔光有多少種拔法?

若是這個問題其實是可以做到 O($n$) 的,但這題 $n$ 只有 $100。

我大概想了五分鐘吧,這兩個問題的差別有二:1. 這題不一定要把全部點拔完。 2. 這題也要考慮無根樹。

1.比較好解決,就dp時狀態多一點就好了,是典型的O($n^2$) tree dp結構。
2.我不久就連想到幾個小時前的 SRM D1 Hard 的其中一個概念:同一個無根樹的拔法我們可以算很多次!(把各個點分別當成root去考慮)但所有拔 $k$ 個點的拔法會算到一樣多次!哈哈在連續兩場比賽看到了一樣概念的題目。

只可惜我在寫產生 tree 的部分寫爛了...,有好多 bug,所以沒能在賽中AC。

Editorial 裡 好像還給了另一種方法。

Problem E --- Fox And Polygon

題意:任意凸多邊形都可以切成很多三角形,給兩種切法,請藉由以下操作,把第一種切法轉換成第二種切法:每次可把兩共用邊的三角形,考慮它們所形成的四邊形,改成用另外一種切成兩個三角形的方法(切線變成另一個對角線)

數據範圍:邊長至多 $1000$,給出的操作數不超過$20000$

tag:[ 平衡數rotated ] [ 數量分析 ]
= = = = = = = = = = = = = = = = = = = = =

我比賽中也有瞄了這題,可是我覺得比起 E 我更擅長 D,但其實這題存在某個好寫多的解法...

官方解是把每種切法對應到一個 rooted tree,並把每個操作想像成平衡數的 rotated,於是就可以使用各種平衡數的做法去解這題。

但這不是我所謂的好寫好想的做法。

請參考以下連結:Egor's comment or TooSimple's code

我不想翻譯了 >_<,我自己看了code大概三分鐘內就了解做法了。

SRM648

這場 SRM 雖然我拿了 -25 分...但還是照寫題解XD
都怪我一剛開始 850 想歪,並且剩 25 分鐘時才去開 550,剩一分多鐘才把 code 寫完而且沒能de 到某個蠢 bug @@

250 --- AB

題意:請構造出一個由 A 和 B 組成長度為 $L$ 的字串,使得 A 在 B 的左邊的組數恰好為 $K$,沒有的這樣的字串存在則回傳空字串

數據範圍:小小的

tag:[ greedy ]

= = = = = = = = = = = = = =

若 A 的數量固定,可以想像所有 A 在所有 B 的左邊時組數會最多,並且數量為 $k*(L-k)$ ($k$ 為 A 的數量)。故組數最多的情況發生在 $k = L/2$。

接著我們可以發現,若存在某個A在某個B的左邊相鄰位置,我們把這兩個相鄰的 AB 交換後,可使 A 在 B 的左邊的組數減 $1$,並且若當前組數不為 0,總是可以找到這樣的相鄰的 AB。

有以上結論,應該就能解出這題了。

550 --- KitayutaMart

題意:一個商店裡有 $K$ 種商品,你所買的第 $k$ 個第 $i$ 種商品要花費 $i \times 2^{k-1}$ 元,你總共要買 $N$ 個商品,希望最貴的一項商品價錢最少,請輸出此價錢 mod $10^9 + 7$

數據範圍: $1 \le N, K \le 10^9$

tag:[ 數學 ][ 二分搜 ]

= = = = = = = = = = = = = =

我的思考邏輯如下:


首先注意到,若某項商品買了比另外一項商品多了至少30個則一定比較貴,所以買的任兩種商品的數量差一定不超過 $30$。

於是我們就可以估計出,最貴的那項商品所買的商品數範圍,一定落在 [$N/K - 100$,N/K + 100] 之間 (對不起我的腦帶無法快速算出更精確的範圍,就隨便給一個一定會對的區間...)。

接著我想對所有可能的 $k$ 試試看,最貴的商品是否可能是第 $k$ 個某商品,由於同種商品的第 $k$ 個的價錢是嚴格遞增的,自然而然的就想到要使用二分搜,於是,在二分搜時我們要判斷:價錢不超過第 $k$ 個第 $i$ 種商品的有幾個,我們能因此找到最小的 $x$ 滿足價錢不超過第 $k$ 個第 $x$ 種商品的個數為 $N$ 個以上,接著我們再計算價錢恰巧和第 $k$ 個第 $x$ 種商品一樣的有幾個,就能知道有第 $N$ 個商品的價錢是否和第 $k$ 個第 $x$ 種商品一樣。

我們剩下兩個問題要解決:1.價錢不超過第 $k$ 個第 $i$ 種商品的有幾個  和 2.價錢恰巧和第 $k$ 個第 $x$ 種商品一樣的有幾個。

第二個問題應該是比較簡單的。我們知道所有的整數數對 $(a, b)$ 若 $a$ 為正且 $b$ 介於 $1$ 和 $k$ 之間,則恰對應到一個價錢是 $a * 2^{b-1}$ 的商品,所以我們只要枚舉所有可能的 $i$ 使得 $(x*2^i, k-i+1)$ 仍是合法的數對,就能知道第二個問題的答案了,數量一定不超過 $30$ 個。

而知道了第二個問題的答案,離解第一個問題也不遠了,因為同樣是第 $k$ 個同種商品,且價錢不超過第 $k$ 個第 $i$ 種商品的個數就是 $i$。於是用類似解第二個問題的方法也可解第一個問題。

850 --- Fragile

題意:有編號的 $N$ 個點所形成的無向圖,有多少種橋的個數是 $K$?所謂的橋是指移除後圖的連通塊個數會增加的邊。

數據範圍:小小的

tag:[ 數學 ][ dp ]

= = = = = = = = = = = = = =

這種題目還蠻常見的,各種各式各樣的圗的技術問題,舉例來說,也有問題是問你 $N$ 個點的樹 (tree) 有幾種?或問你 $N$ 個點的連通圖有幾種?甚至問你 $N$ 個點的強連通有向圖有幾種
之前有在網路上看到一篇投影片是在介紹各種類似的問題,不過我一時間找不到...

這題由於數據範為小小的,所以你使用高複雜度的 dp 都是可解的,大不了花個十幾分鐘跑完程式後把結果印在 code 裡(例如 Petr 的 code)。我自己賽後想到的式O($N^5$)

不過根據我對 writer 的 code的考據,他使用了最高為O($N^4$)的時間複雜度作了總計三次 dp。

(以下所謂的圗都是有編號的 (labeled))

第一次:求出 $N$ 個點的所有點都連通的圖有幾種。時間複雜度為O($N^2$)。

$dp1[i]$ 紀錄點數為 $i$ 的連通塗有幾種。
首先我們知道 N 個點的圗共有 $2^{N*(N-1)/2}$ 種,意即每個邊可選或不選。而若能扣掉部連通的圗的個數,就可以求出連通的圗的個數了。所以我們就枚舉和邊號 $1$ 的點連通的點數,從 $1$ 枚舉到 $N-1$,個數分別是 $dp1[i] * 2^{(N-i)*(N-i-1)/2} * C(N-1, i-1)$

第二次:求出 $N$ 個點的所有點都連通且有 $K$ 個橋的圗有幾種。O($N^4$)。

$dp2[i][j]$ 紀錄 $i$ 個點 $j$ 個橋的種類數。
$j = 0$ 的時,我們一樣試著用 $dp1[i]$ 去扣掉所有 $j$ 非 $0$ 的值。
對於 $j$ 不為 $0$ 的情形,我們使用一種 counting 的技巧 --- 讓同一張圖重複算好多次,但被算到的次數是一樣的,就可以把結果除以同張圖被算到的次數來得到答案。
實際上就是,我們計算編號 $x$ 和編號 $y$ 的點中間有橋的個數,若此座橋移除後,和點 $x$ 連通的點數有 $u$  個且含有 $r$ 座橋,則和點 $y$ 連通的點有就有 $i-u$ 個以及有 $j-r-1$ 座橋,這是我們可以 $O($1$)$求得的東西而且不管 $x$ 和 $y$ 是選哪兩個點結果都一樣,最終同一個圖都恰被算到 $j$ 次(因為 $j$ 座橋恰被枚舉到一次)。把我上面所述的綜合起來,會發現是個 O($N^4$) 的式子。

第三次:求出 $N$ 個點恰 $K$ 個橋的圗有幾種(即最終答案)。 O($N^4$)。

已經有了第二次dp的結果,這部分應該就容易多了,我就不解釋了。