ABC045-C たくさんの数式（Atcoder精進記録） - 人並みソフトウェアエンジニアを目指して

Atcoder Beginner Contest 045-C

〇問題
・1以上9以下の数字からなる文字列Sについて、文字の間のうちいくつかに'+'を入れて作ることができる数式の値の総和を求める。
・1<= |S| <= 10

〇方針
・Sの文字の間それぞれについて、'+'を入れるか入れないかの2通り。
・文字の間（'+'を入れることができる箇所）の数はn-1（ n = |S| ）

⇒ $2^{n-1}$ 通りの全探索
⇒今回は、bit探索を利用

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
    char s[11];
    scanf("%s",s);

    int i,j;

    long long ans=0;
    long long tmp;  // ’＋’で分割したものを代入
    for(i=0;i<( 1 << ( strlen(s) - 1 ) );i++){ //　S="125"なら、i=(00)_2～(11)_2まで。
                                            　 //  strlen(s) にすると、i=(111)_2までになる。
        tmp = s[0] - '0';                       //　Sの１文字目を数値に変換して代入
        for(j=0;j<( strlen(s) - 1 );j++){
            if( i & ( 1 << j ) ){       //　例：(i,j)=(0,1) ⇒ (00) AND (10)
                ans += tmp;             //        　　    　⇒ (10) ⇒ 12 + 5
                tmp = 0;                //  分割した分を足して、tmpを初期化
            }
            tmp = tmp*10 + (s[j+1] - '0');
        }
        ans += tmp;　// 最後の分割部分を足す。
    }

    printf("%lld",ans);

    return 0;
}

〇所感
・コンテストでbit探索の問題が出たときは、よくわからなくて理解を諦めていた。今回で理解できたはず。
・'+'によるSの分割方法に苦労した。結局、ASCIIコードを用いて数値に変換することにした。
・String型ほしい……仕事ではJavaを使うし、そのうちC言語から移行するかも。

〇参考記事
・AtCoder 版！蟻本 (初級編)　（問題の選択）
・bit全探索 - whileD'iary　（実装方法）