noyのブログ

プログラミングとかゲームとか

AtCoder Beginner Contest D問題ジャンル分け

ダブリング

D: 阿弥陀 - AtCoder Beginner Contest 013 | AtCoder
別解:巡回置換

セグメントツリー | Binary Indexed Tree

D: プレゼント - AtCoder Beginner Contest 038 | AtCoder

ARC016 - C ソーシャルゲーム

問題概要

商品が n 種類、くじが m 種類あります。
くじを一度引くのにお金がかかります。
くじからは、ある確率である商品が手に入ります。

最善を尽くしたとき、全ての商品を集める金額の期待値を求めてください。

考えたこと

期待値についてはこちら 期待値と条件付確率 - math314のブログ
問題文についてはこちら ARC016-C「ソーシャルゲーム」 | クリエイティヴなヴログ の記事が非常に参考になります。

こちら 期待値と条件付確率 - math314のブログ の記事で例として挙げられているコイントスの期待値についてです。
頂点の値が、連続で表が出た回数を示しています。
青矢印が表が出たことを、橙矢印が裏が出たことを表しています。
期待値はこのように状態の遷移から式を立てることができます。
f:id:noy72:20171027164545j:plain:w500

単純なくじで、期待値を求める式を立ててみます。
E は、その状態から全ての商品を集めるためにくじを引く回数を表しています。

頂点の値は、商品の入手を bit で表しています。
00 の状態からそれぞれ 10, 01 の状態へ遷移し、最後は 11 となります。
11 は全て揃った状態でありこれ以上はくじを引く必要がないため E_11 = 0 です。
10 の状態から 11 になるに 1 番目の商品を引かなければなりません。
このとき、 5% の確率で引けるので、くじを引く回数の期待値は 100 / 5 回です。
もう片方は 95% なので、 100 / 95 回です。

00 からは 5% の確率で 01 になり、 01 からは 100 / 95 回で全て揃います。
また、 95% の確率で 10 になり、 10 からは 100 / 5 回で全て揃います。
これで、 00 から 11 までの期待値が計算できました。
f:id:noy72:20171027164552j:plain:w500

式を実際に立ててみると、後ろから計算することで解がわかることに気付けます。
f:id:noy72:20171027164617j:plain:w500
f:id:noy72:20171027164624j:plain:w500
f:id:noy72:20171027164641j:plain:w500
あとは式を計算できるように実装します。

実装

sum が自分自身に返ってこない場合の期待値を表しています。
100 / (100 - k) が自分自身に返ってくる確率の逆数(期待値)を表しています。

手計算した式をどうにか実装したらうまくいった、という感じです。

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
const int INF = 1e8;
using namespace std;

//i番目のビットを返す
bool getBit(int num, int i){
	return ((num & (1 << i)) != 0);
}

//i番目を1にする
int setBit(int num, int i){
	return num | (1 << i);
}

int main(){
	int n, m;
	cin >> n >> m;

	vector<int> c(m), cost(m);
	vector<vector<pair<int, int>>> kuji(m); //番号、確率
	rep(i,m){
		cin >> c[i] >> cost[i];
		rep(j,c[i]){
			int a, b;
			cin >> a >> b;
			a--;
			kuji[i].emplace_back(a,b);
		}
	}

	double dp[1 << 10];
	rep(i,1 << 10) dp[i] = INF;
	dp[(1 << n) - 1] = 0;

	for(int s = (1 << n) - 1; s >= 0; s--){
		rep(i,m){
			double sum = cost[i], k = 0;
			for(auto j : kuji[i]){
				if(not getBit(s, j.first)){
					sum += dp[setBit(s, j.first)] * j.second / 100.0;
				}else{
					k += j.second;
				}
			}
			dp[s] = min(dp[s], sum * 100.0 / (100 - k));
		}
	}

	cout << fixed << setprecision(10) << dp[0] << endl;
}

ARC067 - E Grouping

問題概要

N 人をグループ分けします。
一つのグループにつき A ~ B 人で構成し、
同じ人数のグループは 0 か C ~ D 個作らなければいけません。
このようなグループ分けは何通りありますか。

DPの解説

DPテーブルを書いてみます。

横軸が、グループ分けしていない、残っている人の数。
縦軸が、i 人以下のグループのみでグループ分けしていることを表します。

dp[i][j] = i 人以下のグループのみにでグループ分けした時、グループ分けされていない人の数が j 人の時の通り数
f:id:noy72:20171026131458j:plain:w500

入力は、3 1 2 1 2 だとします。

まず、0 人以下のグループのみでグループ分けした場合を考えます。
「誰も選べない」の 1 通りしかないので、dp[0][n] = 1。
残りの人数を減らせないので、その他はすべて0。

次に、1 人のグループのみでグループ分けした場合を考えます。
残り 3 人いるときに、1 人グループを 1 個作った場合、3 人のうちから 1 人選ぶので、 _3 C _1
f:id:noy72:20171026131501j:plain:w500

残り 3 人いるときに、1 人グループを 2 個作った場合、3 人のうちから 1 人選んで、 2 人のうちから 1 人選ぶ。
そして、重複を消せばよいので、 \frac{_3 C _1 \times _2 C _1}{2!}
f:id:noy72:20171026131505j:plain:w500

同じグループは 3 個以上作れないので、次に進みます。
残り2 人いるときに、1 人グループを 1 個作った場合……ですが、
dp[0][2] = 0 のため、dp[1][1] +=  _2 C _1 \times 0となります。
計算をしても +0 するだけなので省略。
f:id:noy72:20171026131509j:plain:w500

これで 1 人グループを作る場合をすべて試せました。
この計算結果は、1 人グループのみでグループ分けした結果の通り数を表しています。
f:id:noy72:20171026131514j:plain:w500

縦軸は、i 人以下のグループのみでグループ分けしていることを表すので、0 行の結果を加える必要があります。
f:id:noy72:20171026131523j:plain:w500

次に、2 人以下のグループのみでグループ分けした場合を考えます。
残り 3 人いるときに、2 人グループを 1 個作った場合、 _3 C _2
f:id:noy72:20171026131527j:plain:w500

2 人グループは 1個以上作れないので、次に進みます。
残り 2 人いるときに、2 人グループを 1 個作った場合、 _2 C _2
f:id:noy72:20171026131531j:plain:w500

2人グループを作る場合が終わりました。
f:id:noy72:20171026131535j:plain:w500

あとは先と同様に、1行の結果を加えます。
f:id:noy72:20171026131541j:plain:w500

これで本当に正しいのか、組み合わせを列挙してみます。

残り 3 人のとき
{ \phi } (空集合)
より 1 通り。

残り 2 人のとき
{1}
{2}
{3}
より 3 通り。

残り 1 人のとき
{1, 2}
{1, 3}
{2, 3}
{ {1}, {2} }
{ {1}, {3} }
{ {2}, {3} }
より 6 通り。

残り 0 人のとき
{ {1, 2}, {3} }
{ {1, 3}, {2} }
{ {2, 3}, {1} }
より 3 通り。

どうやら正しいようです。

実装

先に組み合わせ、階乗の逆元を計算しておきます。
あとは遷移させます。

計算結果がどんどん加算されていくDPなので、更新する方向に気をつければ 1 次元配列で計算できます。

残り 1000 人を 1 人グループに分ける場合、
1 個のとき: _{1000} C _1
2 個のとき: \frac{_{1000} C _1 \times _{999} C _1}{2!}
3 個のとき: \frac{_{1000 }C _1 \times _{999} C _1 \times _{998} C _1}{3!}
....
と組み合わせの計算に時間がかかるので、前回の計算結果を用いて計算量を落としています。

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

const long long M = 1000000007;

long long nCr[1005][1005];
void Pascals(){
	nCr[0][0] = 1;
	range(i,1,1001){
		rep(j,i + 1){
			if(j == 0) nCr[i][j] = nCr[i - 1][j];
			else if(j == i) nCr[i][j] = nCr[i - 1][j - 1];
			else nCr[i][j] = (nCr[i - 1][j] + nCr[i - 1][j - 1]);
			nCr[i][j] %= M;
		}
	}
}

//べき乗 x^n mod M
long long power(long long x, long long n){
	long long res = 1;
	if(n > 0){
		res = power(x, n / 2);
		if(n % 2 == 0) res = (res * res) % M;
		else res = (((res * res) % M) * x ) % M;
	}
	return res;
}

//階乗
long long fact[1005];
long long factorial(long long n, long long r){
	long long res = 1;
	range(i,r,n + 1){
		res*= i;
		res%= M;
		fact[i] = res;
	}
	return res;
}

int main(){
	Pascals();
	factorial(1000,1);
	long long fact_rev[1005];
	rep(i,1001) fact_rev[i] = power(fact[i], M - 2);

	long long n, a, b, c, d;
	cin >> n >> a >> b >> c >> d;

	long long dp[1005] = {0};
	dp[n] = 1;
	range(i,a,b + 1){
		range(k,i * c,n + 1){
			long long person = k;
			long long comb = 1;

			range(j,1,d + 1){
				long long join = i * j;
				if(k - join < 0) break;

				(comb *= nCr[person][i]) %= M;
				person-=i;

				if(j >= c){
					(dp[k - join] += dp[k] * comb % M * fact_rev[j] % M) %= M;
				}
			}
		}
	}

	cout << dp[0] << endl;
}

ABC009 - D 漸化式

問題概要

二つの数列 { \displaystyle
A_1, A_2, …, A_K
}{ \displaystyle
 C_1, C_2, …, C_K
} が入力で与えられる。

数列 A は以下の式によって計算できる。
{ \displaystyle
A_{N+K}=(C_1 AND A_{N+K−1}) XOR (C_2 AND A_{N+K−2}) XOR …  XOR (C_K AND A_N)
}

数列 A の M 番目の値を求めよ。

解き方

漸化式を計算するには、DPを使えば良いです。しかし、制約が大きく、DPでは解けません。
別の方法を使って漸化式を解く必要があります。

そこで、行列累乗を使います(あり本 P.180参照)。
行列累乗に and や xor が使えるのかですが、それは atcoder の公式解説を参照してください。
あり本を見ながらやれば実装できます。ほとんどあり本のプログラムそのままです。
正しい順番で値を入れて、正しい値で初期化して、演算子を変えましょう。

ただ、割と引っかかるポイントが多かったです。

気をつけるところ

and は論理積

bit の and が取りたい時は、 bitand か & を使いましょう。

各項の順番

行列に値を入れる際、右から左に並べるのか、左から右に並べるのか(もちろん上下も)。

and 演算子単位元

普通に掛け算をするのであれば、単位元は 1 です。
あり本にあるプログラムや式は、行列の掛け算を行うため、 単位元に 1 が使われています。
しかし、この問題では and 演算子を使うため、単位元は全 bit が 1 の値です。
初期化ミスに気をつけましょう。

m ≤ k の時の処理

m ≤ k の時は、与えらえれた入力をそのまま返せば良いです。
入力を行列累乗のために逆順に持っていたことを忘れるとWAです(2敗)。

実装

#define int long long なので、単位元は -1 を使っています。

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

#define int long long
typedef vector<vector<int>> mat;

mat mul(mat &a, mat &b){
	mat c(a.size(), vector<int>(b[0].size()));
	rep(i,a.size()){
		rep(k,b.size()){
			rep(j,b[0].size()){
				c[i][j] = (c[i][j] xor (a[i][k] bitand b[k][j]));
			}
		}
	}
	return c;
}

mat pow(mat a, int n){
	mat b(a.size(), vector<int>(a.size(),0));
	rep(i,b.size()) b[i][i] = -1;
	while(n > 0){
		if(n & 1) b = mul(b,a);
		a = mul(a, a);
		n >>= 1;
	}
	return b;
}

int solve(int n, mat A, vector<int> c){
	mat a(A.size(), vector<int>(A.size(), 0));
	for(int i = c.size() - 1; i >= 0; i--){
		//a[0][i] = c[A.size() - 1 - i]; ここの順番が逆だった。
		a[0][i] = c[i];
	}
	rep(i,c.size() - 1){
		a[i + 1][i] = -1;
	}

	a = pow(a,n); //行列Aのn乗。
	mat res = mul(a, A);
	return res[0][0];
}

signed main(){
	int k, m;
	cin >> k >> m;

	mat a(k, vector<int>(1));
	vector<int> c(k);
	rep(i,k) cin >> a[k - i - 1][0];
	rep(i,k) cin >> c[i];

	if(m <= k){
		cout << a[k - m][0] << endl;
	}else{
		cout << solve(m - k,a,c) << endl; //-kを忘れずに
	}
}

ABC025D - 25個の整数

D: 25個の整数 - AtCoder Beginner Contest 025 | AtCoder


解説を見て実装を放置していたため、考察要素はないです。

問題概要

5 * 5 のマスがあります。 1 ~ 25 までの数値を、各マスに一つずつ書きます。
ただし、以下の条件を満たすように書かなければいけません。

縦、あるいは横に 3 つ並んだどのマスの数値も、単調減少、あるいは単調増加してはいけない。

あらかじめいくつかのマスはすでに数値が書かれています。
条件に従い全ての全てのマスを埋めるとき、何通りの埋め方がありますか。

考えたこと

制約は N ≤ 20 だけど、2^25のdpテーブル持ちたい…

2^25のdpテーブルをギリギリ持てた。

マスに何も書かれていない状態から考える。

dfsで 1 から順番に書いていき、全部埋められたら 1 を返す。
また、メモ化して無駄な部分を減らす。

元々数値が書いてあるということは、数値が書ける場所が 1 箇所しかないと考えられる。

bit と 2 次元の盤面を行き来する必要がある。

(x, y)は、bit の (x + y * 5) 番目と考えればよい。

実装

check関数で書けるかどうかの判定をしています。
atcoder公式の解説にある通り、数値を書く時のマスの状況が 4 種類に分けられます。
1. 端のマスに書き込む。
2. 書き込むマスの両側がすでに書き込まれている。
3. 書き込むマスの片方がすでに書き込まれている。
4. 書き込むマスの両方が書き込まれていない。

そして、書き込めないパターンは 3 番のみです。
書き込むマスの前後の bit の xor を取り、反転させれば条件を満たすかを判定できます。
それを縦横両方確かめ、and を取れば、書き込めるかわかります。

1 から順番に埋めていくため、実際に値の大小を比べる必要はありません。


dfs関数では、 num を書き込むマスを全通り試しています。
書き込める場所は、 "入力で 0 が与えられている" かつ "集合 s に含まれていない" 場所です。
1 から順番に書き込んでいくとはいえ、元々書き込まれている部分に書き込むことはできません。

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

const int M = 1000000007;

int dp[1 << 25];
vector<bool> used_number(25,0);
vector<bool> vacant_space(25,0);
pair<int, int> p[25];

bool getBit(int num, int i){
	return ((num & (1 << i)) != 0);
}

int setBit(int num, int i){
	return num | (1 << i);
}

bool check(pair<int, int> p, int s){
	int y = p.first;
	int x = p.second;

	bool xf, yf;
	if(x == 0 || x == 4){ //端に置くケース
		xf = true;
	}else{
		bool left_bit = getBit(s, (x - 1) + y * 5);
		bool right_bit = getBit(s, (x + 1) + y * 5);
		xf = not (left_bit xor right_bit);
	}

	if(y == 0 || y == 4){
		yf = true;
	}else{
		bool up_bit = getBit(s, x + (y - 1) * 5);
		bool down_bit = getBit(s, x + (y + 1) * 5);
		yf = not (up_bit xor down_bit);
	}

	return xf and yf;
}


int dfs(int s, int num){ //s = 埋められた場所の集合
	if(dp[s] != -1) return dp[s];

	if(used_number[num]){ //あらかじめ数字が置かれている場合
		int y = p[num].first;
		int x = p[num].second;
		int next = setBit(s, x + y * 5);

		if(check(p[num],s)){
			return dfs(next, num + 1);
		}else{
			return dp[next] = 0;
		}
	}

	int res = 0;
	rep(i,25){ // num を置ける場所を探す
		if(not getBit(s,i) && vacant_space[i]){
			if(check(make_pair(i / 5, i % 5), s)){
				res += dfs(setBit(s,i), num + 1);
				res %= M;
			}
		}
	}

	return dp[s] = res;
}

signed main(){
	memset(dp, -1, sizeof(dp));
	dp[(1 << 25) - 1] = 1; //全部埋まったら1通り

	rep(i,5) rep(j,5){
		int a;
		cin >> a;
		if(a == 0) vacant_space[i * 5 + j] = true;
		else used_number[a - 1] = true;
		p[a - 1] = make_pair(i,j);
	}

	cout << dfs(0,0) << endl;
}

AOJ 0553 ダンジョンの解説

AOJ 0553 ダンジョン

ダンジョン | Aizu Online Judge

考察

問題点

あり本にある優先度キューを用いたガソリン問題と似ています。
ただし、こちらの問題では、ガソリンを入れられる量の上限があります。

体力が0以下になる前に、どこかで回復しなければいけない
 ->どうせ回復するなら一番回復量が多い泉を使いたい
  ->体力が0以下になった時に、最も回復量が高い泉を使ったことにすれば良い

これは優先度キューを用いれば実現できそうです。

やっかいなのは体力の上限で、「泉の回復量は多いが、体力が減っていないため、実際の回復量が小さくなる」ということが起きるため、優先度キューだけを用いてもうまくいきません。
「泉の回復量が多い順」ではなく、「実際の回復量が多い順」に並べなければいけません。

実際の回復量は、体力と泉の回復量がわかれば求めることができそうです。
そこで、各階を訪れた際の体力を持っておき、それを元に「実際の回復量」を決めましょう。

実際の回復量を求める

体力の更新方法をまずは考えます。

地下 i 階で体力が0になったので、地下 j 階で泉を使ったことにする( i > j )。
すると、当然地下 j 階〜 i 階の体力は増えます。つまり、区間に対する加算を行う必要があります。

また、加算した際に、体力が上限を超えてはいけません。
つまり、地下 j 階で体力を回復する場合、地下 j 階〜 i 階の区間のすべての体力は、(体力の上限 - j 階の回復量)以下である必要があります。
裏を返せば、地下 j 階の回復量は、(体力の上限 - 地下 j 階〜 i 階の区間で最大の体力)以下になります。

よって、実際の回復量を求めるためには、区間の最大値を求める必要があることがわかります。

方針

使うもの
 優先度キュー、 セグメントツリー(区間に対する加算、 区間の最小値を求める)

1)体力をセグメントツリーに記録する
2)泉の情報をキューに入れる
3)体力を消費する
4)体力が0以下になったとき
 1)最も回復量が多いものを取り出す
 2)区間[回復する場所、現在地]の最大値を求める
 3)体力の最大値 + 回復量 <= 体力の上限 のとき、その泉を使えるだけ使う。
   使えないとき、実際の回復量を更新してキューに戻す。その後、1に戻る
 4)泉を使って回復したことにし、区間に加算する。

実装
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

#define int long long

const int MAX_N = 100010;

class segTree{
    public:
        int n, dat[4 * MAX_N];
        void init(int n_, int value, int dat_b[4 * MAX_N] = NULL){
            n = 1;
            while(n < n_) n *= 2;
            rep(i,2 * n){
                dat[i] = value;
                if(dat_b != NULL) dat_b[i] = value;
            }
        }
        void output(int a[4 * MAX_N]){
            show("print");
            range(i,1,n * 2) cout << (a[i] == INT_MAX ? 0 : a[i]) << ' ';
            cout << endl;
        }
};

class starrySky : public segTree{
    private:
        int query(int a, int b, int k, int l, int r){
            if(b <= l || r <= a) return 0;
            if(a <= l && r <= b) return dat[k] + dat_add[k];

            int vl = query(a, b, k * 2, l, (l + r) / 2);
            int vr = query(a, b, k * 2 + 1, (l + r) / 2, r);
            return max(vl, vr) + dat_add[k];
        }
        void add(int a, int b, int k, int l, int r, int x){
            if(b <= l || r <= a) return;
            if(a <= l && r <= b){
                dat_add[k] += x;
            }else{
                add(a, b, k * 2, l, (l + r) / 2, x);
                add(a, b, k * 2 + 1, (l + r) / 2, r, x);
                dat[k] = max(dat[k * 2] + dat_add[k * 2], dat[k * 2 + 1] + dat_add[k * 2 + 1]);
            }
        }
        void init(int n_){ segTree::init(n_,0,dat_add); }
    public:
        int dat_add[4 * MAX_N];
        starrySky(int n){ init(n); }
        int query(int a, int b){ return query(a, b, 1, 0, n); }
        void add(int s, int t, int x){ add(s, t, 1, 0, n, x); }
        void add(int i, int x){ add(i, i + 1, 1, 0, n, x); }
};


signed main(){
    long long n, h;
    cin >> n >> h;

 //1-indexのセグ木
    starrySky seg(n); //体力を保持する
    priority_queue<pair<long long, int>> q; //泉の回復量、pos
    long long cur = h, ans = 0;
    rep(i,n - 1){
        long long damage, heal;
        cin >> damage >> heal;
        q.push(make_pair(heal, i));

        seg.add(i + 1, cur);
        cur -= damage;
        while(cur <= 0){
            pair<long long, int> use = q.top(); q.pop();
            long long maxHP = seg.query(use.second + 1, i + 2); //回復地点から現在地までの体力の最大

            if(maxHP + use.first > h){ //回復量が上限を超えるので、実際の回復量に変更
                q.push(make_pair(h - maxHP, use.second));
                continue;
            }

            long long can_use = (h - maxHP) / use.first;
            long long require = ceil((-1.0 * cur + 1) / use.first);
            long long used = min(can_use, require);
            ans += used;
            cur += used * use.first;

            seg.add(use.second + 1, i + 2, used * use.first);
            q.push(use);
        }
    }
    cout << ans << endl;
}

構文解析初心者でも解ける問題を集めた+解説

水色コーダーが構文解析の問題を解きました。その記録です。
問題の難易度は、AOJ−ICPC基準で300点前後だと思います。

構文解析とは

構文解析とは、やるだけ問題です。
ここ構文解析 Howto · GitHubにもそう書いてあります。
 
構文解析初心者の方は、まずはこれを読みましょう。
読みましょう

ここを読めば、この記事で解説している問題に挑めるはずです。

問題

計算機 | Aizu Online Judge

四則演算の問題です。
テンプレを間違いなく写しましょう。

Unordered Operators | Aizu Online Judge

問題概要

四則演算の優先順位を自由に入れ替えて、解を最大化しましょう。
ただし、割り算は使いません。

解法

全ての優先順位を全通り試せば良いです。
テンプレを見ると分かりますが、同じ関数にある演算子は優先順位が同じで、先に処理される演算子ほど優先度が高いです。
例えば、全ての演算子の優先順位を同じにしたければ、expr関数に全ての演算子を書けばいいです。

long long expr(State &begin) {
    long long ret = term(begin);

    for (;;) {
        if (*begin == '+') {
            begin++;
            ret += term(begin);
        } else if (*begin == '-') {
            begin++;
            ret -= term(begin);
        } else if (*begin == '*'){
            begin++;
            ret *= term(begin);
        } else {
            break;
        }
    }
    return ret;
}

とりあえず全部書けば通りますが、面倒なのでどうにかして楽に書きましょう。

4つのparserを書いたり*1、bitを使って全通り試したりしましょう。

ACされたコード
AIZU ONLINE JUDGE: Code Review

注意点

解の初期化に注意する
解のmaxを取っていくのなら、解を入れる変数を小さい数値で初期化しなければいけません。
ここでは最小値で初期化しましょう。雑に小さい数値を入れるとWAです。

Operations with Finite Sets | Aizu Online Judge

問題概要

集合の演算を行う構文解析です。
演算子は u, i, d, s, c の5つあり、式はセット名、演算子、括弧からなります。
この問題の式は、以下のように与えられます。

<expr> ::= <term> <op> <term>
<term> ::= c <factor> | <factor>
<factor> ::= ( <expr> ) | <set>
<set> ::= A | B | C | D | E
<op> ::= u | i | d | s

見様見真似なので、正しいか全く自信がないです。

解法

まさに構文解析という問題です。
形は変われどやっていることは同じです。
集合の計算は関数があるので、演算子の処理を考える必要はありません。

順番にテンプレを書き換えていきましょう。

number関数
集合を返すだけです。
文字列を数値に変換するなどの操作がないので、number関数を使わなくても問題ありません。

factor関数
括弧を処理するか数を返すかのどちらかなので、そのままで問題がなさそうです。

term関数
ここで行う演算は 'c' のみです。今見ている文字が'c'のとき、factor関数の戻り値を補集合にすればよいです。
'c'ではなかったら、戻り値をそのまま返します。

expr関数
四則演算で言うところの + や - にあたる部分を u, i, d, s を変えます。
条件分岐させて演算するようにします。

ACされたコード
AIZU ONLINE JUDGE: Code Review
構文解析部分は50行と短いです。

注意点

集合は始めにソートする。
set_unionやset_intersectionは、ソートされていないと正しい集合を返しません。

NULLを出力する。
解が空集合の場合、NULLを出力しなければなりません。
ここでいうNULLはテキストの "NULL" です。 '¥0' ではないです。

How can I satisfy thee? Let me count the ways... | Aizu Online Judge

問題概要

0, 1, 2, P, Q, R, -, *, +, (, ) からなる式が与えられます。
P, Q, R は、それぞれ 0 ~ 2 までの数値へ置き換えることができます。
このとき、式の解が 2 であるような P, Q, R の組み合わせは何通りあるでしょうか。

解法

P, Q, R の組み合わせは 27 通りしかないので、全部試して解が 2 になる回数を数えればよさそうです。
次に、式をどのようにして演算すれば良いのかを考えます。

演算子 +, * は、与えられた数値のmax, minを取ればよいです。
- 演算子は、Operations with Finite Sets | Aizu Online Judgeの c 演算子のように処理すればよさそうです。

つまり、expr→term(ここで - 演算子を処理)→factor→numberとすれば計算できます。
ただ、 - 演算子は連続することもあります。
ですので、もし - 演算子があれば、term関数を呼ぶ。
それ以外はfactor関数を呼ぶようにして、連続した - 演算子を処理します。

int term(State &begin){
    if (*begin == '-') {
        begin++;
        //inverted(x) = xを反転した値
        return inverted(term(begin)); 
    } else {
        return factor(begin);
    }
}

ACされたコード
AIZU ONLINE JUDGE: Code Review

Shipura | Aizu Online Judge

問題概要

>>、S<>、数値からなる式を計算する。

解法

まず、空白はあってもなくても変わらないので全部消します。
次に、>> 、S<>について考えます。
>>はexprで処理し、S<>はfactorの括弧の処理を少し書き換えて実装します。

>>を素直に実装すると、

if(*being == '>' && *(begin + 1) == '>'){
    begin++; 
    begin++;
    ret = ret >> term(begin);
}

とやってしまいそうですが、少しまずいです。
まず、この条件では、”S< S< S< 1 > > >” このようなケースのときに、シフトを行ってしまいます。
3 つ '>' が並んでいるときは、シフト演算子ではありません。

if(*begin == '>' && *(begin + 1) == '>' && *(begin + 2) != '>')

2 つのみ並んでいるときだけ、シフトしましょう。

次に、 "ret >> term(begin)" の部分に注目します。
上記の実装では、"1 >> 20000" という計算を行うこともあります。
これだとオーバーフローを起こして 0 ではない値になるので、シフト演算子の右辺は小さめに抑えたほうがよいです。

ACされたコード
AIZU ONLINE JUDGE: Code Review

注意点

2 乗でオーバーフロー
int型だとS<>を処理するときにオーバーフローします。

まとめ

  • 処理を関数にまとめて、順番を決めて、終わり。
  • バグらせると辛い。