月別アーカイブ: 2013年4月

Topcoderメモ

Topcoderの自分用メモです。
適宜追記します。

重要なポイント

Topcoderは.Net Framework 2.0で動いているため、2.0で動くコードにする必要がある。

配列の扱い

配列の初期化、コピー
https://gist.github.com/c611e22c05cb412d8f94
http://smdn.jp/programming/netfx/arrays/2_operations/

文字列の扱い

string型は変更不可なので注意。

  • string1文字の変更
  • string[]をchar[,]に変換

文字列の扱い サンプルコード
https://gist.github.com/abdbca55b14a68fd3bbb

その他

ゲームの必勝法系
* 相手のマネをする戦略に注目する

ニム

ルール:N個の山のどれかから任意の数を取ってよい。最後の石を取った方の勝ち
必勝法:各山のXORをとり、=0なら負け、!=0なら勝ち
証明:勝ちの状態からは負けの状態に必ず移すことができる(一番上のビットが立っている山から調整して取得)、逆に負けの状態からは勝ちの状態に必ず移る
最後の石を取った方が負けのときは?

メモ

intの範囲、longの範囲

int 符号付き 32 ビット整数 (-2^31 ~ 2^31)
2.147 * 10^9 ⇒ -2,147,483,648 ~ 2,147,483,647
long 符号付き 64 ビット整数(-2^63 ~ 2^63) 
9.223 * 10^18

メモリ制限

メモリ制限…64MB(実質50MB?)
int =4byte、int[1000][1000]で4Mbyte。結構厳しい。
100万個程度であれば、int型は問題ないが、連想配列などは注意
1000万個のint型は注意

実行時間

制限時間は2秒。 1秒に対して、

  • 1,000,000→余裕
  • 10,000,000→たぶん大丈夫
  • 100,000,000→おそらく厳しい
    (プログラミングコンテストチャレンジブックより)

落とし穴集

  • 計算した結果がintの制限を超えた
    ダメな場合の値として100000などを入れていた時に、その値を使ってしまい100000*10000などとなるケース
  • doubleで計算するべきものをintで計算していた
    計算最初の値を(long)や(double)でキャストしましょう
    int A, int Bとあるときには、(long)(A * B) ではダメで、(long)A*B とする
  • メモリの制限を超えてしまった
  • オーダーを超えてしまった
  • メモ化をし忘れていた
  • char型の数値を扱うときに、’0’するのを忘れていた
  • http://apps.topcoder.com/wiki/display/tc/General+SRM+Algorithm+FAQ
  • Challengeのコツ http://topcoder.g.hatena.ne.jp/keyword/Challenge%E3%81%AE%E3%82%B3%E3%83%84