[回到版面]
回應模式
名 稱
內 文
附加圖檔[] []
  • 可附加圖檔類型:GIF, JPG, JPEG, PNG, WEBM,瀏覽器才能正常附加圖檔
  • 附加圖檔最大上傳資料量為 3072 KB。
  • 當檔案超過寬 125 像素、高 125 像素時會自動縮小尺寸顯示
  • 目前附加圖檔使用量大小: 220083 KB / 500000 KB
  • 回覆時程式碼縮排會被trim消掉,請善用[code][/code]標色或貼到ideone等網站
  • LaTeX記法可以用「$$」或「\( \)」包起來,例如「$\sum_{k=1}^{k=n} k^2 = \frac{n(n+1)(n+2)}{6}$」
  • 投稿時請點擊畫像認證後,再按下 [送出] 按鈕提交。
  • 鬧板、攻擊性發言、煽動性發言請無視(回應者也無視),並使用del或在貓管理部向管理員回報。
  • 新介面尚處於測試階段,如果有任何問題可以向管理員或於程設交流版反映。

檔名:1554536038977.jpg-(47 KB, 1280x720)
47 KB
競技程式綜合無名19/04/06(六)15:33:58 ID:zVucc1IENo.13204del
好像從來沒看過有人開類似串就負責拋磚引玉一下
各類演算法、程式競賽甚至其他比賽(CTF之類)都歡迎

目前的大比賽(codejam):
https://codingcompetitions.withgoogle.com/codejam
qualification round 到台灣時間 4/6 10 點截止

其他演算法比賽日曆:
https://competitiveprogramming.info/calendar
無名19/04/06(六)16:10:48 ID:zVucc1IENo.13206del
寫個簡單的 Q&A

Q1. 參加競技程式應該要期待什麼?
A1. 把參加比賽當成以 splatoon S+ 或 iidx皆伝為目標這樣的遊戲感覺來玩好好享受吧, 努力後看 rating 慢慢上升的成就感很好玩的
  高中生或大學生請以 TOI 或 ICPC regional 為目標吧
  最近除了 TOI 以外, APCS 之類的比賽也可以拿來當高中升學的依據

Q2. 推薦的中文資料?
A2. 各個學校培訓資訊奧林匹亞或 ICPC 的資料都不錯, 例如建中的培訓講義
  https://tioj.ck.tp.edu.tw/articles?era=2017
  http://pisces.ck.tp.edu.tw/~peng/
  如果還是覺得太難可以從 DJWS 之類的地方開始

Q3. 初學者應該從什麼開始學?
A3. 參加個人比賽的話最重要的是一些基本概念的問題, 因為 ad-hoc 問題很多
  演算法構造的基本概念(分治,貪心,DP...), 基本資料結構, 基本圖論演算法(最短路系列, 生成樹...) 等等
  題目大概八九成都離不開這些基本概念
  如果是大學生以 ICPC 為目標的話就得要再加上一些難一點的模型和建模技巧

Q4. 推薦給新手的比賽?
  大部分的比賽平台都有依照 rating 分等級, 像 codeforces, topcoder 的 div3, div2 都ok
  再更新手的話推薦 atcoder 的 beginner contest, 沒太多困難的演算法概念很適合新手練功

Q5. online judge?
  像 TIOJ 這樣的難度以蠻理想的, 而且還是中文的
  寫 UVA 之類的傳統 OJ 當然也沒問題, 可是題目太多最好能注意一下題目的品質, 有好的題單能避免浪費太多時間在不必要的問題上
無名19/04/06(六)21:00:55 ID:qEN8RYaoNo.13209del
想問一下code jam最後一題的interactive有什麼推薦的debug方法嗎
想印debug message出來但什麼都看不到好難用

在比賽中問系統的問題不確定合不合規定
不行的話我會自刪
無名19/04/06(六)22:26:21 ID:zVucc1IENo.13210del
>>13209
例如把 stderr 的資料抓出來呢?
t_sol.start()
t_judge.start()

while True:
nextline = t_sol.p.stderr.readline()
if nextline == '' and t_sol.p.poll() is not None:
break
sys.stdout.write(nextline)
sys.stdout.flush()

t_sol.join()
t_judge.join()


這樣在 solution 的程式就可以 fflush stderr 把 debug 訊息印出來
無名19/04/07(日)01:25:31 ID:6Ojm5dDENo.13211del
>>13210
謝謝 看來python果然是官方預設大家要會的語言...
無名19/04/07(日)02:37:48 ID:ad8FLdy.No.13212del
檔名:1554575868812.png-(144 KB, 1376x1573)
144 KB
才一年沒比而已怎麼介面跟比賽內容差這麼多
現在的記分板好難閱讀,好友功能刪掉一頁顯示的人數又變少不知道到底在想什麼

還有為什麼拿滿分以後名次會隨時間減少啊?
無名19/04/07(日)03:57:06 ID:XndUSiwYNo.13213del
>>13212
同分的話就比誰快這樣吧?
無名19/04/07(日)08:01:36 ID:EvOt1OksNo.13214del
>>13213
他是說過一段時間之後發現自己名次越來越前面
我也會這樣,感覺像是系統的問題
就算作弊有人失格也不會突然上升個幾百名吧
無名19/04/07(日)09:17:29 ID:/Dv4kL.wNo.13215del
好奇大家都用什麼語言寫題目?
python嗎?
無名19/04/07(日)16:30:36 ID:.t4Q9ZbINo.13218del
大部分的時間都用C++, 限制少而且比較不容易卡到時間限制
偶爾方便時才會用 python 或 ruby, 例如要寫大數的時候

這邊有前幾年使用語言的統計, 越後面的 round C++ 比例越高
https://www.go-hero.net/jam/17/languages
https://www.go-hero.net/jam/16/languages
無名19/04/07(日)17:06:58 ID:.0XHVjosNo.13219del
預選前兩題這種題目真的很討厭
花了很久時間想才發現是像腦筋急轉彎的題目
寫出來code根本不到十行
這種題目真的有辦法練習嗎

還有第四題要怎麼在5次以內問出來?
https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/00000000000881de
無名19/04/07(日)17:27:17 ID:az/vUsNQNo.13220del
>>13218
大數是python專屬技能嗎???
python底層應該也是用GNU出的GMP來做大數運算的吧?
這不算是python的賣點吧??
無名19/04/07(日)17:47:55 ID:.t4Q9ZbINo.13221del
>>13220
我沒有說專屬技能啊
我的意思是寫 code 省時間省 penalty 就用而已
無名19/04/07(日)17:58:27 ID:.t4Q9ZbINo.13222del
>>13219
那種題目只能練習觀察能力吧, 我也覺得數學好的特別吃香

第四題:
詢問的時候,第一次可以把 16 個切成一小塊詢問
0000000000000000 1111111111111111 0000000000000000 111...
想辦法在第一次詢問的時候得出每一塊有幾台好的電腦

通常不能這樣切很多塊只能切兩半的原因是因為
詢問 000 111 000 111 如果機器回答 11
會無法判斷回答 1 的機器到底是在左2或是右1那一塊
但題目給了 B≤15 的條件, 代表每 16 個切一塊的時候不會有一塊的電腦是全壞的
所以上面講的情況不會發生
詢問次數是第一次切 16 的詢問一次,加上長度 16 的二分搜尋四次一共是五次
無名19/04/07(日)21:10:47 ID:7ZgT4gdkNo.13225del
>>13215
一般習慣寫online judge的人都用c++吧?
無名19/04/09(二)01:13:29 ID:Dvk/OtcoNo.13228del
>>13212
那個應該是新ui同步沒同步好的問題
計分板顯示的資訊常常是沒更新或錯誤的

計分板難看就算了 寫code的地方要沒辦法看錯誤訊息抓錯超難用
甚至有的語言根本沒實作好 傳了幾個小時到比賽結束還在pending judge
根本踩地雷大賽
無名19/04/14(日)14:05:08 ID:9JgDXuhINo.13250del
想問一下面試時常問到的問題
有 2 顆蛋,n 層樓
蛋從 >= k 樓丟下來會破,反之則不會破(可以繼續丟)
每次實驗可以拿一顆蛋從某層樓丟下去檢驗他會不會破,但手上就只有兩顆而已
問要確定 k 至少要實驗幾次
http://datagenetics.com/blog/july22012/index.html

想問一下這種題目大家遇到這種面試題通常都怎麼想?
無名19/04/14(日)15:05:54 ID:niy/vb9cNo.13251del
無名19/04/14(日)15:06:20 ID:sFegHACkNo.13252del
>>13250
從現有的演算法去想......吧
這題目看起來就是二分搜尋的變形
無名19/04/14(日)19:38:26 ID:HLOGuF3INo.13254del
>>13250
如果什麼都不知道, 也不確定貪心正確性就先從列式子開始
變數有"樓層數"跟"實驗次數"兩個, 所以遞迴式很有可能是一維的

假設狀態寫成這樣好了:
f(n樓) = 兩顆雞蛋在 n 層樓最少的實驗次數

接下來就可以想想看轉移式
首先, 如果在 n 樓的大樓中選擇 x 樓實驗一次, 會有兩種情況:
狀況1. 蛋沒破, 剩下用 2 顆蛋在 x+1 ~ n 樓之間找會破的樓層, 需要花 f(n-x) 次實驗
狀況2. 蛋破了, 剩下用 1 顆蛋在 1~x-1 樓之間找會破的樓層, 需要花 x-1 次實驗

狀況1 和 狀況2是你實驗的人沒辦法決定的, 考慮運氣最差的情況
如果第一次在第 x 樓丟雞蛋的話,會需要實驗 max{f(n-x), x-1} + 1 次
寫成遞迴式就是這樣: $\displaystyle f(n) = \min_{1 \le x \le n} (\max \{f(i-x), x-1 \} + 1)$

那 x 怎麼辦? 最簡單的方法就是對於每個 n, 都從 1~n 慢慢嘗試
看誰算出來的答案比較小
你這樣就會得到一個簡單的 O(n^2) 算法
int n=100, f[110];
f[0] = 0;
f[1] = 1;
for (int i=2; i<=n; i++) {
f[i] = i;
for (int x=1; x<=n; x++) {
f[i] = min(f[i], max(f[i-x], x-1) + 1);
}
}
無名19/04/14(日)19:57:14 ID:HLOGuF3INo.13255del
>>13254
再來是改進, 因為 O(n^2) 很明顯有點慢
至於怎麼改進呢可以觀察一下幾個特性

1. f(n) ≦ f(n+1), 這很顯然, 因為樓層數越多要實驗的次數當然越多
2. 當 i 固定, x 是變數時, max(f[i-x], x-1) 是個凹函數
因為隨著 x 越大, f[i-x] 越小, x-1 越大
一個遞減跟遞增的函數取 max 就是凹函數

所以就可以有兩個改進的方法
1. 利用是凹函數的特性, 對於每一個 i, 我們可以用三分搜尋 x 決定凹函數的最低點
這樣複雜度會變成 O(n log n)

2. 對於 f(i) 與 f(i+1) 的最佳決策點 x1 與 x2 (第一次丟下去最好的樓層)
可以發現 x1 ≦ x2, 這個有點難用式子解釋, 不過大概可以猜出來
因為越高的大樓, 第一次丟下去最好的位置應該越高才對
所以上面的 code 在迴圈時可以直接從舊的 x 開始跑, 跑到答案不會更好為止
可以改進為 O(n)
int n=100, f[110], x=1;
f[0] = 0;
f[1] = 1;
for (int i=2; i<=n; i++) {
// 如果 x+1 會比較好, 就讓 x++
while (x+1<=n && max(f[i-x-1], x)+1 <= max(f[i-x], x-1)+1) x++;
f[i] = 1 + max(f[i-x], x-1);
}
無名19/04/14(日)20:02:11 ID:HLOGuF3INo.13256del
>>13255
回到最原本的問題, 面試會被問這種問題不外乎是想看思考過程
所以能有辦法列式分析答案, 有辦法把列出來的式子寫成 code
在大部分的面試都會有非常好的表現

再更進一步的, 是在給出基本想法以後
有辦法看出自己演算法效率的問題點, 然後想辦法觀察條件改善複雜度
從頭開始想並改進算法的人, 得到的面試評價會遠比直接把作法背出來(直接給出最佳解)還好很多
無名19/04/14(日)20:06:13 ID:sFegHACkNo.13257del
>>13256
要訓練這種思考方式有什麼途徑呢
感覺上面還用上不少數學
無名19/04/14(日)20:13:14 ID:HLOGuF3INo.13258del
>>13257
其實說是數學, 真的要會的基礎知識也沒有很多
不是像微積分或代數之類大學才會學到的內容

多去寫線上比賽dynamic programming的題目
多看別人怎麼列式或優化轉移蠻有用的
很多比起理論比較像是經驗
無名19/04/14(日)23:02:09 ID:9JgDXuhINo.13259del
檔名:1555254129455.jpg-(125 KB, 1024x1280)
125 KB
>>13256
太感謝了!上網查都只查到一些公式解都沒有這樣的解說
剛剛把你貼的兩份code試著跑一下,下面那一份真的快很多
可以請問一下為什麼下面這樣做兩層迴圈的複雜度是O(n)嗎?
無名19/04/14(日)23:53:48 ID:HLOGuF3INo.13260del
>>13259
均攤 O(n) 沒錯
每進 while 迴圈一次 x 就會加 1, x 最大是 n
所以不管裡層還外層迴圈都只會跑 n 次而已
無名19/04/15(一)21:42:15 ID:BSP2U11ENo.13261del
這題就二分下去跑出O(log n)而已
為啥要搞到這麼複雜?
無名19/04/15(一)23:01:12 ID:S3dU2EwMNo.13262del
>>13261
因為只有兩顆蛋而已
不可以一直把蛋打破
無名19/04/15(一)23:06:51 ID:WwdiyET2No.13263del
檔名:1555340811427.jpg-(859 KB, 1952x1968)
859 KB
>>13250
>>13254
>>13255
>>13261
>>13262
我覺得題目很怪,你們的解法更怪。
【兩顆蛋都會是同一個樓層破的嗎?】
如果是的話,為啥不要每次都加兩樓,破掉的話就是是看加一樓就好?
如果不是的話,不能同一個樓層兩顆雞蛋都丟一次嗎?
無名19/04/15(一)23:10:57 ID:BSP2U11ENo.13264del
>>13262
破的話只是實驗次數+1而已
log n不會變
極端情況就是蛋超幹爆多
但是題目只有兩顆蛋
沒必要為了/2去犧牲log n的效率
無名19/04/15(一)23:11:15 ID:S3dU2EwMNo.13265del
>>13263
從第k樓以上丟會破,所以題目要問一個找出k的最佳策略
每兩層丟一次是個可以找出解的策略沒錯
但這樣要花n/2+1次實驗

上面解答那個遞迴就是在解理論最佳的實驗次數
無名19/04/15(一)23:13:56 ID:WwdiyET2No.13266del
檔名:1555341236431.png-(62 KB, 400x250)
62 KB
>>13263
原本是只看部分回文想說這啥排序法,怎麼看都看不懂,難道老了不中用了嗎?
直到整個往上翻,看到那奇怪的雞蛋題目為止.......

設計與邏輯有一個觀念是這樣的
【不使用框架(模式)與使用框架(模式)同等重要】

不管是程式碼或是題目,我覺得都要寫得能夠讓人閱讀。
畢竟開發與維護的人還是人啊....
無名19/04/15(一)23:17:39 ID:xmbGZVEoNo.13267del
他題目下面有附英文連結喔
http://datagenetics.com/blog/july22012/index.html
看起來沒什麼問題 至少數學上的定義很清楚
無名19/04/15(一)23:31:38 ID:P3JYtIFkNo.13268del
>>13266
code部分不是可讀性差,因為這一串是演算法的討論
定義都用式子寫出來了沒什麼可讀性的問題吧(也才兩三行)
話說不管在面試還是在比賽,數學證明和正確性還真的幾乎是一切
你去翻翻ICPC或資訊奧林匹亞冠軍的code就知道大家平常都寫很亂的
無名19/04/15(一)23:39:59 ID:WwdiyET2No.13269del
檔名:1555342799981.png-(147 KB, 400x295)
147 KB
>>13267
瞄過了,原本以為是哪裡的面試介紹文就沒看。
這樣看起來題目還OK,是我沒去詳讀。

但上面的解答還是很怪。
整篇看起來重點就是【Minimization of Maximum Regret】
與【Two egg solution表格與說明】。
是一個很有智慧的解法。
無名19/04/15(一)23:46:07 ID:BSP2U11ENo.13270del
有沒有英文大師能解惑
是題目的哪個條件導致不能用二分搜尋得出的log N去解?
無名19/04/15(一)23:47:20 ID:xmbGZVEoNo.13271del
>>13269
英文那篇做法
> Imagine we drop our first egg from floor n, if it breaks, we can step through the previous (n-1) floors one-by-one.
> If it doesn’t break, rather than jumping up another n floors, instead we should step up just (n-1) floors (because we have one less drop available if we have to switch to one-by-one floors), so the next floor we should try is floor n + (n-1)

這裡只有講貪心的作法怎麼做,但是並沒有證明這樣實驗次數最少
或者不存在更好的解
要怎麼證明這樣做次數最少,那就是問題所在
無名19/04/15(一)23:49:36 ID:WwdiyET2No.13272del
檔名:1555343376543.png-(97 KB, 906x680)
97 KB
>>13269
給忙碌的人簡單導引
【Many Eggs】->終極密碼
【Back to two eggs】->這題不是終極密碼

所以如果已經知道終極密碼的話可以跳過這兩個
無名19/04/15(一)23:49:53 ID:xmbGZVEoNo.13273del
>>13270
假設有100層樓,但是只要高於一層(k=1)蛋就會破
第一次會在50樓摔破一顆蛋,改試1~49層
第二次又會在25樓摔破一顆蛋
然後就沒有蛋了,沒辦法確認到底k是1~25的哪個數字
無名19/04/15(一)23:59:45 ID:P3JYtIFkNo.13274del
>>13272
面試官:「我們只有兩顆蛋...blahblah」
「我會無限顆蛋的做法,蛋那麼少這題題目一定有問題」
無名19/04/16(二)00:03:32 ID:iMFASpRgNo.13275del
檔名:1555344212276.jpg-(72 KB, 600x447)
72 KB
>>13274
其實業界中,只用兩顆蛋屬於機器底層,往韌體方面靠攏。
而找尋更多蛋,其實也有人要,也很搶手。

所以雖然你應該是等著被吐槽,但我還是要告訴你
【你真的有辦法從機器(環境)上多擠出一顆蛋,那你肯定很厲害】。
無名19/04/16(二)00:05:12 ID:ndijZ8McNo.13276del
>>13273
理解題目了,THX
無名19/04/16(二)00:10:57 ID:qqujh2/cNo.13277del
演算法的題目本來很多都是數學puzzle
這裡討論的純粹就是一個數學的問題而已
就好比在玩魔術方塊的時候,不會有人問「為什麼不把方塊拆掉重組就好,這樣做有效率很多」一樣

>>13275
在軟體業尤其外商問這種問題也是見怪不怪
不喜歡的話去別的公司就好了何必這麼激動?
無名19/04/16(二)00:15:01 ID:iMFASpRgNo.13278del
檔名:1555344901102.jpg-(114 KB, 500x439)
114 KB
>>13277
窩覺得你在紮稻草人
無名19/04/16(二)00:19:52 ID:0g7qq6q2No.13279del
>>13278
他是在說你很KY...
無名19/04/16(二)00:29:09 ID:ndijZ8McNo.13280del
>>13274
口氣差可以去刷牙
無名19/04/16(二)00:31:21 ID:igx09KpINo.13281del
>>13228
有找到非官方的計分板
不過是賽後才有人統計的...
https://codeforces.com/blog/entry/66518
無名19/04/16(二)00:34:28 ID:iMFASpRgNo.13282del
檔名:1555346068765.png-(61 KB, 600x600)
61 KB
>>13279
沒有KY喔,先跳脫雞蛋這個題目限制。
假設同樣的邏輯,你今天可以寫成非同步。
那就是解決速度的困境,那就可以視同這題"找出並運用其他顆雞蛋"。
又或是檢查機器狀況,發現有處理高峰與低峰,那有不改變既有系統處理上,
平衡高低峰處理,也是很有價值的學問。

所以我才說,雖然>>No.13274看起來是來亂的回答。
但實際上能找出更多蛋並有效運用的人其實也是很有價值。
無名19/04/16(二)00:40:10 ID:qqujh2/cNo.13283del
其實要增加雞蛋數量也沒問題...

所以題目可以看成有 n 層樓, m 顆雞蛋可以實驗
剛剛 m=2 和 m>=n 的情況已經找到最少實驗次數的解了
那 m=3, m=5, m=10 怎麼算最少的實驗次數呢?
畢竟這是演算法的討論串大家就一起開開心心來解puzzle吧~
無名19/04/16(二)01:29:43 ID:qqujh2/cNo.13284del
>>13283
剛算一下發現解還蠻有趣的
原本100層樓2顆蛋的問題第一次實驗也不只有第14樓可以丟而已
9~14樓都一樣是最優解

https://gist.github.com/yoshikikazunari/1fcaaa7f37cdb85f64d39088633656b8
無名19/04/16(二)09:13:29 ID:p6UF0PHgNo.13285del
>>13284
9樓爬到99樓要扔11次
要是答案在98樓就不會是最佳解
無名19/04/16(二)10:58:17 ID:JoSTqas6No.13286del
>最近除了 TOI 以外, APCS 之類的比賽也可以拿來當高中升學的依據
怎麼多一堆沒聽過的比賽啊
所以考APCS也有保送的資格嗎
無名19/04/16(二)17:04:07 ID:8a7JrgGgNo.13288del
>>13282
なので樹。
無名19/04/16(二)18:13:46 ID:igx09KpINo.13289del
>>13286
據我所知,目前特殊的升學管道有幾種

保送和推薦: 教育部公布的,在奧林匹亞選訓營前11名可以推薦任何相關科系,如果有拿牌可以保送除了醫學系以外的任何科系。不需要學測成績也不需要備審資料,走這個管道的基本上就是台大資工、電機和數學系

特殊選才: 各校公布,比較有名的是交大資工和中山資工。不需要學測成績,但要準備備審資料審查,不保證會上。這邊雖然採計APCS但也不知道實際怎麼算的
http://exam.nctu.edu.tw/108%E5%AD%B8%E5%B9%B4%E5%BA%A6%E5%A4%A7%E5%AD%B8/%E7%89%B9%E6%AE%8A%E9%81%B8%E6%89%8D/108%E5%AD%B8%E5%B9%B4%E5%BA%A6%E7%89%B9%E6%AE%8A%E9%81%B8%E6%89%8D%E6%8B%9B%E7%94%9F%E7%B0%A1%E7%AB%A0.pdf

推甄: 說APCS採計的主要是這裡,但就是跟以前學測一樣當備審資料。需要學測也需要備審資料
無名19/04/16(二)20:14:34 ID:iMFASpRgNo.13290del
檔名:1555416874818.jpg-(6 KB, 264x191)
6 KB
無名19/04/16(二)21:44:11 ID:xJK7djr2No.13291del
升學管道雖然變多
但看這幾年台灣參加競賽的人口其實沒變很多
日本倒是這幾年每年參賽人數都在增加
到底為什麼呢
無名19/04/16(二)21:46:18 ID:AWyctYkkNo.13292del
>>13291
大概是因為沒有幾個學校在推廣吧
無名19/04/16(二)22:01:35 ID:l6iGqidwNo.13293del
其實升學管道並沒有多很多
除了保送和特殊選材以外 其他都要學測或指考成績
實質上跟推甄沒兩樣

這幾年多出的特殊選材 單就資工系來講一年名額也才20個人左右
這20個人大多是選訓營沒進二階段的人拿的
也就是說除了建中 中南一中這些本來競賽就很強的學校以外
對其他高中而言基本上是無緣的
無名19/04/16(二)22:58:46 ID:dWwi1EQ2No.13294del
保送基本上不用肖想
除非你是建中資優班那種強到見鬼的
不然結論還是要乖乖考學測指考

不過有機會在國高中就接觸程式的話真的建議認真玩
如果你有打得出還算能看的成績的能力
未來就算不讀大學,直接靠這個就能就業

我當年是選訓營第一階段刷掉(20~40名)
看了看簡章沒什麼很值得的加分條件,後來還是考了指考
然後讀了個跟資工無關的科系
然後還沒畢業就被拉回軟體業當了工程師
無名19/04/17(三)01:24:16 ID:wfvCNi9gNo.13295del
認真講TOI的一階在幾年前其實沒有很難
因為以前資訊競賽是少數人在玩的
看某些高中資訊社就知道會比這個的幾乎本來都是一天到晚廢在電腦前的那種宅
所以數學基礎練練, 基本的資料結構, DP, 圖論認真練個一兩年就要過及格線不難
雖然一階跟二階程度差距很大也不能保送 但至少也可以說自己進過選訓營

從今年開始研究所報考資工的人就多非常多
高中也開始出現一堆補習班家教 搞不好以後會變很多人比的比賽也說不定..
https://orangeapple.co/courses/apcs
https://www.pcschool.com.tw/activity/107/1070109_APCS/index.html
無名19/04/17(三)08:57:42 ID:2eRBi.DANo.13296del
那像建中資優班有特別的老師在培訓資訊競賽嗎?
無名19/04/17(三)20:59:36 ID:wfvCNi9gNo.13297del
>>13296
在資訊競賽這一塊 不管帶的人還是出題目的都是選手或退役選手
建中的講義最上面的第一篇回覆有 那些都是每年同學自願寫的
就算在選訓營裡面通常也都是大家自己練自己的 因為教授也不知道怎麼針對比賽教比較好

還有 建中之所以會是全世界奧林匹亞最強的學校我覺得和校風有關
不管是以前學長姐累積下來的培訓風氣也好 或者是學校可以請公假準備的制度也好
他們給了學生很大的權力來規畫自己時間和想做的事情
其它的前幾志願雖然沒建中完整 但也有類似的制度和風氣在
這才是非前幾志願永遠沒辦法贏的原因
無名19/04/17(三)22:30:17 ID:hr4b/7T2No.13298del
如果能把高中那些國文、音樂等等課都能自修演算法
相信高中生的演算法能力可以大幅前進
可惜鐵飯碗不會答應這種事情
無名19/04/17(三)22:43:21 ID:zasfM3VoNo.13299del
>>13297
跟課程制度也有關
當年我讀PR95等級的高中
全校兩千多個學生,算得上會寫程式的不到十個
電腦課只教你用紙筆抄寫VB
這種學校出得了選手才奇怪
無名19/04/17(三)22:46:06 ID:WC0lVMqsNo.13300del
>>13298
不是只有自修演算法或強迫只能選幾個科目,而是要能做所有事情
這才是真正教育應該賦予學生的機會
可惜的是台灣的學生就算給這樣的權力和時間,真的很清楚知道自己想做什麼的
也就只有少數的一群人而已

但就算是會被濫用或者只有少數人能善用,這樣的價值觀也不該被否定
這篇文就講得很好
https://www.ptt.cc/man/ck54th122/D1B5/DD46/D634/M.1493389457.A.D70.html

>我後來回想,才知道我們的老師花了多少力氣在保護我們,避免我們背負太多不屬於我們
>的責任,避免我們受到不合理的不成文規定或價值的約束。他們跟教官說不要管我們中午
>在教室看漫畫打橋牌,他們在教室前面直接放一疊公假單,跟大家說想要離開學校就自己
>簽。

>這樣的做法不是放任,是信任。信任自己的學生,也信任就算被偶爾濫用,讓有需要的學
>生擁有去探索自我、任意運用時間的自由的重要性,遠大於少數學生簽公假單去打網咖被
>抓到的麻煩。

>我相信老師會這樣跟教官為自己的學生辯護:「如果學生簽公假單去打網咖,那是因為他
>現在需要打網咖。」這種興利大於防弊的精神,出了建中,在這個國家我再也沒有感受過
>。
無名19/04/17(三)23:26:53 ID:zQ.6rqeANo.13301del
>>13299
可是其它高中也沒有教啊?
以前建中附中的電腦課也是大家都在打CS玩遊戲

大多數參加比賽的人都是自學 不然就是社團同學之間一起互相學的
這樣反而能凸顯這群人是完全憑興趣在玩的
反過來講, 開始重視資訊教育, 要開始評估所有人的資訊成績這種風氣的出現才是應該注意的
只會扼殺更多的學生而已, 一點好處都沒有
無名19/04/17(三)23:39:29 ID:zasfM3VoNo.13302del
>>13301
我是不太清楚別的學校的實際情況啦
不過光看賽場榜單我覺得應該有特定幾所學校有在教
往往被少數幾所高中大量洗榜,其他高中出現零星一兩個人
像建中就是洗榜主力
你要說建中的人都對程式特別有興趣、自學人數多到能佔全高中生一半以上?
也許有可能啦,畢竟是建中
但還有其他幾間我連名字都不記得的私校也在洗榜,那就沒辦法解釋了


>>開始重視資訊教育, 要開始評估所有人的資訊成績這種風氣的出現才是應該注意的
>>只會扼殺更多的學生而已
確實
我也不認同在正課教演算法
畢竟演算法只是我們這個小圈圈在玩的東西,別人根本沒理由來學
而且這東西如果被逼成績,學習效益肯定大減

不過倒是該加一門電腦基本常識課
這年頭懂得裝設wifi AP比起懂生火綁結、知道蘇軾老爸的名字等等都重要多了
無名19/04/17(三)23:45:27 ID:zasfM3VoNo.13303del
想想上面我講的看起來好像矛盾
這邊多解釋一下

我覺得應該在副科教基本程設
不逼成績也不教到演算法那麼硬的東西
就只是介紹個基本的程設觀念給學生
沒興趣的人就像其他副科一樣玩玩混混就過去,反正副科本來就是這樣
有興趣有天分的人則能藉此得到繼續自修的方向
勾起盡量多的人走向這條路,對他們對國家應該都是好的
無名19/04/17(三)23:46:47 ID:zQ.6rqeANo.13304del
>>13302
據我所知 目前有專門請人來培訓的只有像康橋這種私立學校而已
大部分學校比賽的傳統(至少資訊這一塊)都是社團為主
像建中資訊社就有學長帶學弟的風氣
而中一中、南一中、雄中附中據我所知競賽的主力也都是社團
確實說完全自學也不太對,但裡面學長姐都會告訴你該怎麼學或該學什麼比較有效率

而這件事情到大學就更極端
如果你知道台大ICPC培訓的方法就知道
除了練習賽是幾乎沒有上課的(頂多暑假上一兩天課而已)
無名19/04/18(四)00:08:41 ID:3J7GajlwNo.13305del
>>13304
而且資訊最大的優勢是情報開放
網路上免費的資源很多 願意公開情報的人也很多
這點很重要, 至少有人跟你提學習的方向之後要怎麼造成就看個人了
對後面的學校至少不會是劣勢才是

如果跟物理化學比就知道
他們不只實驗器具要錢 獲得不易
還有獲得不易的資料(像物理奧林匹亞的灰書, 只有進過選訓營的才拿得到), 學校如果沒有參加過選訓營的學長姐根本就拿不到
資訊跟這些比賽相比, 就顯得平易近人很多, 只要有電腦和網路幾乎可以做到所有事情
無名19/04/18(四)00:32:36 ID:9630UDKcNo.13306del
>>13300
看過這篇 真的寫得很好...
考好學校最大的目的不是因為裡面的課或老師有多好
而是老師願意尊重學生的態度和願意給自由發展的機會
說來簡單 但全台灣真的沒幾間學校可以做得到這件事

在某些高中還在討論該不該髮禁的同時
另一些學校已經這麼先進了
這也難怪差距會這麼大了
無名19/04/18(四)12:26:19 ID:tJgeUd2gNo.13307del
>>13306
同儕競爭力差很多
PR99跟PR90就能感受到差距
更別說90不到的學校
而後段班又會拖累整個學校的開放程度
要8+9自我學習實在太難
沒在學校抽菸吸毒打炮就不錯了
無名19/04/18(四)19:09:24 ID:uxOm2s7.No.13308del
>>13302
>但還有其他幾間我連名字都不記得的私校也在洗榜

查了一下今年TOI的學校分布 完全沒有洗榜吧?

一階(共33人)
建中 8
實驗 6
成功 5
南一中 3
延平 板中 2
附中 彰中 雄中 嘉華 1
增額: 北一女2 中山女1

二階(共12人)
成功 4
實驗 3
建中 板中 2
南一中 1

比起高中,大學的獨佔狀況嚴重很多
除了前一兩年有交大參賽以外,每年進 ICPC world finals 的都只有台大而已
這其實不是個好現象...
無名19/04/19(五)01:15:25 ID:af8/4aOENo.13309del
想問一下這邊的大神線上比賽rating大概多少?
個人有比codeforces和atcoder
不過rate都卡在綠色~藍色中間上不去
有什麼建議突破的方法嗎
無名19/04/19(五)20:47:59 ID:qlG7jHWMNo.13310del
>>13309
卡在2300~2400升不上去
atcoder和codeforces要練的地方有點不太一樣

atcoder的題目非~常數學
思考過程很長 但寫出來的code通常很短
要練這種題目我覺得最好的方法就是多寫atcoder...
看解答的時候可以多想想為什麼這樣做是對的 盲點在哪
還有可以多練習證明正確性和複雜度
這對以後看到ad-hoc題的思考過程會有幫助 思考速度會變快一點
最好不要看到解答什麼都不想就寫成code 因為以後遇到變形的題目還是想不出來

另一方面codeforces的題目就經典演算法比較多
除了上面的那種ad-hoc題以外 如果目標是要寫出div2的後面兩三題
可以把一些經典的技巧看一看 像矩陣的DP轉移啦, 圖論啦, 線段樹的應用...
跟練ICPC的方法比較像
無名19/04/20(六)15:59:19 ID:D4bQE.OMNo.13313del
20:00~21:40 AtCoder
24:00~26:00 TopCoder
26:05~28:35 Codeforces
31:00~34:00 Google kickstart
34:30~36:00 LeetCode

看了一下今天晚上超多比賽
有勇者可以全部參加嗎
無名19/04/20(六)21:58:08 ID:3dpAIVYsNo.13314del
atcoder題目難到哭出來了...
還有比到一半突然server沒辦法更新 慘
無名19/04/20(六)22:11:49 ID:D4bQE.OMNo.13315del
>>13314
官方說如果會lag的話用新版介面
https://twitter.com/chokudai/status/1119598315870441472
無名19/04/20(六)22:20:22 ID:3dpAIVYsNo.13318del
>>13315
感謝 下一次試試看
只能在舊版註冊這個規定真的有點爛
無名19/05/06(一)14:55:46 ID:Nrk5jU4sNo.13338del
大學時只玩過一年
然後同隊的都沒在玩,沒朋友的我也沒玩了
最近發覺自己寫程式感受到樂趣的時候就是玩程式競賽時,就想重來挑戰一下
但又不夠能力...

知道基本的演算法,不過有種力不從心的感覺
應該要怎樣去"練等"?
不斷做codeforces的education題目和參加education round就可以嗎?
每次數字的算式也不太想到...
無名19/05/07(二)01:33:49 ID:tuH/7NDENo.13340del
先講結論好了
我覺得 CF education round 並沒有很 education...
題目很雜, 也不是照技巧整理感覺一般的 div1/div2 或者其它地方的比賽差不多
如果是覺得基礎概念不夠的, 可以去看日本人寫的書:
http://www.drmaster.com.tw/Bookinfo.asp?BookID=PG21319

當基礎知道得差不多以後
常常會碰到的瓶頸是不管再學多少, rating 還是卡在綠色~藍色附近
那是因為個人賽比起演算法知識更要求技巧, 要你設計新的演算法
這裡說的技巧包括數學分析的技巧, 列式的技巧等等
需要分析要舉一反十的題目很多
但要求很多基礎知識, 很難實作的算法題很少
雖然對天才來講這是考他們臨場思考反應
但對凡人如我就只能看一個技巧 多學一個技巧, 慢慢靠經驗撐rating

技巧我看過整理最好的是日本人的blog
https://www.hamayanhamayan.com/entry/2100/01/01/000000
或者是DP技巧集的練習: https://atcoder.jp/contests/dp/tasks?lang=en
照著題單一題一題寫下來也不錯

我是自己跟著月曆慢慢打比賽 賽後看解答就常常會學到新技巧
永遠有學不完的技巧
然後看到新的題目還是永遠不會...唉...
無名19/05/08(三)09:26:58 ID:QMNRvm3INo.13341del
>>13338
我覺得是要習慣力不從心的感覺
覺得很順利的話人人都可以當tourist了...
無名19/05/08(三)13:06:37 ID:OR0v39tcNo.13342del
檔名:1557291997130.jpg-(78 KB, 360x230)
78 KB
咦?有人叫我嗎?
無名19/05/11(六)00:40:37 ID:gQ.d5cCANo.13346del
剛在codeforces討論版看到的
[Tutorial] A way to practice competitive programming — from rating 1000 to 2400+

裡面有介紹哪一個階段要怎麼練
https://drive.google.com/file/d/1J2x8pIYQ3MXANgvzOgBciWd3d79j_Exa/view
https://codeforces.com/blog/entry/66909
無名19/05/11(六)23:26:16 ID:1fFtzlh2No.13347del
這次的atcoder
難得覺得rating要大漲卻unrated了
果然會unrated的只出現在表現好的時候...
無名19/05/11(六)23:53:22 ID:gQ.d5cCANo.13348del
>>13347
上推特看了一下好像情況蠻慘的
因為是企業贊助的比賽
好像要把錢全部退款了
無名19/05/12(日)13:37:30 ID:9uFIX1KQNo.13349del
檔名:1557639450243.png-(97 KB, 807x676)
97 KB
翻譯:最後還是要看數學能力
oh...
無名19/05/13(一)17:42:34 ID:.aaFRoOQNo.13350del
>>13349
2600, 3000太高了
其實只要 rating 到 1700~2000 左右就會開始很有感了
會想 ad-hoc 問題的人頭腦構造真的不太一樣
無名19/06/02(日)03:56:24 ID:.bDPOJjENo.13382del
>>13308
得了吧...其實競賽就是很吃數學能力 並不是這些學校和其他學校的課程安排不一樣 (當然老師資歷、能提供的資源和同儕環境有很大的差別)
最多就是公假放到爽 讓你一個人能夠去圖書館爽爽念


【刪除文章】[]
刪除用密碼: