AtCoder蟻本 初級編 2-1 全探索 ①部分和問題

ARC061 C - たくさんの数式 / Many Formulas (300)

C: たくさんの数式 / Many Formulas - AtCoder Regular Contest 061 | AtCoder

概要

数字のからよりなる文字列が与えられる。
この文字列の文字間に好きなだけの記号を挿入した算式を作成し、その和を計算する。（を挿入しなくてもよい）
全ての和の合計を求めよ。

制約

方針

再帰関数を用いて全探索する。
各文字間に足す記号を入れるか入れないかの情報をビット列として再帰的に生成し、
ビット列が必要な長さになったら実際にその情報に基づき計算を行う。

感想

計算結果を再帰関数の引数や返り値にしながら計算する方法を考えたが、
それだと意外に計算しにくい。

解答

Submission #3829984 - AtCoder Regular Contest 061 | AtCoder

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
string s;
ll ans;
 
void dfs(int d, int u){
	if(d == s.length()-1) {
		ll t = s[0] - '0';
		for(int i = 0; i < s.length()-1; i++){
			if(u & (1 << i)){
				ans += t;
				t = s[i+1] - '0';
			}else{
				t *= 10;
				t += s[i+1] - '0';
			}
		}
		ans += t;
		return;
	}
 
	int b = (1 << d);
	dfs(d+1, u);
	dfs(d+1, u+b);
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> s;
	ans = 0;
	dfs(0, 0);
 
	cout << ans << endl;
}

ABC079 C - Train Ticket (300)

C - Train Ticket

概要

以上以下の数字からなる4桁の文字列が与えられる。
各文字間にとのどちらかを挿入した算式を計算し、その結果がとなるものについて、
その算式を出力せよ。
ただし、与えられた文字列は適切に記号を挿入すれば、その結果が7になるものが存在することが保証される。

制約

問題のとおり。

方針

「たくさんの数式」と同様。

感想

解答

Submission #3830002 - AtCoder Beginner Contest 079

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
string s;
bool answered;
 
void dfs(int d, int u){
	if(d == s.length()-1){
		int t = s[0] - '0';
		for(int i = 0; i < s.length()-1; i++){
			if(u & (1 << i)){
				t += s[i+1] - '0';
			}else{
				t -= s[i+1] - '0';
			}
		}
 
		if(t == 7 && !answered){
			cout << s[0];
			for(int i = 0; i < s.length()-1; i++){
				if(u & (1 << i)){
					cout << '+' << s[i+1];
				}else{
					cout << '-' << s[i+1];
				}
			}
			cout << "=7" << endl;
			answered = true;
			return;
		}
		return;
	}
 
	int b = (1 << d);
	dfs(d+1, u);
	dfs(d+1, u+b);
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> s;
	answered = false;
	dfs(0, 0);
}