AtCoder が提供しているABC(AtCoder Beginner Contest)045 C問題をC++で解いてみました。ABC045は、2016年9月11日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 たくさんの数式(Difficulty : 1089)
問題の詳細は、リンク先をご覧ください。
bit全探索を使って文字列を分解します。AtCoder Problems による Difficulty は 1089 でした。
解答案
入力例1を振り返ります。文字列は “125” です。以下の4通りの数式があります。
- 125
- 1+25
- 12+5
- 1+2+5
1と2の間、2と5の間の2か所について、その場所に + を入れる場合と入れない場合の2通りに分かれます。結果的に、文字列の長さ-1の2乗の組み合わせがあります。
C++ プログラム例(ABC045C)
bit全探索ですべての場合を調べます。最後に数字を加える必要があります(24行目)。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
int main()
{
string s;
cin >> s;
int n = (int)s.length() - 1;
ll result = 0;
for (uint bit = 0; bit < (1U << n); ++bit) {
ll t = s[0] - '0';
for (uint i = 0; i < (uint)n; ++i) {
if ((bit & (1 << i)) != 0) {
result += t;
t = s[i + 1] - '0';
} else {
t = 10 * t + (s[i + 1] - '0');
}
}
result += t;
}
cout << result << endl;
return 0;
}
AC(Accepted=正しいプログラム)と判定されました。
最後に
bit全探索を使う典型問題ですが、当時は緑レートでした。
引き続き ABC の問題を紹介していきます。