概要
正の点を取ってる人が少なくて寂しいので共有します。
私が使っているものと同じですが、バグがあるかもしれません。(あったら私は終わり)
使いたい場合は自由に使ってください、責任は取れませんが...
コンストラクタで n と s を指定します。s は x, w 合わせた変数の個数です。(使われなかった分は圧縮するので多めに取って大丈夫です)。
変数のインデックスは 0-indexed です、問題文や入力と異なることに注意してください
constant() で定数、linear(v) で1次の項、quadratic(v0, v1) で2次の項の係数を取得します。
get_output() で使用されていない追加変数と係数が0の項を圧縮して出力するデータを std::string で取得できます。
get_M_L_maxC() は名前通りの関数ですが正常に動作してるか確認する術がないので知りません。
コードと使用例
2次以下の項はそのまま採用し、3次以上の項は c>0 なら定数 c、c<0 なら追加変数 w で c*w*(sum(v_i) - d + 1) とする、というシンプルな戦略を実装したものが以下のコードです。
#include <cassert> #include <cstddef> #include <string> #include <tuple> #include <utility> #include <vector> template <class CoefficientType = int> class hokudai_hitachi2018_output_formatter { public: using value_type = CoefficientType; using const_reference = const value_type &; using reference = value_type &; using size_type = ::std::size_t; protected: static constexpr size_type sig(const size_type &k) noexcept { return k * (k - 1) / 2; } static constexpr bool is_nonzero(const value_type &c) noexcept { return c != static_cast<value_type>(0); } static void maximize(value_type &x, const value_type &c) noexcept { if (x < c) { x = c; } else if (x < (-c)) { x = -c; } } size_type n_; value_type constant_; ::std::vector<value_type> linear_; ::std::vector<value_type> quadratic_; public: hokudai_hitachi2018_output_formatter(const size_type &n, const size_type &s) noexcept : n_(n), constant_(0), linear_(s, 0), quadratic_(sig(s), 0) {} size_type max_variable_index() const noexcept { return linear_.size(); } const_reference constant() const noexcept { return constant_; } reference constant() noexcept { return constant_; } const_reference linear(const size_type &variable) const noexcept { assert(variable < max_variable_index()); return linear_[variable]; } reference linear(const size_type &variable) noexcept { assert(variable < max_variable_index()); return linear_[variable]; } const_reference quadratic(const size_type &variable_0, const size_type &variable_1) const noexcept { assert(variable_0 < max_variable_index()); assert(variable_1 < max_variable_index()); if (variable_0 < variable_1) { return quadratic_[sig(variable_1) + variable_0]; } else if (variable_1 < variable_0) { return quadratic_[sig(variable_0) + variable_1]; } else { return linear(variable_0); } } reference quadratic(const size_type &variable_0, const size_type &variable_1) noexcept { assert(variable_0 < max_variable_index()); assert(variable_1 < max_variable_index()); if (variable_0 < variable_1) { return quadratic_[sig(variable_1) + variable_0]; } else if (variable_1 < variable_0) { return quadratic_[sig(variable_0) + variable_1]; } else { return linear(variable_0); } } ::std::tuple<size_type, size_type, value_type> get_M_L_maxC() const noexcept { const size_type vs = max_variable_index(); ::std::vector<bool> used(vs, false); size_type ret_L = 0; value_type ret_maxC = 0; if (is_nonzero(constant())) { ++ret_L; } for (size_type i = 0; i != vs; ++i) { const value_type &c = linear(i); if (is_nonzero(c)) { used[i] = true; ++ret_L; maximize(ret_maxC, c); } } for (size_type i = 0; i != vs; ++i) { for (size_type j = i; (++j) != vs;) { const value_type &c = quadratic(i, j); if (is_nonzero(c)) { used[i] = true; used[j] = true; ++ret_L; maximize(ret_maxC, c); } } } size_type ret_M = 0; for (size_type i = n_; i != vs; ++i) { if (used[i]) { ++ret_M; } } return ::std::make_tuple(ret_M, ret_L, ret_maxC); } ::std::string get_output() { const size_type vs = max_variable_index(); ::std::string ret_s; ::std::vector<size_type> offset(vs, 0); size_type L = 0; if (is_nonzero(constant())) { ++L; } for (size_type i = 0; i != vs; ++i) { const value_type &c = linear(i); if (is_nonzero(c)) { offset[i] = 1; ++L; } } for (size_type i = 0; i != vs; ++i) { for (size_type j = i; (++j) != vs;) { const value_type &c = quadratic(i, j); if (is_nonzero(c)) { offset[i] = 1; offset[j] = 1; ++L; } } } for (size_type i = 0; i != n_; ++i) { offset[i] = 1; } for (size_type i = 1; i != vs; ++i) { offset[i] += offset[i - 1]; } ret_s += ::std::to_string(offset.back()) + ' ' + ::std::to_string(L) + '\n'; { const value_type &c = constant(); if (is_nonzero(c)) { ret_s += ::std::to_string(0) + ' ' + ::std::to_string(c) + '\n'; } } for (size_type i = 0; i != vs; ++i) { const value_type &c = linear(i); if (is_nonzero(c)) { ret_s += ::std::to_string(1) + ' ' + ::std::to_string(c) + ' ' + ::std::to_string(offset[i]) + '\n'; } } for (size_type i = 0; i != vs; ++i) { for (size_type j = i; (++j) != vs;) { const value_type &c = quadratic(i, j); if (is_nonzero(c)) { ret_s += ::std::to_string(2) + ' ' + ::std::to_string(c) + ' ' + ::std::to_string(offset[i]) + ' ' + ::std::to_string(offset[j]) + '\n'; } } } return ::std::move(ret_s); } }; #include <iostream> #include <vector> int main() { int n, k; ::std::cin >> n >> k; int w = n; hokudai_hitachi2018_output_formatter<int> of(n, n + k); for (int i = 0;i != k;++i) { int d, c; ::std::cin >> d >> c; ::std::vector<int> v(d); for (auto &e : v) { ::std::cin >> e; --e; } if (d == 0) { of.constant() += c; } else if (d == 1) { of.linear(v[0]) += c; } else if (d == 2) { of.quadratic(v[0], v[1]) += c; } else { if (c > 0) { of.constant() += c; } else { for (const auto &e : v) { of.quadratic(e, w) += c; } of.linear(w) -= c*(d - 1); ++w; } } } ::std::cout << of.get_output(); return 0; }
A で 4.2*108、B で 2.3*108、C で 5.2*108 程度の得点が得られます。
