Chemist's Math

ICPC アジア地区予選2009F Chemist's Math

実装量がとにかく多い

構文解析パート

連立方程式パート

有理数ライブラリパート（実際にはdoubleで十分な精度が得られるらしい）

掃き出し法パート

係数の定数倍調整パート

構文解析パート

dict[O][0] = 2

dict[H][1] = 2

dict[H][2] = -2

dict[O][2] = -1

構文解析自体は、再帰下降で簡単にできます。

括弧の向きとか矢印の向きとかは注意

連立方程式パート

誤差で死なないために有理数ライブラリを作りましょう

掃き出し法で使うので、基本的な四則演算系の演算子オーバーロードはしておきましょう

あと、整数型と親和性が高いと多分嬉しい

とすれば良いです。

C++なら、

code: cpp

Matrix A;

A.push_back_row(num);

}

みたいに実装できると嬉しいね

掃き出し法はけんちょんさんの記事を見て実装します

係数の定数倍調整パート

答えが次のような感じで得られます。

$ \begin{pmatrix}1&0&0&\ a_1/b_1\\0&1&0&\ a_2/b_2\\0&0&1& a_3/b_3\\0&0&0&0\\\vdots& &\ddots& \vdots\\0&0&0&0\end{pmatrix} \begin{pmatrix}t_1\\t_2\\t_3\\t_4\end{pmatrix} = \begin{pmatrix}0\\0\\0\\0\end{pmatrix}

$ t_i = \frac{a_i}{b_i}t_n\ \ (1\leq i \leq n-1)

$ t_n = \mathrm{lcm}_{i=1..n-1} \left( b_i \right)

で計算できます。有理数ライブラリを作っていると、ここを簡単に計算できます。

まとめ

実装例です。

code: (cpp)

# include <ngng628_library/base>

# include <ngng628_library/fraction>

# include <ngng628_library/matrix>

using State = string::const_iterator;

void skip(State& it) { while (isspace(*it)) ++it; }

void skip(State& it, char c) { assert(c == *it); ++it; }

void skip(State& it, const string& s) { for (char c : s) { assert(c == *it); ++it; } }

void skip(State& it, int n) { while (n--) ++it; }

string erase_all_space(string s) { s.erase(remove_if(all(s), [](char c){ return isspace(c); }), s.end()); return s; }

int ctoi(char c) { assert('0' <= c and c <= '9'); return c - '0'; }

bool Main() {

// ────────────────────────────────

// 1. 入力

// ────────────────────────────────

string s;

cin >> s;

s.pop_back();

if (s.empty()) return false;

reverse(all(s));

// ────────────────────────────────

// 2. 構文解析

// ────────────────────────────────

struct Parser {

string s;

int n_terms;

map<string, vec<Fraction>> mp;

Parser(string _s) : s(_s), it(s.begin()) {}

void parse() {

n_terms = count(all(s), '+') + 2;

chemical_equation();

}

private:

State it;

void chemical_equation() {

molecule_sequence();

}

void molecule_sequence() {

int sgn = 1;

molecule(sgn, 0, 1);

int term_index = 1;

for (; it != s.end();) {

if (*it == '+') {

skip(it, '+');

molecule(sgn, term_index++, 1);

}

else if (*it == '>') {

skip(it, ">-");

sgn *= -1;

}

else {

molecule(sgn, term_index++, 1);

}

}

}

void molecule(int sgn, int i, int k) {

const set<char> delimiters = {'+', '>', '('};

while (it != s.end() and not delimiters.count(*it)) group(sgn, i, k);

}

void group(int sgn, int i, int k) {

k *= isdigit(*it) ? number() : 1;

unit_group(sgn, i, k);

}

void unit_group(int sgn, int i, int k) {

if (*it == ')') {

skip(it, ')');

molecule(sgn, i, k);

skip(it, '(');

}

else {

chemical_element(sgn, i, k);

}

}

void chemical_element(int sgn, int i, int k) {

string elem;

if (islower(*it)) {

elem.push_back(*it++);

}

elem.push_back(*it++);

}

int number() {

int res = 0;

int ratio = 1;

for (; isdigit(*it); ++it) {

res = res + ratio * ctoi(*it);

ratio *= 10;

}

return res;

}

};

auto parser = Parser(s);

parser.parse();

// ────────────────────────────────

// 3. 拡大係数行列の生成

// ────────────────────────────────

Matrix<Fraction> mat(0, parser.n_terms);

for (auto p : parser.mp) mat.push_back_row(p.second);

int h = mat.n_rows();

vec<Fraction> zeros(h, 0);

mat.push_back_col(zeros);

int w = mat.n_cols();

// ────────────────────────────────

// 4. 掃き出し法をする

// ────────────────────────────────

sweep(mat, true);

// ────────────────────────────────

// 5. 係数を調整

// ────────────────────────────────

int k = 1;

rep (i, h) k = lcm(k, mat(i, w - 2).den());

vi ans(w - 1);

ans.back() = k;

// ────────────────────────────────

// 6. 答えの出力

// ────────────────────────────────

reverse(all(ans));

cout << ans << endl;

return true;

}

int32_t main() {

while (Main());

}