Topcoder

topcoder.png

使えそうな関数

問題のカテゴリー

カテゴリーと書いてありますが、ひとつの問題に複数のカテゴリーがつくことがあります。つまり、タグのようなものです。
カテゴリー 概要 関連ページ
Advanced Math
Brute Force 全探索
Dynamic Programming 動的計画法
Encrypt/Compression
Geometry 幾何学の問題
Graph Theory
Greedy 貪欲法
Math
Recursion 再帰
Search
Simple Math
Simple Search Iteration
Simulation もしこうだったらどうなるか、分類しがたいその他というかんじ
Sorting
String Manipulation 文字列操作
String Parsing 文章区切り系,というか文章解析系 ある特定の文字で、文字列を分割するには?,文字列⇔数値
Iteration

問題の難易度

Division OneとTwoがあります。Division OneはTopCoder Ratingが1200以上の人だけ行けるので、
Division Oneの問題のほうがTwoより難易度が高いです。
Divの中でもLevel 1,2,3がありますが、1が最も簡単で、3が最も難易度が高いです。
というのが大体の分類ですが、それだけでは問題の数が多すぎて絞れません。
Pointの問題の難易度の指標にはなるけれど、Pointが低いのに難しい問題も存在します。
難易度を見分ける上で一番良いのは正答率です。
正答率98%の問題とかは、とても簡単で、問題文に何をすればいいかほぼ手順が書いてあるよね?レベルの問題です。初心者や久しぶりにソースコード書くからリハビリしたい人などにおすすめ。

過去問で練習するには?

TopCoder Arenaの中にPractice Roomというのがあります。

練習環境

初心者にはコードアリーナだけで練習するのは難しい。。
途中過程をデバッグしたりしたい。
私のお気に入りの方法は
Visual Studio Code内でコマンドプロンプト(「端末」と呼ばれている)を開いて(Ctrl+@で切り替えられる)
まず立ち上げ時に

vcvars32.bat

と打つ。これはコマンドプロンプトでC++のコンパイルをするのに必要な環境変数を一気に設定してくれるバッチファイル。
Visual Studioのインストールフォルダの下のVC/bin とか書いてあるところにあるはず。

cl ファイル名.cpp

でコンパイル

ファイル名

で実行。を毎回やること。デバッグは標準出力(cout)でやっている。
インテリセンスとかで関数のサジェストはでないけど、Visual Studioより軽くてTopCoderの練習には良いと思う。

Web ArenaかJavaAppletのArenaか

しばらくWebArenaでやってみたけど、めっちゃ重かった。重くなったらいったんブラウザを閉じたら治る。
JavaAppletのArenaは簡単な問題だけピックアップするのが面倒くさい。問題を好きな順番に並べて選ぶということができないのが欠点。
本番ではいいかもしれないけど。

練習サイクル

  1. まずは自分で考えて問題を解く。
  2. 提出(Submit)
  3. Run System test
  4. 合ってても、あってなくても、他の人はどんなコードを書いたのか見て、より良いコードが書けなかったのか考察する

他の人の答えを見るには?

problem archivesのページのdetal->Top submission ->view
で見れます。

どの言語が良いか?

C++ 素早いコーディングを追及すると最終的にマクロ合戦になってしまうのが私は見栄え的に好きではない。。。

コツ

Map<Integer,Integer>を使うくらいなら2次元配列

その方が早いし、便利!

複数やり方がある場合、選ぶのは「覚えやすいほう」

とにかく手早くコーディングするのが大事。
topcoderの簡単な問題の場合は、どんでもなく大きな数のことや、実行速度のことをそんなに考えなくてもいいので、
覚えやすいやり方を覚えて、すぐ何も調べずに書けるようにすることが大事。

可能な限り分岐を減らす

そのほうがコードが見やすくなってミスが減るからだ。

減らす方法

min,max関数を利用

よく使うクラス・関数

Java C++ Python
インクルード #include "bits/stdc++.h"
文字列 String string
配列 vector<int>
for文 for(int i=0;i<n;i++){ for(int i=0;i<n;i++){
foreach for (string a : array)
ソート sort(v.begin(),v.end()) sorted(v),or v.sort()
検索 find(v.begin(),v.end()) or string.find("文字列")
合計 accumulate(v.begin(),v.end(),0) sum(v)
min,max min(a,b);max(a,b)
文字列の一部を切り取る str.substr(pos,num) str[begin:end]
文字列を継ぎ足す str += "文字" str += "文字"
配列の継ぎ足し v.push_back()
文字列を数値へ変換 文字列.parseInt(); stoi(文字列)
charの数字をint数字へ変換 i = c-'0'
重複排除 set<int> s; s.insert(要素) set(list)
大文字・小文字変換 toupper(c),tolower(c)
map 2次元配列利用がおすすめ

制限

実行時間
1テストケースにつき2秒
メモリ使用量
64MB以下

メモリ使用量の見積り方

  • 100万個程度であれば、int型の配列は気にせず作っても問題ない。連想配列などはここを超えたら注意する
  • 1000万個のint型配列を作る必要がある場合は、空間計算量に注意する。

お勧め本

Bibliography
3. 最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイド….小難しいアルゴリズムがわかりやすい口調で書いてあって頭にスッと入りやすいです。

アリーナの使い方

MacでもWindowsでもCtrl+cでコピーです command+cではありません

ChromeだとJava Web Startが開けない???

tcd.png
過去の問題を解くのに必要。
http://cm55.com/GS/dev/help/network/terminal/trouble.html
http://www.ehow.com/how_12036296_configure-chrome-open-jnlp-files.html

サポートサイト Wikidot.com