本文根據(jù)經(jīng)典的TC教程完善和改編。
TopCoder：http://www.topcoder.com/
基本規(guī)則
TopCoder的比賽類型很多，最常見的是周賽SRM（Single Round Match），另外還有TCHS SRM（TopCoder High School SRM，題目和SRM一樣，僅限中學(xué)生參加，參賽者水平較低，據(jù)說(shuō)漲rating很容易），馬拉松（Marathon Matchs），還有TCOpen（每年兩次的大比賽）之類的比賽。因?yàn)榇蠖鄶?shù)人都在做SRM，所以本文介紹的TC比賽即為SRM。
SRM的規(guī)則總結(jié)起來(lái)就是一句話：75分鐘做完3道難度遞增的題。
TC的每個(gè)用戶（handle）都有自己的積分（rating），從0-3000+不等。成績(jī)?cè)胶茫謹(jǐn)?shù)越高。
積分與顏色的對(duì)應(yīng)為：白色——未參賽（unrated）；灰色——0~899；綠色——900~1199；藍(lán)色——1200~1499；黃色——1500~2199；紅色——2200+。另外排名最高的幾個(gè)人在TC客戶端中會(huì)變成紅色靶子圖標(biāo)。
比賽分為兩個(gè)Division，Div I和Div II。白色灰色和綠色的參加Div II，藍(lán)色黃色和紅色的參加Div I。Div I的題要比Div II難許多，一般DivII的最后一題和Div I的第一或第二題是一樣的。無(wú)論是Div I或Div II。三道題目的Score一般為250, 500和1000。
TC的計(jì)分規(guī)則很詭異，可以見http://www.topcoder.com/wiki/display/tc/Algorithm+Competition+Rating+System，但基本是沒人看的懂。不過(guò)，TC積分規(guī)則的基本思想很簡(jiǎn)單。
首先是SRM每道題的計(jì)分規(guī)則。題目從打開開始計(jì)時(shí)，隨著時(shí)間的流逝，你這道題目可能得到的分?jǐn)?shù)也越來(lái)越少。不過(guò)分?jǐn)?shù)減少的速率會(huì)逐漸變慢（有人說(shuō)是先快后慢再快再慢，我不清楚到底哪個(gè)是對(duì)的，不過(guò)總體趨勢(shì)是越來(lái)越慢），一般1000分的題目在降低到300分的時(shí)候就基本不會(huì)再下降太多了。每道題點(diǎn)擊Submit才算正式提交，如果Submit之后發(fā)現(xiàn)錯(cuò)誤，還可以再次點(diǎn)擊Submit修改提交，不過(guò)這樣會(huì)扣除這道題一定的分?jǐn)?shù)。
其次是TC的計(jì)分規(guī)則。復(fù)雜的數(shù)學(xué)公式很難看懂，但大概的計(jì)分思想是：根據(jù)此次比賽的得分算出一個(gè)這次比賽的rank，然后和以前的rank做比較，求出一個(gè)期望的rank，再根據(jù)這個(gè)期望的rank調(diào)整rating。而有時(shí)也會(huì)出現(xiàn)考得很砸但依然漲rating的情況，不過(guò)總體來(lái)說(shuō)TC的計(jì)分公式是十分穩(wěn)定的。
運(yùn)行環(huán)境
TC的客戶端是一個(gè)Java程序，所以需要JRE（Java Runtime Environment）或者JDK（Java Development Kit）來(lái)運(yùn)行。如果平時(shí)不寫Java程序的話，裝JRE就可以了。畢竟JDK比JRE大一個(gè)數(shù)量級(jí)，下載慢。安裝照著提示完成就行了。推薦使用1.4.1以后的版本，因?yàn)閹Я薺ava web start，可以快速登陸。具體方法下一部分講。
JRE下載地址（中文）：http://www.java.com/zh_CN/download/index.jsp
注冊(cè)
原文在注冊(cè)的地方?jīng)]有詳細(xì)說(shuō)明，但很多人似乎對(duì)注冊(cè)都有疑問(wèn)。所以這里我來(lái)注冊(cè)一個(gè)小號(hào)，并通過(guò)整個(gè)過(guò)程講解如何注冊(cè)。
首先打開http://www.topcoder.com/tc（本文后面TopCoder的主頁(yè)都指這個(gè)網(wǎng)址），然后點(diǎn)擊右上角的Register Now（沒看到？你可能看到了一個(gè)Login，目光向下挪一點(diǎn)，那個(gè)紅底白字的“Register Now”就在下面）。接下來(lái)會(huì)彈出http://www.topcoder.com/reg這個(gè)頁(yè)面，因?yàn)槲覀円獏⒓覵RM，所以選擇第一個(gè)，Competition Registration。如果要參加TCHS可以選擇第二個(gè)High School (Secondary School) Registration。這些以后都可以更改（這里沒有選的如果以后要選上，只需要更新個(gè)人設(shè)置并挑勾；如果選上的要撤銷選擇則需要點(diǎn)一個(gè)“Unregister”的鏈接）。這里選擇項(xiàng)目的多少和后面的頁(yè)面需要填寫內(nèi)容的多少相關(guān)，本文以只選擇第一項(xiàng)為例。
需要填寫的項(xiàng)目和對(duì)應(yīng)的中文翻譯如下：
* Given Name: 名
* Surname: 姓
* Address1: 地址1
Address2: 地址2
Address3: 地址3（如果一行寫不開，就在三行中分別寫）
* City: 城市
State (US Only): 地區(qū)（不在美國(guó)就不用選）
Postal Code: 郵編
Province: 省
* Country: 國(guó)家
* Country to represent: 代表國(guó)家（不知道啥意思，中國(guó)人兩個(gè)都填China就行）
* Timezone: 時(shí)區(qū)（選Asia/Chongqing）
Phone Number: 電話號(hào)碼
* Email Address: 電子郵件
* Confirm Email Address: 確認(rèn)電子郵件地址（就是把電子郵件地址重新打一遍）
Email Notifications: 郵件提醒（就是它給你發(fā)郵件提醒什么東西）
- Algorithm Competitions 算法比賽，就是SRM和TCOpen
- Software Development Opportunities 貌似就是有軟件開發(fā)的項(xiàng)目就告訴你
- Employment Opportunities 工作機(jī)會(huì)
- TopCoder News & Events 新聞
* Enable Member Contact: 允許成員聯(lián)系（似乎就是說(shuō)是不是讓別人在TC上能找到你）
* Show / hide earnings: 顯示/隱藏收入（大概是說(shuō)別人是不是能看到你賺了多少錢，TC的比賽可是有錢賺的）
* User Name: 用戶名（下面的話提醒你一定不要填錯(cuò)，因?yàn)樽?cè)多個(gè)用戶是不符合規(guī)定的。據(jù)說(shuō)有人因?yàn)閯e人在TC客戶端和他打招呼說(shuō)“怎么你拿小號(hào)上了”，那個(gè)人的號(hào)就被封了）
* Password: 密碼
* Confirm Password: 確認(rèn)密碼
* Secret Question: 密碼找回問(wèn)題（找回密碼時(shí)需要回答這個(gè)問(wèn)題，注意至少要8個(gè)字符長(zhǎng)，而一個(gè)中文字似乎算一個(gè)字符，所以最后可能要打幾個(gè)問(wèn)號(hào)補(bǔ)齊長(zhǎng)度）
* Secret Question Response: 密碼找回問(wèn)題答案
Quote: 座右銘，就是個(gè)簽名檔之類的東西
* Student/Professional: 學(xué)生/職業(yè)程序員
* = required 帶*的項(xiàng)目必填
填寫之后點(diǎn)Term of Use下面的I Agree，再點(diǎn)Submit，完成提交。除了用戶名別的以后似乎都可以改。
接下來(lái)進(jìn)入Demographics頁(yè)面，這個(gè)大概相當(dāng)于一個(gè)注冊(cè)用戶情況調(diào)查。
* Age : 年齡
* Gender : 性別（Male男，F(xiàn)emale女）
* Ethnic Background : 民族背景（似乎選Asian or Pacific Islander就行吧……）
* Primary Interest in TopCoder : 在TC的主要興趣，看不懂的就選第一個(gè)吧，那個(gè)是說(shuō)你的興趣在獎(jiǎng)金……
* Shirt Size : T-Shirt大小（有的比賽會(huì)給排名前N的選手發(fā)T-Shirt，這里你需要選擇適合自己的大小，如果選最后一個(gè)說(shuō)明你不想要T-Shirt，人家也不發(fā)你了。TC的T-Shirt還是挺好看的，比AStar的好）
* College Major : 大學(xué)的專業(yè)
* College Major Description : 這個(gè)不知道啥意思，隨便填點(diǎn)東西就行……
* Degree Program : 學(xué)位（從上到下分別為：準(zhǔn)學(xué)士，學(xué)士，碩士，博士，中學(xué)生）
* Graduation Year : 畢業(yè)年份
* Graduation Month : 畢業(yè)月份
* Clubs / Organizations : 組織（一般選None，可以按住Ctrl點(diǎn)鼠標(biāo)多選）
Other Clubs / Organizations : 其它組織
* School: 學(xué)校（點(diǎn)Choose School選擇學(xué)校，可以搜索，不過(guò)為啥shanghaijiaotong university才2個(gè)人注冊(cè)？！）
* Show / hide my school: 顯示/隱藏我的學(xué)校
GPA: 不懂的自己百度去……
GPA Scale: 同上
Resume: 簡(jiǎn)歷
* How did you hear about TopCoder?: 你怎么知道的TC，如果選了“Member Referral”的話，需要填寫那個(gè)人在TC的用戶名（歡迎填寫sqybi~）
* = required
點(diǎn)Submit，進(jìn)入Confirm頁(yè)面，確認(rèn)信息。如果有誤可以點(diǎn)Edit修改，否則點(diǎn)最下面的Confirm提交。
接下來(lái)進(jìn)入Success，提示你已經(jīng)發(fā)送一封郵件到你的郵箱中，你必須去點(diǎn)擊里面的鏈接激活用戶。激活之后就可以使用這個(gè)用戶了。
登錄
登錄的方法一般都是使用Java Web Start。
在TopCoder主頁(yè)（http://www.topcoder.com/tc）最下方有一段話，第一句是“Load the Arena as an Applet or as a Java Web Start Application”。點(diǎn)“Java Web Start Application”，就會(huì)自動(dòng)下載登陸需要的文件（一個(gè)jnlp格式的文件，本機(jī)裝了JRE/JDK才能打開）。經(jīng)測(cè)試在IE7下這個(gè)鏈接似乎不管用，在Firefox 3下正常。
然后運(yùn)行下載下來(lái)的jnlp文件，就打開了TC客戶端。第一次運(yùn)行和有更新的時(shí)候會(huì)自動(dòng)下載安裝程序，等待即可，很快。
在我這里有時(shí)會(huì)提示“語(yǔ)法錯(cuò)誤”，但沒有任何影響，點(diǎn)“確定”就可以。啟動(dòng)可能會(huì)慢一些，耐心等待。
然后輸入用戶名密碼，在Connection的地方選合適的登錄方式（一般Direct就行，如果不行的話可以試試別的或者用AUTODETECT自動(dòng)檢測(cè)），在PROXY處設(shè)置代理，點(diǎn)GO登陸。這時(shí)可能還會(huì)提示語(yǔ)法錯(cuò)誤，再確定就行，這個(gè)也沒有什么影響。
界面
下面的圖們來(lái)自原文，很經(jīng)典，不打算改動(dòng)了。請(qǐng)使用等寬字體瀏覽。
主界面：
———————————————————————–
| Advertisements…………. |
———————————————————————–
| Main | Lobbies | Options | Practice Rooms | Active Contests | Help ||
———————————————————————–
| | Clock | |
———————————————————————–
| Rating Key | Who’s here | Chat Area |
| . | | |
| . | | |
| . | | |
| . | | |
| . | | |
|————| | |
| MESSAGES | | |
|————| | |
|LEADER BOARD| | |
|————| | |
| | | |
| | |——————————————-|
| | | >>_______________________________________ |
———————————————————————–
Advertisements 廣告。
菜單項(xiàng):
- Main里可以看在線名單和找人。
- Lobbies基本用不著，因?yàn)橛脩粢话愣荚贑hat Room 1。
- Options里是一些選項(xiàng)和顏色設(shè)置。
- Practice Rooms里有大量的練習(xí)，都是以前比賽的題目
- Active Contests只有有比賽的時(shí)候才有用，顯示當(dāng)前正在進(jìn)行和將要進(jìn)行的比賽以及比賽注冊(cè)之類的東西。
- Help里是….不用說(shuō)了吧。
Rating Key: handle的顏色是隨著積分而改變的，這里顯示了積分與顏色的關(guān)系。
MESSAGES: 比賽的時(shí)候這里有注冊(cè)提示和clarification。
LEADER BOARD: 看每個(gè)room的最高分。
Who’s here: 當(dāng)前room里的人。
Chat Area: 聊天。
練習(xí)
在Practice Rooms里隨便選擇一個(gè)room就可以進(jìn)入practice了。
界面與主頁(yè)面稍有變化，但基本相同，略去不畫。主要的變化就是Who’s here分成了兩塊，多了一塊Who’s assigned。這塊顯示的是誰(shuí)被分到了這個(gè)room。因?yàn)槭蔷毩?xí)區(qū)，所以只要是在這里打開過(guò)題的都算是assigned。而在正式比賽中room是由TC分配的。這里顯示的是被分配到這個(gè)room的人。界面上還有一個(gè)變化是Chat Area頂上多了三塊。最左邊的是一個(gè)下拉菜單。里面有三個(gè)分值，選擇后就可以打開相應(yīng)的題目。中間的summary可以看這個(gè)room里每個(gè)人的提交情況。
在practice room里只有coding phase。提交后要判的話需要自己選擇Practice Options（多出來(lái)的菜單項(xiàng)）里的Run System Test。
比賽
每次比賽(除了1年兩次的大賽)都需要在賽前3小時(shí)-5分鐘之間登陸注冊(cè)方可參加，注冊(cè)需要在Active Contest菜單中，選擇你要參加的那個(gè)比賽，再選擇Register。注意比賽前5分鐘注冊(cè)停止，這時(shí)候如果沒有注冊(cè)就不能參賽了。而注冊(cè)了沒有打開題目也視為沒有參賽，rating不變動(dòng)。
然后TopCoder開始根據(jù)每個(gè)人的rating分配room，一般每個(gè)room都有高手和菜鳥，只不過(guò)如果你的rating高，和高手分在一起的概率高一些（當(dāng)然也不一定是這樣，比如我上次就和yuhch大牛分在了一起……）
分配完成后，Active Contest菜單中Register一項(xiàng)變成Enter。選擇后可以直接進(jìn)入你被分配到的room。Active Contest菜單最下面還有一項(xiàng)暗色背景的Room子菜單，可以進(jìn)入各個(gè)room溜達(dá)。
進(jìn)入自己room的時(shí)候一般離開始只有3分鐘左右，靜一下心就可以直接開始比賽了。coding phase的過(guò)程與practice基本相同。注意每題的得分是和用的時(shí)間相關(guān)（見前面的計(jì)分規(guī)則），而時(shí)間是從你打開該題開始算的。所以一題做完后可以不急著打開下一題，先放松一下。
75分鐘的coding后是5分鐘的intermission，這段時(shí)間是用來(lái)休息和聊天的。
然后就是最刺激的15分鐘challenge phase，也就是通常說(shuō)的cha人。打開summary，雙擊別人的各題Score可以打開那題的程序，如果覺得有錯(cuò)誤就可以點(diǎn)左下的Challenge然后輸入你認(rèn)為他會(huì)錯(cuò)的輸入數(shù)據(jù)，如果輸入數(shù)據(jù)合法那么系統(tǒng)會(huì)用標(biāo)程的輸出和這個(gè)程序的輸出對(duì)比，如果出現(xiàn)不同則cha人成功。成功的話你能得到50分，對(duì)方該題分?jǐn)?shù)為0；而如果失敗了，你會(huì)被減去25分。每個(gè)程序只能成功被cha一次，也就是說(shuō)，如果有人cha掉了這個(gè)程序，你就不能再次cha。但是一個(gè)人可以cha某個(gè)程序很多次，直到這個(gè)程序被cha掉或者你放棄。
Challenge結(jié)束后就是System Test。這個(gè)過(guò)程一般比較慢，可以先走開做其他事，過(guò)20分鐘再回來(lái)看結(jié)果。System Test中的測(cè)試數(shù)據(jù)有兩種：一種是出題者準(zhǔn)備的測(cè)試數(shù)據(jù)，一種是成功cha掉別人的數(shù)據(jù)。所以，TC中很少出現(xiàn)有bug的程序能通過(guò)System Test的情況。
結(jié)果出來(lái)后再過(guò)一段時(shí)間，就可以看到一系列message,比如rating更新了，新的practice room建好了以及可以通過(guò)主頁(yè)查看這次比賽的數(shù)據(jù)了。這時(shí)比賽就宣告結(jié)束。
注意事項(xiàng)
1.在TC主頁(yè)（http://www.topcoder.com/tc）上可以看到Next SRM，這是下次SRM的時(shí)間。注意我們的時(shí)間與他們剛好相差12小時(shí)，因此若時(shí)間是7月9日9:00 PM的話，這里是7月10日9:00 AM。還有要注意的是美國(guó)有夏令時(shí)，非夏令時(shí)的時(shí)候，還要再加1小時(shí)，就是7月10日10:00 AM。
2.Practice Rooms里寫的程序只要點(diǎn)SAVE就可以保存，下次login的時(shí)候還可以看到，但是比賽時(shí)候的程序必須Submit才可以在coding phase結(jié)束后保存(coding phase結(jié)束前還是只要SAVE就可以的)。
3.若想cha別人的程序，自己必須是正分(0分也不行)，所以若沒有一題有正確的程序但有很好的數(shù)據(jù)的話，隨便交一道看上去正確的程序，然后在challenge的時(shí)候快下手，就可以賺到了。
4.客戶端自帶的編輯器只有基本的編輯功能和編譯及測(cè)試功能，所以若覺得不方便的話可以使用parser和plugin，TC主頁(yè)最下面有plugin的連接。每個(gè)plugin都有詳細(xì)說(shuō)明文檔，這里不再贅述。
5.TC的FAQ：http://www.topcoder.com/?&t=support&c=index
6.最后一條，千萬(wàn)不要作弊，會(huì)有嚴(yán)重的后果。
SRM的輸入輸出
SRM是不用標(biāo)準(zhǔn)或文件輸入和輸出的，只要寫一個(gè)類的一個(gè)成員函數(shù)。也就是說(shuō)，你需要編寫的并不是一個(gè)完整的程序，而是一個(gè)類。
輸入是成員函數(shù)的參數(shù)，輸出用return，所以經(jīng)常需要STL中的vector和string。
因?yàn)門C的系統(tǒng)并不測(cè)試標(biāo)準(zhǔn)輸出，所以標(biāo)準(zhǔn)輸出可以當(dāng)調(diào)試用。
下面以SRM 413 Div 2的1000分題目介紹程序的寫法。
題目如下（選擇不同的語(yǔ)言，題目描述會(huì)略有不同，本文以C++為例）：
Problem Statement
NOTE: This problem statement contains subscripts that may not display properly if viewed outside of the applet.
Let’s consider an infinite sequence A defined as follows:
A0 = 1;
Ai = A[i/p] + A[i/q] for all i >= 1, where [x] denotes the floor function of x. (see Notes)
You will be given n, p and q. Return the n-th element of A (index is 0-based).
Definition
Class:
InfiniteSequence
Method:
calc
Parameters:
long long, int, int
Returns:
long long
Method signature:
long long calc(long long n, int p, int q)
(be sure your method is public)
Notes
- [x] denotes the floor function of x which returns the highest integer less than or equal to x. For example, [3.4] = 3, [0.6] = 0.
Constraints
- n will be between 0 and 10^12, inclusive.
- p and q will both be between 2 and 10^9, inclusive.
Examples
0)
0
2
3
Returns: 1
A[0] = 1.
1)
7
2
3
Returns: 7
A[0] = 1; A[1] = A[0] + A[0] = 2; A[2] = A[1] + A[0] = 2 + 1 = 3; A[3] = A[2] + A[1] = 3 + 2 = 5; A[7] = A[3] + A[2] = 5 + 3 = 8.
2)
10000000
3
3
Returns: 32768
3)
256
2
4
Returns: 89
4)
1
1000000
1000000
Returns: 2
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
下面是我寫的一個(gè)錯(cuò)誤算法的程序，僅供參考格式用：
#include <string>
#include <vector>
class InfiniteSequence {
public:
long long calc(long long n, int p, int q) {
if (n == 0)
return 1;
else
return calc(n/p, p, q) + calc(n/q, p, q);
}
};
轉(zhuǎn)自：http://sqybi.com/blog/archives/25