結果

問題 No.1196 A lazy student
コンテスト
ユーザー e869120
提出日時 2021-03-05 20:29:52
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 79 ms / 1,000 ms
コード長 3,058 bytes
コンパイル時間 1,024 ms
コンパイル使用メモリ 89,680 KB
実行使用メモリ 56,248 KB
最終ジャッジ日時 2024-10-06 22:58:50
合計ジャッジ時間 2,637 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
#pragma warning (disable: 4996)

// 入力
int N;
double P, Q, R;
string S;

// その他の変数
int dep[1 << 20];
bool tonari[1 << 20];
vector<int> V1[1 << 19];
vector<int> V2[1 << 19];
vector<int> V3[1 << 19];

double dfs(int cl, int cr) {
	int CurrentDep = dep[cl];

	// OR の計算
	int pos1 = lower_bound(V1[CurrentDep].begin(), V1[CurrentDep].end(), cl + 0) - V1[CurrentDep].begin();
	int pos2 = lower_bound(V1[CurrentDep].begin(), V1[CurrentDep].end(), cr + 1) - V1[CurrentDep].begin();
	if (pos1 < pos2) {
		int border = V1[CurrentDep][pos2 - 1];
		double v1 = dfs(cl, border - 1);
		double v2 = dfs(border + 2, cr);
		double t = 1.0 - (1.0 - v1) * (1.0 - v2);
		double u = (1.0 - t) * R + t * (1.0 - R);
		return u;
	}

	// AND の計算
	int pos3 = lower_bound(V2[CurrentDep].begin(), V2[CurrentDep].end(), cl + 0) - V2[CurrentDep].begin();
	int pos4 = lower_bound(V2[CurrentDep].begin(), V2[CurrentDep].end(), cr + 1) - V2[CurrentDep].begin();
	if (pos3 < pos4) {
		int border = V2[CurrentDep][pos4 - 1];
		double v1 = dfs(cl, border - 1);
		double v2 = dfs(border + 3, cr);
		double t = v1 * v2;
		double u = (1.0 - t) * R + t * (1.0 - R);
		return u;
	}

	// RANDOM の計算
	if (cr - cl >= 6 && S[cl] == 'r') {
		int pos5 = lower_bound(V3[CurrentDep + 1].begin(), V3[CurrentDep + 1].end(), cl + 7) - V3[CurrentDep + 1].begin();
		int pos6 = lower_bound(V3[CurrentDep + 1].begin(), V3[CurrentDep + 1].end(), cr + 0) - V3[CurrentDep + 1].begin();
		int border = V3[CurrentDep + 1][pos5];
		double v1 = dfs(cl + 7, border - 1);
		double v2 = dfs(border, cr - 1);
		double u = v1 * v2 * P + (1.0 - v1 * v2) * Q;
		return u;
	}

	// (...) の場合
	if (S[cl] == '(' && S[cr] == ')') {
		return dfs(cl + 1, cr - 1);
	}

	// それ以外の場合
	if (cr - cl == 2 && S[cl] == 'Y') {
		return 1.0;
	}
	if (cr - cl == 1 && S[cl] == 'N') {
		return 0.0;
	}
	return 869120.0;
}

int main() {
	// Step #1. 入力
	cin >> N >> P >> Q >> R;
	cin >> S;

	// Step #2. 前処理
	for (int i = 0; i < S.size(); i++) {
		dep[i + 1] = dep[i];
		if (S[i] == '(') dep[i + 1] = dep[i] + 1;
		if (S[i] == ')') dep[i + 1] = dep[i] - 1;
	}
	int cx = 0;
	while (cx < S.size()) {
		bool flag = true;
		if (S[cx] == 'r') { cx += 6; flag = false; }
		else if (S[cx] == 'o') { V1[dep[cx]].push_back(cx); cx += 2; flag = false; }
		else if (S[cx] == 'a') { V2[dep[cx]].push_back(cx); cx += 3; flag = false; }
		else if (cx + 1 < (int)S.size()) {
			int cnt = 0;
			if (S[cx + 0] == 'S' || S[cx + 0] == 'O' || S[cx + 0] == ')') cnt += 1;
			if (S[cx + 1] == 'Y' || S[cx + 1] == 'N' || S[cx + 1] == 'r' || S[cx + 1] == '(') cnt += 1;
			if (cnt == 2) tonari[cx + 1] = true;
		}
		if (tonari[cx + 1] == true) V3[dep[cx + 1]].push_back(cx + 1);
		if (flag == true) cx += 1;
	}

	// Step #3. 構文解析
	double I = dfs(0, N - 1);
	int J = (int)(100.0 * I);
	cout << J << endl;
	return 0;
}
0