Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2008-10-13

NextNumber (SRM416 DIV1 Easy)

| 10:59 | NextNumber (SRM416 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - NextNumber (SRM416 DIV1 Easy) - TopCoder煮ブログ

勢いよく Submit したが、System Test で撃沈。凡ミス。

C++ 一位の人の回答がスマートすぎる。

  1. (N & -N) で最下位ビットが分かる
    • 補数表現は最下位ビットが重複する
  2. 最下位ビットを足す
    • 必ず繰り上がりが起きてビット数が同じか小さくなる
  3. ビット数が小さくなったら、減った分だけ加算
    • (1 << num) - 1
    • (例)num が 3 のときは、7(111)

CubeNets (SRM417 DIV1 Medium)

| 18:22 | CubeNets (SRM417 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - CubeNets (SRM417 DIV1 Medium) - TopCoder煮ブログ

サイコロ問題。展開図を回すのではなく、展開図の上をサイコロを転がすとよいようだ。C++ 1位の人は、展開図全面をサイコロごろごろ転がして、全部の面に # がヒットしたら YES を返してる。なるほど…。

YearProgressbar (SRM420 DIV2 Medium)

| 18:57 | YearProgressbar (SRM420 DIV2 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - YearProgressbar (SRM420 DIV2 Medium) - TopCoder煮ブログ

勢いよく書いたが System Test で撃沈。うるう年の時に3月以降なら1日足すところを、if(M > 2 && isLeap(Y)) days++; とやっていた。月は 0 base で保持していたので、3月は 2。M >= 2 としたら成功。こんなしょぼいミスばっかり。

PrettyPrintingProduct (SRM420 DIV2 Hard)

| 23:22 | PrettyPrintingProduct (SRM420 DIV2 Hard) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - PrettyPrintingProduct (SRM420 DIV2 Hard) - TopCoder煮ブログ

上位桁と下位桁を別々に計算すればよい。方針は合っていたが、できる限り多く保持しようとして、long long が桁あふれしてしまった。

64bit で表せる数が 0~1.8*10^19。かけていく数は最大10^6なので、low, high ともに 10^12 ぐらいに留めるべきだった。