AtCoder

ABC045 C問題(たくさんの数式)を解く

AtCoder_ABC045_C

AtCoder が提供しているABC(AtCoder Beginner Contest)045 C問題をC++で解いてみました。ABC045は、2016年9月11日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 たくさんの数式(Difficulty : 1089)

問題の詳細は、リンク先をご覧ください。

ABC045 C問題 たくさんの数式

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 の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA