NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » 一般 » 綜合討論區
 台北市資訊學科能力競賽 結束 !

作者 主題: 台北市資訊學科能力競賽 結束 !  (閱讀 7550 次)

lini

  • 高級會員
  • ****
  • 文章數: 101
    • 檢視個人資料
台北市資訊學科能力競賽 結束 !
« 於: 十一月 19, 2010, 06:35:53 pm »

分析一下 可能 應該是這樣 ..

pA(chain) : DP , TIOJ有類似題(更難)
pB(jack) : brute force
pC(gift) : DP(knapsack problem)
pD(Meteor) : Simulation(模擬) + 數學
pE(ecology) : DP? DFS+cut? BFS? Greedy?

難度排序(難->易) : pE > pD > pA > pC > pB

我的成績是 . .
pA : 25/25
pB : 25/25
pC : 20/25 (一堆人跟我一樣第3筆WA)
pD : 15/25 (寫個假解撈撈撈, 陣列開太小第5筆RE)
pE : 0/25 (連暴搜都沒什麼想法 .. ->我好弱)

筆試不知道成績
應該還可以

總排名 : 14/117 (三等)


北市賽真可怕 ..

一等全部建中 (全場 WOW~~~)


坐在建中那群附近 ..

有人說 :「現在已經8個100以上了」

聽到整個很囧 ...


su_horng
你已經保送了 別來了辣 =  =
« 上次編輯: 十一月 19, 2010, 10:20:00 pm 由 lini »
記錄

phat

  • 新手
  • *
  • 文章數: 18
    • 檢視個人資料
回覆: 台北市資訊學科能力競賽 結束 !
« 回覆 #1 於: 十一月 20, 2010, 03:51:50 pm »

pE是一類很標準的線性規劃題目。

基本上是屬於大學課程的東西,只是一種防破台而已...


如果有想要瞭解該怎麼去解的可以參考大陸的國家集訓隊論文:

李宇骞《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》


我自己是還沒開始閱讀啦,而且這類問題在高中競賽應該是屬於這次出現以後就再也不會碰到的題目。


===

97北市p1 cookie也是一類求整數解的線性規劃,

是屬於一類NPC問題,但是該題測試資料給定範圍很小所以可以進行枚舉。


===

我覺得此次比較嚴重的問題是測試資料普遍不強,

前四題前兩筆輸入皆為範例測資、像第四題印象中最大一筆才幾百...題目敘述過度膨脹,

第三題輸出答案相差皆很小,似乎是完全亂數產生之測資,而且第三筆似乎官方輸出有誤。

第五題竟然有兩筆標準答案為-1,讓不少puts("-1");者受惠...


記錄

lini

  • 高級會員
  • ****
  • 文章數: 101
    • 檢視個人資料
回覆: 台北市資訊學科能力競賽 結束 !
« 回覆 #2 於: 十一月 20, 2010, 06:57:37 pm »

啊 失誤 = =

第五題讀完敘述就沒看下去了 . .

少了10分 . .


第4題
2000 x 2000

當下有shock到
整題就是卡在建築物可以400W

我自己是這樣code
假設觀測點高度 100 89
那我會去算隕石高度為 80 70 60 50 40 30 20 10 0 在哪格上
讀進來在判斷隕石當時的高度會不會撞到那棟建築



第三題
第三筆不是聽說有人對 ?
(還是剛好跟出題的一樣code錯 XD)
« 上次編輯: 十一月 20, 2010, 07:07:06 pm 由 lini »
記錄

jurrasickill

  • 新手
  • *
  • 文章數: 13
    • 檢視個人資料
回覆: 台北市資訊學科能力競賽 結束 !
« 回覆 #3 於: 十一月 20, 2010, 09:17:08 pm »

第五題明顯是線性規劃......一出考場很多人就在講了阿Q
如果真的只是DP或DFS+cut或BFS或Greedy怎麼可能沒人對= ="
2筆-1我覺得還頗瞎...雖然有撈到就是orz

第四題我不知道2000*2000=400萬有啥關係@@陣列開的下阿...
我是直接算兩個觀測點的距離以及x,y,z的改變量,兩個相除
代表每個單位移動~接下來就移動它拉~反正距離最多也才2000...不會TLE~
可是不要一次動10,就一次1單位1單位動,看那格的z有沒有大於現在的高度就可以了

第三題應該是官方有問題...只是說真的沒差大家都錯...
好像有少數人對啦orz只是說真的也沒啥影響@@

還有第一題TIOJ類似題是啥@@
那個不就卡特蘭數orz

還有感謝二樓提供線性規劃的參考資料QQ

記錄

wudaiyang

  • 初級會員
  • **
  • 文章數: 23
    • 檢視個人資料
回覆: 台北市資訊學科能力競賽 結束 !
« 回覆 #4 於: 十一月 20, 2010, 10:31:00 pm »

兩筆-1阿.....
我忘了撈頗白爛的真蠢....
記錄

lini

  • 高級會員
  • ****
  • 文章數: 101
    • 檢視個人資料
回覆: 回覆: 台北市資訊學科能力競賽 結束 !
« 回覆 #5 於: 十一月 20, 2010, 10:45:59 pm »

第五題明顯是線性規劃......一出考場很多人就在講了阿Q
如果真的只是DP或DFS+cut或BFS或Greedy怎麼可能沒人對= ="
2筆-1我覺得還頗瞎...雖然有撈到就是orz

第四題我不知道2000*2000=400萬有啥關係@@陣列開的下阿...
我是直接算兩個觀測點的距離以及x,y,z的改變量,兩個相除
代表每個單位移動~接下來就移動它拉~反正距離最多也才2000...不會TLE~
可是不要一次動10,就一次1單位1單位動,看那格的z有沒有大於現在的高度就可以了

第三題應該是官方有問題...只是說真的沒差大家都錯...
好像有少數人對啦orz只是說真的也沒啥影響@@

還有第一題TIOJ類似題是啥@@
那個不就卡特蘭數orz

還有感謝二樓提供線性規劃的參考資料QQ



第一題是同學跟我講的
指的是suhorng出的TIOJ 1607

我自己是當場想的 . . 花掉了一點時間
我跟我同學解法不太一樣 時間都是O(n^2) (只是空間用量我比較少 .)
題目n=25無所謂
不過TIOJ上限值10W穩炸 . .


第四題
了解 . .

因為那時候第一個想法是說
400W建築 每筆要怎麼O(1)判斷有沒有切到
後來還有try其他方向 but浮點數真的很煩
最後放棄 寫假解撈點分數



對不起 懂得太少 =  =

同學會的演算法跟我一樣多 只有很基本很基本的 .

私立學校
沒人帶 也沒有真的跟高手交流過
學校也不支持 (只管升學的白X)

所以結論 : 我很笨 . - -
記錄

kanna

  • 新手
  • *
  • 文章數: 1
    • 檢視個人資料
回覆: 台北市資訊學科能力競賽 結束 !
« 回覆 #6 於: 十一月 21, 2010, 03:29:24 pm »

pE是一類很標準的線性規劃題目。
基本上是屬於大學課程的東西,只是一種防破台而已...

如果有想要瞭解該怎麼去解的可以參考大陸的國家集訓隊論文:
李宇骞《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》
我自己是還沒開始閱讀啦,而且這類問題在高中競賽應該是屬於這次出現以後就再也不會碰到的題目。
===
97北市p1 cookie也是一類求整數解的線性規劃,
是屬於一類NPC問題,但是該題測試資料給定範圍很小所以可以進行枚舉。
===
我覺得此次比較嚴重的問題是測試資料普遍不強,
前四題前兩筆輸入皆為範例測資、像第四題印象中最大一筆才幾百...題目敘述過度膨脹,
第三題輸出答案相差皆很小,似乎是完全亂數產生之測資,而且第三筆似乎官方輸出有誤。
第五題竟然有兩筆標準答案為-1,讓不少puts("-1");者受惠...
第四題一點初步的想法:
可以想像成平面,假如隕石會從天空經過或者撞到大樓,那麼彗星的參數式與方格必定相交。
而這條直線必定與方格的四個邊至少有一個邊相交。
枚舉所有大樓的前後左右界,再做一點處理,可得解。

第五題考出來真的很扯,難易度差太多。
這次情況大致上是125-15(做不出來)-5(gift測資錯誤)=105分
然後比誰炸比較多這樣orz

師大和育成高中方面是一直表示,他們測資不出難是想讓不會算法的人也有機會能撈到分數。
出這樣確實對普通高中去參加的人有受惠,但是對於前段高中來講變成大家擠在100分附近,鑑別度小了許多。
相對的,筆試的重要性也高了很多。至於有沒有這樣做,則有待討論。
« 上次編輯: 十一月 21, 2010, 03:32:21 pm 由 kanna »
記錄

jurrasickill

  • 新手
  • *
  • 文章數: 13
    • 檢視個人資料
回覆: 台北市資訊學科能力競賽 結束 !
« 回覆 #7 於: 十一月 21, 2010, 05:56:27 pm »

kanna大的解法是比較嚴謹的方法

可是他在考到一半的時候有說有人問"剛好擦到"的情況

她的回答是說應該要算,可是測資內不會有這種極端測資存在...

所以第四題說真的亂亂做也不是不行....

不然第四題要處理的情況很多@@

像垂直、平行、同點觀測這些情況或許都還得先判掉才有辦法...

是說第五題有聽說有人假解用出一筆,不可能的情況判掉,所以或許有辦法拿到15分

第三題感覺應該是標程錯誤...有人greedy做還AC的@@

總之今年真的是筆試就是orz
記錄

phat

  • 新手
  • *
  • 文章數: 18
    • 檢視個人資料
回覆: 回覆: 台北市資訊學科能力競賽 結束 !
« 回覆 #8 於: 十一月 21, 2010, 06:53:34 pm »

引用
第四題一點初步的想法:
可以想像成平面,假如隕石會從天空經過或者撞到大樓,那麼彗星的參數式與方格必定相交。
而這條直線必定與方格的四個邊至少有一個邊相交。
枚舉所有大樓的前後左右界,再做一點處理,可得解。


事實上不用枚舉所有的左右界,可以先把參數式弄出來,

然後帶入所有x=10k求出所有隕石會經過而且是x方向大樓邊界的高度

帶入y=10w同樣求出所有y邊界,

這樣只要作(Sx+Sy)次處理,基本上複雜度不錯。


//不過這題讀入就Sx*Sy了,應該差不了多少xD
記錄

willyliu

  • 新手
  • *
  • 文章數: 13
    • 檢視個人資料
回覆: 台北市資訊學科能力競賽 結束 !
« 回覆 #9 於: 十一月 22, 2010, 08:32:18 pm »

第四題根本是認真就輸了的題目好嗎...

爆出參數式x(t), y(t), z(t)之後直接令step=0.001慢慢帶, 檢查現在的那格高度是否>z(t)就好了~

當然這種方法有可能會錯, 但考慮北市賽測資很弱的傳統, 不會有問題的.

認真寫判斷經過哪些格子反而容易編程出錯.
記錄

jurrasickill

  • 新手
  • *
  • 文章數: 13
    • 檢視個人資料
回覆: 台北市資訊學科能力競賽 結束 !
« 回覆 #10 於: 十一月 23, 2010, 04:29:12 pm »

第四題根本是認真就輸了的題目好嗎...

爆出參數式x(t), y(t), z(t)之後直接令step=0.001慢慢帶, 檢查現在的那格高度是否>z(t)就好了~

當然這種方法有可能會錯, 但考慮北市賽測資很弱的傳統, 不會有問題的.

認真寫判斷經過哪些格子反而容易編程出錯.

事實證明step=1也會AC= =

測資真的不強就是@@
記錄

lini

  • 高級會員
  • ****
  • 文章數: 101
    • 檢視個人資料
回覆: 台北市資訊學科能力競賽 結束 !
« 回覆 #11 於: 十一月 23, 2010, 09:55:13 pm »

QQ

測我的那位 按超快

完全看不到測資說 ..


X的 . 我幹嘛step -10啊

那時候2(邏輯出錯) 3(背包太久沒寫) 卡1小時
整個覺得很瞎 ..

緊張果然會失常 . X!


如果明年沒進TOI 電腦可以拿去燒了 ...
記錄

jurrasickill

  • 新手
  • *
  • 文章數: 13
    • 檢視個人資料
回覆: 台北市資訊學科能力競賽 結束 !
« 回覆 #12 於: 十一月 23, 2010, 11:28:38 pm »

(拍拍

我這次更X吧= =

IDE有問題....................

編譯出來都有問題= ="重新開機兩次才好的...

而且jack那題的測資多一個空白我也是一直找問題在哪浪費了也有一個小時吧= =
記錄

leo09221461

  • 新手
  • *
  • 文章數: 7
    • 檢視個人資料
回覆: 台北市資訊學科能力競賽 結束 !
« 回覆 #13 於: 十一月 26, 2010, 10:18:00 pm »

好吧我第4題想法明明就跟你們差不多
結果卻錯了
可能有些code錯吧...
於是只拿到3等獎...
基本上前4題都有把握應該都能拿到不錯的獎項吧
記錄

suhorng

  • 初級會員
  • **
  • 文章數: 26
    • 檢視個人資料
回覆: 台北市資訊學科能力競賽 結束 !
« 回覆 #14 於: 十一月 26, 2010, 11:32:14 pm »

基本上前4題都有把握應該都能拿到不錯的獎項吧
一等~二等之間 (看筆試)
第五題很多人都 puts("-1"); 得到 10 分 (15筆)
看測資好像有幾筆是二維的zzz (12筆?)
但官方只提供三筆測資所以實際情形也不知道

不過第三題第三筆官方測資應該是錯的...
記錄

ACRash

  • 新手
  • *
  • 文章數: 11
    • 檢視個人資料
回覆: 台北市資訊學科能力競賽 結束 !
« 回覆 #15 於: 十二月 06, 2010, 11:53:58 am »

tioj上那題有點數學成分了...

不過既然是數學題, 而不是需要自己思考的算法題,

我就來略述一下:


此題是利用F(n) = C(2n, n) / (n + 1)的數學式來做

但是因為mod, 所以就必須求出 n + 1 的逆元素.


另外對每個詢問O(n)顯然不會過

所以可以找出F(n)之間的遞迴關係, 一路DP上去.

之後每個問題可以O(1)回答

不過還是會用到逆元素啦...



逆元素有兩種求法:

一種是利用輾轉相除法來做擴展歐基理德

另外一種可以從費馬小定理知

在mod 1000000007下, x ^ 1000000005 就是 x 的逆元素

只需寫一個快速羃即可.



以上... 有錯還請各位更正
記錄

jurrasickill

  • 新手
  • *
  • 文章數: 13
    • 檢視個人資料
回覆: 台北市資訊學科能力競賽 結束 !
« 回覆 #16 於: 十二月 06, 2010, 09:22:57 pm »

那題本來就幾乎數學吧(zzz
整個數論(?

話說看到上一頁書弘的最後一個留言還是好想哭QQQQQQ
記錄

lini

  • 高級會員
  • ****
  • 文章數: 101
    • 檢視個人資料
回覆: 台北市資訊學科能力競賽 結束 !
« 回覆 #17 於: 十二月 06, 2010, 10:54:25 pm »

?
完全 . 看 . 不懂 . =  =


第一題我是用排容原理
寫了一個稍微複雜的遞迴式

最簡單的寫法應該就是開二維陣列DP吧 . .


第五題
線性規劃後來去問數學老師 她也只會二維的 QQ

我們雖然是私立學校 但進度目前也才要到高三上 . .


不過
只公布部分測資 是哪招 = =?
(( 怕自己正解有誤噢 ?
記錄

ACRash

  • 新手
  • *
  • 文章數: 11
    • 檢視個人資料
回覆: 台北市資訊學科能力競賽 結束 !
« 回覆 #18 於: 十二月 11, 2010, 09:36:22 pm »

看不懂其實沒關係

北市賽那題測資很小, 隨意作都會過.


只是寫TIOJ有時候需要一點點數論基礎這樣
記錄
+ NPSC補完計劃 » 一般 » 綜合討論區
 台北市資訊學科能力競賽 結束 !