#796363 (C++17) No.2069 み世界数式

提出ソース

結果

問題	No.2069 み世界数式
ユーザー	👑 Nachia
提出日時	2022-09-09 00:10:09
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	3 ms / 2,000 ms
コード長	9,586 bytes
コンパイル時間	1,426 ms
コンパイル使用メモリ	94,692 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-11-24 21:38:36
合計ジャッジ時間	3,068 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,820 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,816 KB
testcase_04	AC	1 ms 6,816 KB
testcase_05	AC	2 ms 6,820 KB
testcase_06	AC	2 ms 6,816 KB
testcase_07	AC	2 ms 6,820 KB
testcase_08	AC	2 ms 6,820 KB
testcase_09	AC	2 ms 6,820 KB
testcase_10	AC	2 ms 6,816 KB
testcase_11	AC	2 ms 6,816 KB
testcase_12	AC	3 ms 6,820 KB
testcase_13	AC	2 ms 6,816 KB
testcase_14	AC	2 ms 6,816 KB
testcase_15	AC	3 ms 6,816 KB
testcase_16	AC	2 ms 6,820 KB
testcase_17	AC	2 ms 6,816 KB
testcase_18	AC	2 ms 6,816 KB
testcase_19	AC	3 ms 6,820 KB
testcase_20	AC	3 ms 6,816 KB
testcase_21	AC	2 ms 6,816 KB
testcase_22	AC	2 ms 6,820 KB
testcase_23	AC	2 ms 6,820 KB
testcase_24	AC	3 ms 6,816 KB
testcase_25	AC	2 ms 6,820 KB
testcase_26	AC	2 ms 6,820 KB
testcase_27	AC	2 ms 6,816 KB
testcase_28	AC	2 ms 6,816 KB
testcase_29	AC	2 ms 6,816 KB
testcase_30	AC	2 ms 6,820 KB
testcase_31	AC	2 ms 6,820 KB
testcase_32	AC	2 ms 6,820 KB
testcase_33	AC	2 ms 6,820 KB
testcase_34	AC	2 ms 6,816 KB
testcase_35	AC	2 ms 6,820 KB
testcase_36	AC	2 ms 6,816 KB
testcase_37	AC	2 ms 6,820 KB
testcase_38	AC	2 ms 6,816 KB
testcase_39	AC	2 ms 6,816 KB
testcase_40	AC	2 ms 6,816 KB
testcase_41	AC	2 ms 6,820 KB
testcase_42	AC	2 ms 6,816 KB
testcase_43	AC	2 ms 6,820 KB
testcase_44	AC	2 ms 6,816 KB

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

ソースコード

raw source code

#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;

yukicoder

結果

テストケース

ソースコード