結果
| 問題 | No.2069 み世界数式 |
| ユーザー |
👑  Nachia
|
| 提出日時 | 2022-09-09 00:10:09 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 23 ms / 2,000 ms |
| コード長 | 9,586 bytes |
| コンパイル時間 | 5,232 ms |
| コンパイル使用メモリ | 131,764 KB |
| 最終ジャッジ日時 | 2025-02-07 03:34:52 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 41 |
ソースコード
#include<vector>#include<utility>#include<istream>// テンプレート引数// S ： オペランドの型// read_S ： 引数の入力ストリームからオペランドを 1 つ読み込んで返す関数のポインタ// op_add ： S どうしの足し算を計算する関数のポインタ// op_sub ： S どうしの引き算を計算する関数のポインタ// op_mul ： S どうしの掛け算を計算する関数のポインタtemplate<class S,S(*read_S)(std::istream&),S(*op_add)(S, S),S(*op_mul)(S, S),S(*op_paren)(S)>class parse {private:enum Op_Symbol {Op_Symbol_Add,Op_Symbol_Mul,Op_Symbol_BracketOpen};struct parse_stack {// オペランドの位置関係std::vector<S> St;// 演算子と括弧の位置関係// 優先順位が低い順に並ぶので、後ろから計算されるstd::vector<Op_Symbol> OpSymbols;// OpSymbols の最後の要素を、適切な操作を伴って削除する// Op_Symbol_BracketOpen の場合は取り除かれるだけvoid remove_last_op() {switch (OpSymbols.back()) {case Op_Symbol_Add: {S r = St.back(); St.pop_back();S l = St.back(); St.pop_back();St.push_back(op_add(l, r));} break;case Op_Symbol_Mul: {S r = St.back(); St.pop_back();S l = St.back(); St.pop_back();St.push_back(op_mul(l, r));} break;case Op_Symbol_BracketOpen: {} break;}OpSymbols.pop_back();}};public:// 引数の入力ストリームから EOF まで式を読み込み、評価する。// 読み込まれる式が正しくない場合、未定義動作。S calc(std::istream& istr) const {parse_stack st;while (true) {char c; istr >> c;if (istr.eof()) break;if (c == '(') {// Op_Symbol_BracketOpen は ')' が来たときに取り除かれるst.OpSymbols.push_back(Op_Symbol_BracketOpen);continue;}else if (c == ')') {// 優先順位の高いものをすべて計算// カッコ内すべてbool pop_done = false;while (!st.OpSymbols.empty() && !pop_done) {switch (st.OpSymbols.back()) {case Op_Symbol_Add:case Op_Symbol_Mul: {st.remove_last_op();} break;default: {pop_done = true;}}}// Op_Symbol_BracketOpen を取り除くst.St.back() = op_paren(st.St.back());st.OpSymbols.pop_back();}else if (c == '$') {// 優先順位の高い掛け算はすべて計算// 掛け算または左側の足し算引き算bool pop_done = false;while (!st.OpSymbols.empty() && !pop_done) {switch (st.OpSymbols.back()) {case Op_Symbol_Add:case Op_Symbol_Mul: {st.remove_last_op();} break;default: {pop_done = true;}}}// 現時点で優先順位最高st.OpSymbols.push_back(Op_Symbol_Add);}else if (c == '&') {bool pop_done = false;// 優先順位の高いものをすべて計算// 左側の掛け算while (!st.OpSymbols.empty() && !pop_done) {switch (st.OpSymbols.back()) {case Op_Symbol_Mul: {st.remove_last_op();} break;default: {pop_done = true;}}}// 優先順位が現時点で最高なので、OpSymbolsの最後に足すだけでよいst.OpSymbols.push_back(Op_Symbol_Mul);}else {// 演算子や括弧ではないので、オペランドとして読み込むistr.unget();st.St.push_back(read_S(istr));}}// 残りを計算while (!st.OpSymbols.empty()) {st.remove_last_op();}return st.St.back();}};#include <iostream>#include <string>#include <vector>#include <algorithm>#include <bitset>using namespace std;using i32 = int32_t;using u32 = uint32_t;using i64 = int64_t;using u64 = uint64_t;#define rep(i,n) for(int i=0; i<(int)(n); i++)vector<int> opLeft;vector<int> opRight;vector<int> opType;vector<int> expSize;vector<int> expPos;vector<int> expVal;int read_S(istream& cin){int v; cin >> v;int res = opType.size();opLeft.push_back(-1);opRight.push_back(-1);opType.push_back(v);expSize.push_back(to_string(v).size());expVal.push_back(-1);expPos.push_back(0);return res;}int op_add(int l, int r){int res = opType.size();opLeft.push_back(l);opRight.push_back(r);opType.push_back(-1);expSize.push_back(expSize[l] + expSize[r] + 1);expVal.push_back(-1);expPos.push_back(0);return res;}int op_mul(int l, int r){int res = opType.size();opLeft.push_back(l);opRight.push_back(r);opType.push_back(-2);expSize.push_back(expSize[l] + expSize[r] + 1);expVal.push_back(-1);expPos.push_back(0);return res;}int op_paren(int l){int res = opType.size();opLeft.push_back(l);opRight.push_back(-1);opType.push_back(-3);expSize.push_back(expSize[l] + 2);expVal.push_back(-1);expPos.push_back(0);return res;}using Parse = parse<int, read_S, op_add, op_mul, op_paren>;int main(){int M; cin >> M;int C; cin >> C;Parse().calc(cin);/*rep(i,opType.size()){cout << "i = " << i << " , ";cout << "l = " << opLeft[i] << " , ";cout << "r = " << opRight[i] << " , ";cout << "ty = " << opType[i] << " , ";cout << endl;}cout << endl;*/vector<bitset<301>> dp(opType.size());bitset<301> mask;rep(i,M+1) mask.set(i);rep(i,opType.size()){if(opType[i] >= 0){dp[i].set(opType[i]);}else if(opType[i] == -1){for(int d=0; d<=M; d++){if(!dp[opRight[i]].test(d)) continue;dp[i] |= dp[opLeft[i]] << d;dp[i] |= dp[opLeft[i]] >> d;}dp[i] &= mask;}else if(opType[i] == -2){for(int d=0; d<=M; d++) if(dp[opLeft[i]].test(d)) for(int e=0; d*e<=M && e<=M; e++) if(dp[opRight[i]].test(e)){dp[i].set(d*e);}vector<int> imos(M+2, 0);rep(d,M+1) imos[d+1] = imos[d] + (dp[opLeft[i]].test(d) ? 1 : 0);for(int d=1; d<=M; d++) if(dp[opRight[i]].test(d)) for(int t=0; d*t<=M && t<=M; t++) if(imos[min(M+1,d*(t+1))] - imos[d*t]){dp[i].set(t);}}else if(opType[i] == -3){dp[i] = dp[opLeft[i]];}}//rep(i,opType.size()) cout << dp[i] << endl;//cout << endl;if(!dp.back().test(C)){ cout << "-1\n"; return 0; }expVal.back() = C;string res(expSize.back(), ' ');for(int i=(int)opType.size()-1; i>=0; i--){//cout << "i = " << i << " , ";//cout << "val = " << expVal[i] << " , ";//cout << "ty = " << opType[i] << endl;if(!dp[i].test(expVal[i])){ cout << "value error" << endl; return 0;}if(opType[i] >= 0){string tmp = to_string(opType[i]);copy(tmp.begin(), tmp.end(), res.begin() + expPos[i]);}else if(opType[i] == -1){expPos[opLeft[i]] = expPos[i];expPos[opRight[i]] = expPos[i] + expSize[opLeft[i]] + 1;int v = expVal[i];bool done = false;for(int l=0; l<=v; l++) if(dp[opLeft[i]].test(l) && dp[opRight[i]].test(v-l)){expVal[opLeft[i]] = l;expVal[opRight[i]] = v-l;res[expPos[i] + expSize[opLeft[i]]] = '+';done = true;break;}for(int l=v; l<=M; l++) if(dp[opLeft[i]].test(l) && dp[opRight[i]].test(l-v)){expVal[opLeft[i]] = l;expVal[opRight[i]] = l-v;res[expPos[i] + expSize[opLeft[i]]] = '-';done = true;break;}if(!done) return 0;}else if(opType[i] == -2){expPos[opLeft[i]] = expPos[i];expPos[opRight[i]] = expPos[i] + expSize[opLeft[i]] + 1;int v = expVal[i];bool done = false;for(int d=0; !done && d<=M; d++) if(dp[opLeft[i]].test(d)) for(int e=0; d*e<=M && e<=M; e++) if(d*e == v) if(dp[opRight[i]].test(e)){expVal[opLeft[i]] = d;expVal[opRight[i]] = e;res[expPos[i] + expSize[opLeft[i]]] = '*';done = true;break;}vector<int> imos(M+2, 0);rep(d,M+1) imos[d+1] = imos[d] + (dp[opLeft[i]].test(d) ? 1 : 0);for(int d=1; !done && d<=M; d++) if(dp[opRight[i]].test(d)) if(imos[min(M+1,d*(v+1))] - imos[d*v]){for(int e=d*v; e<=M; e++) if(dp[opLeft[i]].test(e)){expVal[opLeft[i]] = e;expVal[opRight[i]] = d;res[expPos[i] + expSize[opLeft[i]]] = '/';done = true;break;}}if(!done) return 0;}else if(opType[i] == -3){expPos[opLeft[i]] = expPos[i] + 1;expVal[opLeft[i]] = expVal[i];res[expPos[i]] = '(';res[expPos[i] + 1 + expSize[opLeft[i]]] = ')';}//cout << "res = " << res << endl;}cout << res << '\n';return 0;}struct ios_do_not_sync{ios_do_not_sync(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);}} ios_do_not_sync_instance;