ioi2010-misc-guide.txt

* IOI2010 アルゴリズム以外の周辺まとめ by qnighy
あくまでqnighyの習慣にあわせたまとめであることに注意。

** RunCについて
RunCを用いたprintfデバッグは困難である。
デバッガはgdbとdddのみが用意されているが、これらは使いづらい。Emacs使いなら何とかなるかもしれないが、僕はEmacs使いではない。
そのため、開発中は自前でコンパイルし、提出前にRunCで動作確認するのが良いと考えられる。(開発用とRunC用のディレクトリを分けたほうがいいかもしれない)
以下はMakefileのサンプルである。

CXXFLAGS = -O2 -Wall -Wextra -Wno-unused-result -g
LDFLAGS = -lm
all: gameshow
gameshow: jill.cpp jack.cpp grader.cpp
    $(CXX) $(LDFLAGS) $(CXXFLAGS) -o $@ $^

なお、-Wno-unused-resultはscanf()の戻り値を使用しないことに対する警告を抑止するものであるが、
IOI2010のコンテスト形式を考えるとこのオプションは不要かもしれない。

** Valgrindについて
Segmentation faultなど、メモリ関連のエラーに遭遇した場合は、
迷わずValgrindを使用するべきである。

./gameshow < gameshow.in.1 を
valgrind ./gameshow < gameshow.in.1 に変えるだけで実行できる。

メモリの境界範囲外アクセス、メモリリーク、未代入の変数の使用、などメモリ関連のエラーの多くを検出できる
ので、提出前にも実行しておくとよいかもしれない。

ただし、これを有効に使うためには、コンパイルオプションに-gが入っている必要がある。
そのためにも自前でコンパイルすることを推奨する。

それから、スタック上に確保された配列の範囲外アクセスの検出は苦手らしい。極力ヒープに確保したほうがよいと考えられる。
僕は以下のようにすることにした。
bool *vis = new bool[n];
int (*tbl)[1000] = new int[n][1000];
delete[] tbl;
delete[] vis;

** Bashについて
Bashのプロンプトが長ったらしくてたまらない。以下のコマンドを実行するべきである。
PS1='\w\$ '
シェル変数PS1に文字列を代入している。ダブルクオートではなくシングルクオートを使うこと。
イコールの前後に空白を挟んでもいけない。
\wはカレントディレクトリ、\$はプロンプトの直前の記号$を表す。

なお、これを恒久的に使用する場合は、このコマンドを
~/.bashrc
の最後に追加すればよい。

** Vimについて
Vimを使用するのは僕だけかもしれないが、もしVimを使うのであれば
cp /usr/share/vim/vim72/vimrc_example.vim ~/.vimrc
するとvimrcの設定が簡単になる。

** geditについて
geditをコマンドライン(bash)から起動する場合は以下のようにする。
gedit fruits.cpp &
最後の&は重要。

** キーボードについて
IOI2010で用意されているキーボードは以下である。
http://www.ioi2010.org/images/keyboard.jpg
BackspaceとEnterの位置が、日本で流通してるものと違うことに注意すること。
キーが1つ少ないことがわかると思う。

このため、このキーボードをJP配列にして使うと、打てない文字が発生する。
(tos曰く、アンダースコアが使えなくなるらしい)

すなわち以下の選択肢がある。
- US配列でがんばる。
- キーボードを持ちこむ。
- アンダースコア禁止ルール
STL使いならアンダースコア禁止は辛いと思われる。

** コーディング規約について
僕は以下のようなコーディング規約を採用している。参考程度に。

- 空白等のルールはPEP8を参考に。
- 配列は基本的に配列newで生成
- 自分で定義するクラスは全てUpperCase
- typedef long long int64_t;
- mainのシグネチャは、int main()
- ブレース{}の直前は改行せず、空白を挿入
- 最初にインクルードするのはcstdioとalgorithmの2つだけ
- 配列はがんばって複数形の名前をつける
- 配列サイズをあらわす変数は、points_sizeとかそういう名前にする
- 変数名の長さは、そのスコープや使用頻度から適当に判断する
- forの空白: for(int i = 0; i < 10; i++) {}
- 同様に、それなりに空白は入れる
- あとは臨機応変

** プログラミング言語について
PythonとPerlはインスールされていると考えられる。(RubyやJavaは入ってないと考えられる。残念。)
必要になることは滅多にないと思うが、使えると便利である。

また当然ながらシェルスクリプトは使用可能である。

** プロファイラについて
(プロファイラ…時間のボトルネックを調べるツール)
「最強のプロファイラ」であるoprofileはさすがにインストールされていないが、
gprofとgcovがインストールされている。

gprofは、関数ごとに合計何秒消費したかを計測する。
gcovは、行ごとに何回実行されたかを計測する。

gprofはbinutilsに、gcovはgccに同梱されているので、まず入っていると仮定していいだろう。
ただ、使う必要があるかは疑問である。

*** gprof
gprofを使う場合、コンパイルオプションに-pgを付ける。
プログラムを実行したあと、
gprof 実行ファイル名
で、関数ごとのプロファイル結果が出る。

*** gcov
gcovを使う場合、コンパイルオプションに-profile-arcs -test-coverageを付ける。
プログラムを実行したあと、
gcov ソースコード名
で、nanka.cpp.gcovのようなファイルが生成される。

** 禁止事項について
pingを飛ばしたりするとヤバいので気をつけること。(頭にブーメランが刺さった状態で)
あとsudoやsuも禁止。
ブラウザのURLバーは使えないようにしたほうがいいかもしれない。
alias ping=ls
alias sudo=ls
alias su=ls
とかやるといいかもしれない。

** ulimitについて
bashの組み込みコマンドでulimitがあり、プログラムの使用する資源に制限を加えることができる。
*** スタックの制限を一時的に外す
ulimit -s unlimited
*** メモリに制限を加える
ulimit -v 64000
*** CPU時間に制限を加える
ulimit -t 3

これらはulimitコマンドを実行したシェルの中で有効である。

また、CPU時間はtimeで測定する。
time ./command
"user"とある項目がCPU時間である。

** プログラムの戻り値について
プログラムは戻り値をもつ。実行結果が0の場合成功、それ以外の場合失敗とされる。
プログラムを実行した「直後」に
echo $?
とするとわかる。

** sudoについて
sudoは禁止のようである。危ないところだった。
/etc/sudoersでシステム的に禁止してほしい。

** 作業に便利なコマンド
*** head
出力の先頭を抽出する。デフォルトでは10行。
./program | head -n 5

makeのエラーとかは標準エラーに出力されるので以下のようにしないといけない
make 2>&1 | head -n 15

*** tail
出力の末尾を抽出する。デフォルトでは10行。

*** less
出力を閲覧する。
./program | less

jkもしくは矢印キーで上下移動。
qで終了。

*** grep
出力を検索する。
./program | grep 999