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)