SRM 553 250pt : Suminator

問題概要

数列Xがある。一つだけ-1が入っていてそれ以外は非負整数が入っている。今、0がたくさんつまったスタックがある。-1を適当な非負整数に置き換える。数列を先頭から見ていったとき、0ならトップの二つを和で置き換え、それ以外ならその値を直接プッシュするようにする。最後の先頭の価がWになるようにするには-1をいくつに置き換えればよいか求める問題。無理なら指摘。複数答があるときは最小の整数を返す。

解法

まず0で上手くいくなら0を返す。それ以外のとき、値をINFとして計算し、最後の値からINFを引いたのが答の候補になっているので正しいかどうか確かめればよい。

acceptされたコード

#include <vector>
using namespace std;

typedef long long int64;
const int64 INF = int64(1.1e17);

struct Suminator {

	int findMissing(vector <int> program, int wantedResult) {
		const int n = program.size();
		vector<int64> stack;
		for (int i = 0; i < 100; ++i) {
			stack.push_back(0);
		}

		for (int i = 0; i < n; ++i) {
			if (program[i] > 0) {
				stack.push_back(program[i]);
			}
			else {
				int64 a = stack.back();
				stack.pop_back();
				int64 b = stack.back();
				stack.pop_back();
				stack.push_back(a + b);
			}
		}
		if (stack.back() == wantedResult) {
			return 0;
		}

		stack.clear();
		for (int i = 0; i < 100; ++i) {
			stack.push_back(0);
		}

		for (int i = 0; i < n; ++i) {
			if (program[i] > 0) {
				stack.push_back(program[i]);
			}
			else if (program[i] == 0) {
				int64 a = stack.back();
				stack.pop_back();
				int64 b = stack.back();
				stack.pop_back();
				stack.push_back(a + b);
			}
			else {
				stack.push_back(INF);
			}
		}

		int64 result = stack.back();
		if (result < INF / 10){
			return result == wantedResult ? 1 : -1;
		}
		result -= INF;
		result = wantedResult - result;
		if (result > 0) {
			return result;
		}

		return -1;
	}

};