#42192 (C++11) No.265 数学のテスト

提出ソース

結果

問題	No.265 数学のテスト
ユーザー	anta
提出日時	2015-08-07 22:36:48
言語	C++11 (gcc 11.4.0)
結果	RE
実行時間	-
コード長	6,615 bytes
コンパイル時間	1,032 ms
コンパイル使用メモリ	92,444 KB
実行使用メモリ	12,032 KB
最終ジャッジ日時	2024-07-18 05:11:05
合計ジャッジ時間	3,670 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	RE	-
testcase_01	RE	-
testcase_02	AC	3 ms 6,944 KB
testcase_03	RE	-
testcase_04	RE	-
testcase_05	RE	-
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	RE	-
testcase_12	AC	2 ms 6,944 KB
testcase_13	RE	-
testcase_14	RE	-
testcase_15	AC	2 ms 6,944 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	1 ms 6,944 KB
testcase_18	AC	2 ms 6,940 KB
testcase_19	AC	2 ms 6,944 KB
testcase_20	RE	-
testcase_21	AC	1 ms 6,944 KB
testcase_22	RE	-
testcase_23	AC	2 ms 6,940 KB
testcase_24	AC	2 ms 6,940 KB
testcase_25	RE	-
testcase_26	AC	2 ms 6,940 KB
testcase_27	AC	2 ms 6,940 KB
testcase_28	AC	1 ms 6,940 KB
testcase_29	AC	2 ms 6,940 KB
testcase_30	RE	-
testcase_31	AC	2 ms 6,940 KB
testcase_32	AC	1 ms 6,940 KB
testcase_33	AC	2 ms 6,940 KB
testcase_34	AC	1 ms 6,940 KB
testcase_35	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }


namespace parse {
	typedef const char *Pos;

	struct ParseError {
		Pos p_;
		std::stringstream *ss_;
		ParseError(const Pos &p): p_(p), ss_(new std::stringstream()) { }
		ParseError(const ParseError &that): p_(0), ss_(0) { *this = that; }
		ParseError &operator=(const ParseError &that) {
			delete ss_;
			p_ = that.p_;
			ss_ = new std::stringstream(that.ss_->str());
			return *this;
		}
		~ParseError() { delete ss_; }
		template<typename T> ParseError &operator<<(const T &t) {
			*ss_ << t;
			return *this;
		}
		friend std::ostream &operator<<(std::ostream &o, const ParseError &e) {
			o << e.ss_->str() << " at: ";
			Pos q = e.p_;
			for(int k = 0; *q && k < 20; ++ q, ++ k)
				o << *q;
			if(*q) o << "...";
			else o << "(end)";
			return o;
		}
	};

	inline bool cond(bool b, Pos &p) {
		if(b) ++ p;
		return b;
	}

	inline bool rewind(int k, bool b, Pos &p) {
		if(!b) p -= k;
		return b;
	}
	inline bool rw0(bool b, Pos &p) { return b; }
	inline bool rw1(bool b, Pos &p) { return rewind(1, b, p); }
	inline bool rw2(bool b, Pos &p) { return rewind(2, b, p); }

	inline bool optional(bool) { return true; }

	inline bool expect(bool b, const Pos &p) {
		if(!b) throw ParseError(p) << "parse error";
		return b;
	}
	inline bool char_(char c, Pos &p) {
		return cond(c == *p, p);
	}

	inline bool string_(const char *str, Pos &p) {
		Pos o = p;
		for(const char *s = str; *s; ++ s, ++ p) {
			if(*s != *p) {
				p = o;
				return false;
			}
		}
		return true;
	}
};


using namespace parse;

bool natural(Pos &p, int &res) {
	if(!isdigit(*p)) return false;
	int c = 0;
	while(isdigit(*p)) {
		c = c * 10 + (*p - '0');
		++ p;
	}
	res = c;
	return true;
}

bool number(Pos &p, int &res) {
	if(char_('-', p)) {
		expect(natural(p, res), p);
		res = -res;
		return true;
	}else
		return natural(p, res);
}


struct Polynomial {
	typedef long long Coef; typedef Coef Val;
	vector<Coef> coef;	//... + coef[2] x^2 + coef[1] x + coef[0]
	Polynomial() {}
	explicit Polynomial(int n): coef(n) {}
	static Polynomial One() {
		Polynomial r(1);
		r.coef[0] = 1;
		return r;
	}
	bool iszero() const { return coef.empty(); }
	int degree1() const { return coef.size(); }	//degree + 1
	int resize(int d) { if(degree1() < d) coef.resize(d); return d; }
	const Coef operator[](int i) const {
		return i >= degree1() ? Coef() : coef[i];
	}
	void canonicalize() {
		int i = coef.size();
		while(i > 0 && coef[i-1] == Coef()) i --;
		coef.resize(i);
	}
	Val evalute(Val x) const {
		int d = degree1();
		Val t = 0, y = 1;
		rep(i, d) {
			t += y * coef[i];
			y *= x;
		}
		return t;
	}
	Polynomial &operator+=(const Polynomial &that) {
		int d = resize(that.degree1());
		for(int i = 0; i < d; i ++) coef[i] += that[i];
		canonicalize();
		return *this;
	}
	Polynomial operator+(const Polynomial &that) const { return Polynomial(*this) += that; }
	Polynomial &operator-=(const Polynomial &that) {
		int d = resize(that.degree1());
		for(int i = 0; i < d; i ++) coef[i] -= that[i];
		canonicalize();
		return *this;
	}
	Polynomial operator-(const Polynomial &that) const { return Polynomial(*this) -= that; }
	Polynomial operator-() const {
		int d = degree1();
		Polynomial res(d);
		for(int i = 0; i < d; i ++) res.coef[i] = - coef[i];
		return res;
	}
	//naive
	Polynomial operator*(const Polynomial &that) const {
		if(iszero() || that.iszero()) return Polynomial();
		int x = degree1(), y = that.degree1(), d = x + y - 1;
		Polynomial res(d);
		rep(i, x) rep(j, y)
			res.coef[i+j] += coef[i] * that.coef[j];
		res.canonicalize();
		return res;
	}
	//long division
	pair<Polynomial, Polynomial> divmod(const Polynomial &that) const {
		int x = degree1() - 1, y = that.degree1() - 1;
		int d = max(0, x - y);
		Polynomial q(d + 1), r = *this;
		for(int i = x; i >= y; i --) {
			Coef t = r.coef[i] / that.coef[y];
			q.coef[i - y] = t;
			assert(t * that.coef[y] == r.coef[i]);
			r.coef[i] = 0;
			if(t == 0) continue;
			for(int j = 0; j < y; j ++)
				r.coef[i - y + j] -= t * that.coef[j];
		}
		q.canonicalize(); r.canonicalize();
		return make_pair(q, r);
	}
	Polynomial operator/(const Polynomial &that) const { return divmod(that).first; }
	Polynomial operator%(const Polynomial &that) const { return divmod(that).second; }

	Polynomial differentiate() const {
		int d = degree1();
		Polynomial q(d - 1);
		for(int i = 0; i < d - 1; i ++)
			q.coef[i] = coef[i+1] * Coef(i+1);
		return q;
	}
};

bool expr(Pos &p, Polynomial &res);

bool factor2(Pos &p, Polynomial &res) {
	int x;
	if(char_('d', p)) {
		expect(char_('{', p), p);
		expect(expr(p, res), p);
		expect(char_('}', p), p);
		res = res.differentiate();
		return true;
	}else if(char_('x', p)) {
		res.coef.assign(2, 0);
		res.coef[1] = 1;
		return true;
	}else if(natural(p, x)) {
		res.coef.assign(1, 0);
		res.coef[0] = x;
		return true;
	}else {
		return false;
	}
}

bool factor(Pos &p, Polynomial &res) {
	Polynomial r;
	if(!factor2(p, res)) return false;
	while(char_('*', p)) {
		expect(factor2(p, r), p);
		res = res * r;
	}
	return true;
}

bool expr(Pos &p, Polynomial &res) {
	Polynomial r;
	if(!factor(p, res)) return false;
	while(char_('+', p)) {
		expect(factor(p, r), p);
		res += r;
	}
	return true;
}

int main() {
	int N, d;
	while(cin >> N >> d) {
		string S;
		cin >> S;
		Pos p = S.c_str();
		Polynomial r;
		expect(expr(p, r), p);
		r.canonicalize();
		rep(i, d+1) {
			if(i != 0) putchar(' ');
			printf("%lld", r[i]);
		}
		puts("");
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード