初心に立ち帰り、最近、問題解決力を鍛える！アルゴリズムとデータ構造 という本を読み始めた。
At Coder の問題をベースとして、アルゴリズムの紹介とそれに合ったデータ構造を解説した本である。
3月からアルゴリズム系の仕事が始まるので、ちょっと復習のつもりで買ってみた。
が、３章の問題からつまづいています。特に 3-7
数値文字列（例えば 1356）の途中に + 記号を入れ、和を計算する。
+記号は0個以上で文字列の間であれば任意の位置に入るものとする。
全ての場合についての総和を計算する。
例えば、135なら 135, 1+35=36, 13+5=18, 1+3+5=9 で総和は 198 となる。
2進数で、+記号を入れる位置を1、それ以外を0とすれば0〜2^(文字列長-1)-1が取り得る + 記号の位置であることはすぐ分かる。ビット表現から文字列を分割するコードを思いつくのに、ことの他時間がかかってしまった。
直感的に実装すると、以下のようになりそう。
int subsum(const string &s, int i, int psz) {
int sum = 0;
int ssum = int(s.at(0) - '0');
int x = psz;
for (int idx = 1; idx < s.size(); x >>= 1, idx++) {
if (x & i) {
sum += ssum;
ssum = 0;
} else {
ssum *= 10;
}
ssum += int(s.at(idx) - '0');
}
sum += ssum;
return sum;
}各iについて、この関数の結果を足し算すれば良いから、
int main() {
string src;
cin >> src;
int sz = src.size();
int sum = 0;
int psz = int(pow(2, sz - 1));
for (int i = 0; i < psz; i++) {
sum += subsum(src, i, psz >> 1);
}
cout << "Total sum:" << sum << endl;
return 0;
}となる。部分和を求める部分がもう少しカッコ良く書けないかと思うのだが、今のところ思いつかない。
コメントを残す