Challengeのコツ

Challengeのコツ

キーワードに対して脊髄反射でChallengeを考えられるようにするためのメモ.

過去にどんなテストケースで撃墜があったかはTopCoder Statistics - Round Statisticsで見れます.

Combination

n個の中からk個を選ぶという処理.この中で素直に掛け算をしていると100個から100個を選ぶときなどでintのオーバーフローをおこすことがある.

Pascalの三角形などを使って計算途中でオーバーフローしないようにしていても、32bit符号付整数ではC(33,16)まで、64bitではC(66,33)までが限界です

割り算"/"とあまり"%"

それぞれ0で割ると例外が出る.

next_permutation

next_permutationする前にsortしてないと全部の場合がでない.

push_backのやりすぎ

もし10^7とかpush_backしているようなことがあれば例外が飛ぶぽい.push_backはどれだけできる? - Div2から抜けだしたいsuztomoの日記 - TopCoder部

続いているものチェック

文字列の中に特定のある長さの部分文字列が出現しているかは,文字全体をなめるループを出たあとももう一回チェックしないといけない.

例: SRM429 250 Barbaro

INT_MAX越え

INT_MAXは2ではじまる10桁.9^10はINT_MAXを越える.

intとかlongとかdoubleとか

double a = 1 / 2 は 0.0

double a = 1.0d / 2 は 0.5

double a = (double)1 / 2 も 0.5

double a = (double)(1 / 2) は 0.0

long b = 1 << 32 は 0L

long b = 1L << 32 は 4,294,967,296

TLE(Time Limit Exceeded)狙い

brute forceでやってるとか、メモ化してないとか、枝狩りしてないとか。