ICPC-Kobunkaiseki-2023-tutorial

みなさんこんにちは。

ICPCに向けて構文解析バチャを立てましたので、解説記事を投稿します。

基本的には以下のテンプレを前提として解説します。

code: (cpp)

# include <bits/stdc++.h>

# define all(v) std::begin(v), std::end(v)

# define rall(v) std::rbegin(v), std::rend(v)

# define len(v) (ll(std::size(v)))

# define overload3(_1,_2,_3,name,...) name

# define _step(n) _rep(_,n)

# define _rep(i,n) _repr(i,0,n)

# define _repr(i,b,e) for(int i=(b), i##_len=(e); i<i##_len; ++i)

# define rep(...) overload3(__VA_ARGS__, _repr, _rep, _step)(__VA_ARGS__)

using namespace std;

using ll = long long;

using ld = long double;

using pll = pair<ll, ll>;

constexpr ll inf = numeric_limits<ll>::max() / 2 - 1;

英語の問題は、はじめに（省略した）和訳を載せました。

table: 個人的難易度表

問題ID 構文解析の難しさ 構文解析以外の難しさ 実装の大変さ

A ★4 ★2 ★2

B ★2 ★2 ★2

C ★3 ★4 ★3

D ★3 ★4 ★2

E ★5 ★2 ★3

F ★4 ★3 ★3

G ★4 ★3 ★4

H ★4 ★2 ★2

I ★3 ★2 ★3

J ★4 ★3 ★3

K ★4 ★4 ★5

L ★4 ★2 ★5

M ★2 ★3 ★2

N ★2 ★2 ★2

O ★2 ★2 ★2

P ★4 ★4 ★4

Q ★3 ★4 ★4

L ★2 ★4 ★4

S ★1 ★1 ★2

T ★1 ★2 ★2

U ★2 ★4 ★3

V ★3 ★4 ★4

A問題〜D問題

hr.icon

A問題

hr.icon

そして、

code: (cpp)

struct Parser {

string s;

string::const_iterator it;

vector<vector<char>> ops;

Parser() = default;

Parser(const string& _s, const vector<vector<char>>& _ops) : s(_s), ops(_ops) { it = s.begin(); }

ll parse() { return expr(); }

ll expr(int depth = 0) {

if (depth == 3) return fact();

ll acc = expr(depth + 1);

char op = *it++;

ll other = expr(depth + 1);

acc = operate(acc, op, other);

}

return acc;

}

ll fact() {

if (isdigit(*it)) return number();

else {

ll ret = expr();

return ret;

}

}

ll operate(ll a, char op, ll b) const {

switch (op) {

case '+': return a + b;

case '-': return a - b;

case '*': return a * b;

}

assert(false);

}

bool in(char c, const vector<char>& o) const {

return count(all(o), c);

}

};

int main() {

string s;

cin >> s;

ll ans = -inf;

rep (i, 3) rep (j, 3) rep (k, 3) {

vector<vector<char>> ops(3);

chmax(ans, Parser(s, ops).parse());

}

cout << ans << endl;

}

B問題

hr.icon

構文解析パートですが、S問題を知っているのであれば、それを真似て、構文規則を再帰関数に落とし込むような実装を考えれば良いです。

基本的に構文解析では、下手に自分流に構文規則をアレンジするよりも、問題文中のBNF記法をそのまま書き写すようにしたほうがバグりにくいです。

code: (cpp)

struct Parser {

string s;

string::const_iterator it;

map<char, bool> mp;

Parser(string s, const map<char, bool>& mp) : s(s), mp(mp), it(s.begin()) {}

bool parse() {

return formula();

}

bool formula() {

if (*it == 'T') {

it++;

return true;

}

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

it++;

return false;

}

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

it++;

return !formula();

}

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

it++;

bool lhs = formula();

char c = *it++;

if (c == '-') it++, c = '>';

bool rhs = formula();

bool ret = false;

switch (c) {

case '*': ret = lhs & rhs; break;

case '+': ret = lhs | rhs; break;

case '>': ret = (!lhs & !rhs) | ((lhs | rhs) & rhs); break;

}

assert(*it++ == ')');

return ret;

}

else assert(false);

return true;

}

};

int main() {

while (true) {

string s;

cin >> s;

if (s == "#") break;

string a = s.substr(0, s.find('='));

string b = s.substr(s.find('=') + 1);

int n_values = 'k' - 'a' + 1;

bool ok = true;

rep (mask, 1 << n_values) {

map<char, bool> mp;

ok &= Parser(a, mp).parse() == Parser(b, mp).parse();

}

cout << (ok ? "YES" : "NO") << endl;

}

}

C問題

hr.icon

前から解いていく人にとっては、初めて「問題文を見ただけでウッとする」タイプの問題になると思います。

問題文を和訳すると、

配列の宣言と代入ができるだけの簡単なプログラムが与えられるのでバグがないか判定してください。

ここで、バグとは以下のどちらかです

1. 配列外参照

code: (py)

2. まだ初期化されていない要素へのアクセス

code: (py)

これら以外のバグ、例えば宣言していない配列の使用などは考えなくてよいです。

問題文を読むのこそ大変ですが、構文解析自体はS問題の応用で十分対応できます。

code: (cpp)

constexpr int NIL = -1;

struct Parser {

map<char, vector<ll>> mp;

pair<int, int> cur;

int h;

map<ll, ll> comp;

vector<string> s;

Parser() = default;

Parser(vector<string> s) : cur(0, 0), h(s.size()), s(s) {

vector<ll> v;

rep (i, 0, h) {

cur = {i, 0};

ll value = number2();

v.push_back(value);

}

else {

cur.second++;

}

}

}

sort(all(v));

v.erase(unique(all(v)), v.end());

rep (i, 0, v.size()) {

}

}

int parse() {

rep (i, 0, h) {

cur.first = i;

cur.second = 0;

if (program()) return i + 1;

}

return 0;

}

bool program() {

if (t.find('=') == string::npos) return declaration();

else return assignment();

}

bool declaration() {

assert(isalpha(name));

ll size = number();

return false;

}

bool assignment() {

assert(isalpha(name));

ll index = expression();

ll value = expression();

if (value == NIL) return true;

return false;

}

ll expression() {

return number();

}

else {

ll index = expression();

}

}

ll number() {

ll res = 0;

}

}

ll number2() {

ll res = 0;

}

return res;

}

};

int main() {

while (true) {

string s;

cin >> s;

if (s == ".") break;

vector<string> ss;

for (; s != "."; cin >> s) {

ss.push_back(s);

}

int ans = Parser(ss).parse();

cout << ans << endl;

}

}

D問題

hr.icon

問題を和訳します。

覆面算をしてください。

たとえ出現位置が異なっても、同じアルファベットに異なる記号は対応させられません

異なるアルファベットには異なる記号を対応させる必要があります。つまり一対一で対応させてください。

ありえる対応のさせかたの通り数を出力してください。

出現するアルファベットは最大で31文字であるため、アルファベットへの対応のさせ方を全探索しても間に合います。

code: (py)

import itertools

s = input()

alphas = list(set(filter(lambda c: c.isalpha(), s)))

n_alphas = len(alphas)

if n_alphas > len(symbol):

print(0)

exit()

cnt = 0

for ops in itertools.permutations(symbol, n_alphas):

t = s

for c, op in zip(alphas, ops):

t = t.replace(c, op)

if t.count('=') != 1:

continue

u = ''

ok = True

i = 0

while i < len(t):

ok = False

break

else:

v = ''

i += 1

u += str(int(v, 2))

i -= 1

else:

i += 1

pos = u.find('=')

continue

lhs = 0

rhs = 0

ok = True

for i in range(1, len(expr) - 1):

ok = False

for i in range(1, len(expr) - 1):

ok = False

for i in range(1, len(expr)):

ok = False

for i in range(0, len(expr) - 1):

ok = False

if not ok:

continue

try:

lhs = int(eval(ul))

except:

ok = False

try:

rhs = int(eval(ur))

except:

rhs = 0

ok = False

if lhs == rhs and ok:

cnt += 1

print(cnt)

E問題〜H問題

hr.icon

E問題

hr.icon

code: (cpp)

constexpr ll MOD = ll(1e9) + 7;

struct Parser {

string s;

int cur;

Parser() = default;

Parser(string _s) : s(erase_all_space(_s)) {

cur = len(s) - 1;

}

ll parse() {

return expr();

}

ll expr() {

deque<ll> terms;

terms.push_front(term());

terms.push_front(term());

}

rep (i, 1, len(terms)) {

while (not (y == 0 || ret == 0)) {

ret >>= 1;

y--;

}

}

return ret;

}

ll term() {

return number();

}

else {

ll val = expr() % MOD;

val = (val * val) % MOD;

return val;

}

}

ll number() {

deque<char> dq;

}

return stoll(string(all(dq)));

}

};

int main() {

while (true) {

string s;

getline(cin, s);

if (s == "#") break;

cout << Parser(s).parse() << endl;

}

}

F問題

hr.icon

問題文を和訳すると、

続く1行に式が与えられるので、式を計算した結果を出力してください。

ここで、式は5つの演算と括弧からなります。演算は左結合です。

BNFが書かれていないため、自分で生成規則を考える必要があります。

考えると次のようになります。

code: (txt)

<expr> ::= <factor> | <expr><op><factor>

<op> ::= "u" | "i" | "d" | "s"

<factor> ::= <set> | "(" <expr> ")"

<set> ::= c<var> | <var>

<var> ::= "A" | "B" | "C" | "D" | "E"

あとはS問題と同様に再帰下降構文解析をすれば良いです。

実は {和, 積, 差, 対称差} 集合を行うメソッドはC++では標準で提供されているので、それを使えば良いです。

問題文に式が丁寧に書いてあるため、それを見ながら for 文を書いても良いです。

code: (cpp)

void print(const set<int>& st) {

if (st.empty()) {

cout << "NULL" << endl;

return;

}

int n = st.size();

int i = 0;

for (auto a : st) {

i++;

}

}

struct Parser {

map<char, set<int>> mp;

string s;

set<int> u;

string::const_iterator it;

Parser() = default;

Parser(map<char, set<int>> mp, string s) :mp(mp), s(s), it(s.begin()) {}

set<int> parse() {

u.clear();

for (auto vi : v) u.insert(vi);

}

it = s.begin();

return expr();

}

set<int> expr() {

set<int> now = set_expr();

while (it != s.end() && *it != ')') {

if (*it == 'u') {

++it;

auto st = set_expr();

set<int> res;

set_union(now.begin(), now.end(), st.begin(), st.end(), inserter(res, res.end()));

now = res;

}

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

++it;

auto st = set_expr();

set<int> res;

set_intersection(now.begin(), now.end(), st.begin(), st.end(), inserter(res, res.end()));

now = res;

}

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

++it;

auto st = set_expr();

set<int> res;

set_difference(now.begin(), now.end(), st.begin(), st.end(), inserter(res, res.end()));

now = res;

}

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

++it;

auto st = set_expr();

set<int> res;

set_symmetric_difference(now.begin(), now.end(), st.begin(), st.end(), inserter(res, res.end()));

now = res;

}

}

return now;

}

set<int> set_expr() {

if (*it == '(') {

it++;

auto ret = expr();

it++;

return ret;

}

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

++it;

set<int> st = set_expr();

set<int> res;

for (auto ui : u) if (not st.count(ui)) res.insert(ui);

return res;

}

else {

assert(isalpha(*it));

}

}

};

int main() {

while (true) {

map<char, set<int>> mp;

while (true) {

char c;

if (!(cin >> c)) return 0;

int n;

cin >> n;

if (c == 'R') break;

set<int> v;

rep (_, 0, n) {

int x;

cin >> x;

v.insert(x);

}

}

string s;

cin >> s;

auto ans = Parser(mp, s).parse();

print(ans);

}

}

G問題

hr.icon

構文解析は再帰下降構文解析を行えば良いです。

状態の持ち方ですが、私はポインタで左と右の子を持つような構造体を作りました。

code: (cpp)

class Node;

using pNode = shared_ptr<Node>;

struct Node {

int value;

pNode left, right;

};

木の情報はこれで表現し、二分木の結合は幅優先探索の要領で行えば良いです。

二分木の出力は再帰関数を使って深さ優先探索的に「左の子→親→右の子」と出力するのが良いです。

1つ目の木には左の子が存在するが、2つ目の木には左の子が存在しない（右も同様）ようなパターンに注意してください。

code: (cpp)

struct Parser {

string s;

string::const_iterator it;

Parser() = default;

Parser(const string& s) : s(s) { it = this->s.begin(); }

pNode parse() {

return tree();

}

pNode tree() {

pNode node = make_shared<Node>();

if (*it == '(') {

it++;

node->left = tree();

assert(*it++ == ')');

}

else {

assert(it == s.end() || *it == ')');

return nullptr;

}

assert(*it++ == '[');

node-> value = number();

assert(*it++ == ']');

assert(*it++ == '(');

node->right = tree();

assert(*it++ == ')');

return node;

}

};

int main() {

string s, t;

cin >> s >> t;

auto ns = Parser(s).parse();

auto nt = Parser(t).parse();

pNode root = make_shared<Node>();

queue<tuple<pNode, pNode, pNode>> que;

que.emplace(root, ns, nt);

while (not que.empty()) {

que.pop();

a->value = b->value + c->value;

if (b->left != nullptr && c->left != nullptr) {

pNode leftchild = make_shared<Node>();

a->left = leftchild;

que.emplace(leftchild, b->left, c->left);

}

if (b->right != nullptr && c->right != nullptr) {

pNode rightchild = make_shared<Node>();

a->right = rightchild;

que.emplace(rightchild, b->right, c->right);

}

}

string s = "";

if (now == nullptr) {

s = "";

}

else {

s += "(" + rec(rec, now->left) + ")";

s += "(" + rec(rec, now->right) + ")";

}

return s;

};

cout << rec(rec, root) << endl;

}

H問題

hr.icon

A問題の応用です。

code: (cpp)

struct Parser {

string s;

string::const_iterator it;

vector<ll> ops;

vector<int> ord;

bool zflag;

Parser() = default;

Parser(const string& _s, const vector<ll> _ops) : s(_s), ops(_ops), ord(_s.size(), -1), zflag(false) {

it = s.begin();

int cur = 0;

rep (i, 0, len(s)) {

cur++;

}

}

}

ll parse() {

return expr();

}

ll expr(int depth = 0) {

if (depth == len(ops)) {

if (*it == '(') {

assert(*it++ == '(');

ll val = expr();

assert(*it++ == ')');

return val;

}

else {

return number();

}

}

ll acc = expr(depth + 1);

char op = *it++;

ll other = expr(depth + 1);

acc = eval(acc, op, other);

}

return acc;

}

ll eval(ll a, char op, ll b) {

switch (op) {

case '+': return a + b;

case '-': return a - b;

case '*': return a * b;

case '/': if (b == 0) { zflag = true; b = 1; } return a / b;

}

assert(false);

}

};

int main() {

while (true) {

string s;

getline(cin, s);

if (s == "#") break;

int sum = count(all(s), '+') + count(all(s), '-') + count(all(s), '*') + count(all(s), '/');

set<ll> st;

vector<ll> ops(sum, 0);

iota(all(ops), 0);

do {

Parser parser(s, ops);

ll res = parser.parse();

if (not parser.zflag) st.insert(res);

} while (next_permutation(all(ops)));

cout << st.size() << endl;

}

}

I問題〜L問題

hr.icon

I問題

hr.icon

構文規則がいつもと異なるため、難しく感じるかもしれません。逆に構文規則に慣れていない人はこちらの方が考えやすいかもしれません。

実装を見てもらったほうが早いかもしれません。

code: (cpp)

struct Parser {

vs s;

int i, j;

Parser(vector<string> s) : s(s) {}

ll parse() {

i = j = 0;

return expr();

}

ll expr(int depth = 0) {

}

i += 1;

auto v = numbers(depth + 1);

ll s = 0;

for (ll vi : v) s += vi;

return s;

}

i += 1;

auto v = numbers(depth + 1);

ll s = 1;

for (ll vi : v) s *= vi;

return s;

}

else {

assert(false);

}

}

vector<ll> numbers(int depth) {

vector<ll> ret;

while (i < s.size()) {

if (dep(t) == depth) {

ll v = expr(depth);

i += 1;

ret.push_back(v);

}

else {

assert(dep(t) < depth);

i--;

break;

}

}

return ret;

}

int dep(string w) {

return count(w.begin(), w.end(), '.');

}

};

J問題

hr.icon

和訳すると、

二次元構文解析をしてください。

構文規則といえばこの問題です。

一見嫌すぎる問題ですが、S問題と同じようにとりあえず再帰関数を構文規則通り書いていけば案外すんなり解けます。

とにかく、まずは構文規則通りに再帰関数を書くことが重要です。

code: (cpp)

struct Parser {

const int h, w;

vector<string> s;

mint parse() {

int base = find_base(0, h, 0);

int cur = 0;

return expr(0, base, h, cur);

}

mint expr(int top, int base, int bottom, int& cur) {

mint acc = term(top, base, bottom, cur);

bool ok = true;

return ok;

};

while (ok()) {

assert(op == '+' || op == '-');

mint other = term(top, base, bottom, cur);

if (op == '+') {

acc += other;

}

else {

acc -= other;

}

}

return acc;

}

mint term(int top, int base, int bottom, int& cur) {

mint acc = factor(top, base, bottom, cur);

bool ok = true;

return ok;

};

while (ok()) {

mint other = factor(top, base, bottom, cur);

acc *= other;

}

return acc;

}

mint factor(int top, int base, int bottom, int& cur) {

return -factor(top, base, bottom, cur);

}

return fraction(top, base, bottom, cur);

}

return powexpr(top, base, bottom, cur);

}

else {

cur++;

return factor(top, base, bottom, cur);

}

}

mint fraction(int top, int base, int bottom, int& cur) {

int cur_num = cur;

int cur_den = cur;

mint num = expr(top, find_base(top, base, cur_num), base, cur_num);

mint den = expr(base + 1, find_base(base + 1, bottom, cur_den), bottom, cur_den);

return num / den;

}

mint powexpr(int top, int base, int bottom, int& cur) {

mint val;

val = expr(top, base, bottom, cur);

}

else {

val = number(base, cur);

}

ll e = raw_number(base - 1, cur);

val = val.pow(e);

}

return val;

}

int find_base(int top, int bottom, int cur) {

for (int i = top; i < bottom; i++) {

}

return find_base(top, bottom, cur + 1);

}

mint number(int base, int& cur) {

mint ret = 0;

}

return ret;

}

ll raw_number(int base, int& cur) {

ll ret = 0;

}

return ret;

}

};

K問題

hr.icon

辛さで言えば最上位だと思います。

code: 逆からみないバージョンの実装 (cpp)

vector<string> splited(string s) {

vector<string> ret;

const int n = s.size();

rep (i, 0, n) {

ret.push_back(s.substr(i, 2));

i += 1;

}

ret.push_back(s.substr(i, 2));

i += 1;

}

string t;

}

ret.push_back(t);

i--;

}

else {

ret.push_back(s.substr(i, 1));

}

}

return ret;

}

struct Parser {

vector<string> s;

int cur;

map<string, map<ll, ll>> mp;

Parser(vector<string> _s) : s(_s), cur(0) {}

map<string, map<ll, ll>> parse() {

molecule_sequence();

return mp;

}

void molecule_sequence() {

int cnt = 0;

cnt++;

cnt++;

}

}

map<string, ll> molecule() {

map<string, ll> ret;

}

return ret;

}

map<string, ll> group() {

map<string, ll> ret = unit_group();

cur++;

value *= num;

}

}

return ret;

}

map<string, ll> unit_group() {

auto res = molecule();

return res;

}

else {

cur++;

return ret;

}

}

};

void solve(string s) {

vector<string> t = splited(s);

vector<string> tl, tr;

{

int i = 0;

tl.push_back("->");

i++;

tr.push_back(".");

}

auto lhs = Parser(tl).parse();

auto rhs = Parser(tr).parse();

map<string, ll> elems;

ll left_n_terms = 0;

chmax(left_n_terms, nt);

}

ll right_n_terms = 0;

chmax(right_n_terms, nt);

}

const ll n_elems = elems.size();

const int n_terms = left_n_terms + 1 + right_n_terms + 1;

M mat(n_elems, n_terms + 1, Fraction(0));

}

}

sweep(mat);

ll k = 1;

rep (i, n_elems) {

Fraction v = mat(i, n_terms - 1);

k = lcm(k, v.den());

}

rep (i, n_terms - 1) {

cout << -mat(i, n_terms - 1) * Fraction(k) << " ";

}

cout << k << endl;

}

L問題

hr.icon

和訳すると、

https://gyazo.com/50bc1754fcede062603d90ae57abdec5

基本的には上の画像が本質で、行列の要素が空白区切りで与えられますが、行列が並べられている場合があるのでうまく結合させる必要があります。

構文規則は簡単で、再帰降下すれば良いです。言われた通りの演算ができる行列ライブラリを作るのが本質です。

四則演算と転置行列の他に次のようなメソッドがあると良いでしょう。

code: (cpp)

struct Matrix {

// 行のスライス

Matrix selected_rows(const vector<int>& indices) {

vector<vector<T>> acc;

for (int i : indices) {

}

return Matrix(acc);

}

// 列のスライス

Matrix selected_cols(const vector<int>& indices) {

vector<vector<T>> acc;

Matrix mt = transposed();

for (int j : indices) {

}

return Matrix(acc).transposed();

}

// 行列を横に合体させる

//

Matrix row_concat(const Matrix& other) {

assert(n_rows() == other.n_rows());

Matrix ret(n_rows(), n_cols() + other.n_cols());

const int w = n_cols();

rep (i, n_rows()) {

}

return ret;

}

// 行列を縦に合体させる

//

Matrix col_concat(const Matrix& other) {

assert(n_cols() == other.n_cols());

Matrix ret(n_rows() + other.n_rows(), n_cols());

const int h = n_rows();

rep (i, h) {

}

rep (i, other.n_rows()) {

}

return ret;

}

};

code: (cpp)

struct Parser {

map<char, M> mp;

vector<string> s;

int line;

string::const_iterator it;

Parser() = default;

Parser(const vector<string>& _s) : s(_s) {

}

void parse() {

const int n = len(s);

rep (i, 0, n) {

line = i;

program();

}

}

void program() {

char var = *it++;

assert(*it++ == '=');

M res = expr();

assert(*it++ == '.');

cout << res << endl;

}

M expr() {

M acc = term();

while (*it == '+' || *it == '-') {

char op = *it++;

M other = term();

if (op == '+') {

acc += other;

}

else {

acc -= other;

}

}

return acc;

}

M term() {

M acc = factor();

while (*it == '*') {

assert(*it++ == '*');

M other = factor();

if (isnumber(acc) && isnumber(other)) {

acc *= other;

}

else if (isnumber(acc) && not isnumber(other)) {

acc = acc(0, 0) * other;

}

else if (not isnumber(acc) && isnumber(other)) {

acc *= other(0, 0);

}

else {

assert(not isnumber(acc) && not isnumber(other));

acc *= other;

}

}

return acc;

}

M factor() {

if (*it == '-') {

assert(*it++ == '-');

M ret = factor();

return -ret;

}

return primary();

}

M primary() {

M ret;

if (isdigit(*it)) {

mint val = inum();

ret = M(1, 1, val);

}

else if (isalpha(*it)) {

}

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

assert(*it++ == '(');

ret = expr();

assert(*it++ == ')');

}

else {

assert(*it == '[');

ret = matrix();

}

while (*it == '(' || *it == '\'') {

if (*it == '(') {

assert(*it++ == '(');

M is = expr();

assert(*it++ == ',');

M js = expr();

assert(*it++ == ')');

assert(is.n_rows() == 1);

assert(js.n_rows() == 1);

{

vector<int> indices;

rep (j, 0, is.n_cols()) {

indices.push_back(is(0, j).val() - 1);

}

ret = ret.selected_rows(indices);

}

{

vector<int> indices;

rep (j, 0, js.n_cols()) {

indices.push_back(js(0, j).val() - 1);

}

ret = ret.selected_cols(indices);

}

}

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

assert(*it++ == '\'');

ret = ret.transposed();

}

}

return ret;

}

M matrix() {

assert(*it++ == '[');

M row = row_seq();

assert(*it++ == ']');

return row;

}

M row_seq() {

M acc = row();

while (*it == ';') {

assert(*it++ == ';');

M other = row();

acc = acc.col_concat(other);

}

return acc;

}

M row() {

M acc = expr();

while (*it == ' ') {

assert(*it++ == ' ');

M other = expr();

acc = acc.row_concat(other);

}

return acc;

}

bool isnumber(const M& mat) {

return mat.n_rows() == 1 && mat.n_cols() == 1;

}

mint inum() {

mint ret = 0;

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

ret = 10*ret + (*it - '0');

}

return ret;

}

};

M問題〜P問題

hr.icon

M問題

hr.icon

構文解析は再帰降下で良いです。

code: (cpp)

struct Parser {

string s;

string::const_iterator it;

Parser() = default;

Parser(const string& _s) : s(_s) {

it = s.cbegin();

}

ll parse() {

return result();

}

ll result() {

if (isdigit(*it)) {

return number();

}

else {

assert(*it++ == '[');

vector<ll> a;

bool islast = isdigit(*it);

a.push_back(result());

while (*it != ']') {

assert(*it == '[' || isdigit(*it));

a.push_back(result());

}

assert(*it++ == ']');

sort(a.begin(), a.end());

ll sum = 0;

rep (i, 0, len(a) / 2 + 1) {

}

return sum;

}

}

};

N問題

hr.icon

S問題と同様に再帰降下構文解析をすれば良いです。

code: (cpp)

struct Parser {

string s;

string::const_iterator it;

map<char, int> mp;

Parser() = default;

Parser(const string& _s, const map<char, int>& _mp) : s(_s), mp(_mp) {

it = s.cbegin();

}

int parse() {

return formula();

}

int formula() {

if (*it == '-') {

assert(*it++ == '-');

int x = formula();

return 2 - x;

}

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

assert(*it++ == '(');

int x = formula();

char op = *it++;

int y = formula();

int xy = op == '*' ? min(x, y) : max(x, y);

assert(*it++ == ')');

return xy;

}

else {

}

}

};

int main() {

while (true) {

string s;

cin >> s;

if (s == ".") break;

int cnt = 0;

rep (p, 0, 3) rep (q, 0, 3) rep (r, 0, 3) {

map<char, int> mp = {

{'P', p},

{'Q', q},

{'R', r},

};

if (Parser(s, mp).parse() == 2) cnt++;

}

cout << cnt << endl;

}

}

O問題

hr.icon

S問題と同様に再帰降下構文解析をすればよいです。

code: (cpp)

struct Parser {

string s;

string::const_iterator it;

Parser() = default;

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

string parse() {

return cipher();

}

string cipher() {

string now = str();

while (it != s.end() && *it != ']') {

now += str();

}

return now;

}

string str() {

if (*it == '[') {

assert(*it++ == '[');

auto rev = cipher();

assert(*it++ == ']');

reverse(rev.begin(), rev.end());

return rev;

}

else {

return letter();

}

}

string letter() {

if (*it == '+') {

it++;

return succ(letter());

}

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

it++;

return pred(letter());

}

else {

return string(1, *it++);

}

}

string succ(string x) {

}

string pred(string x) {

}

char mod_add(char c, int i) {

return ((c - 'A' + i) % 26 + 26) % 26 + 'A';

}

};

int main() {

while (true) {

string s;

cin >> s;

if (s == ".") break;

string ans = string(1, 'Z' + 1);

if (auto i = s.find('?'); i == string::npos) {

ans = min(ans, Parser(s).parse());

}

else {

for (char c = 'A'; c <= 'Z'; c++) {

rec(rec, s.replace(i, 1, string(1, c)));

}

}

};

rec(rec, s);

cout << ans << endl;

}

}

P問題

hr.icon

和訳すると、

やるだけではあるのですが、点と線分の区別が付けづらいです。

交点や対称な点はググりながら頑張って理解すると良いです。

code: (cpp)

struct P {

ld x, y;

P() : x(0), y(0) {}

P(ld _x, ld _y) : x(_x), y(_y) {}

friend ostream& operator <<(ostream& os, const P& p) {

return os << '(' << p.x << ", " << p.y << ')';

}

};

struct Line {

P s, t;

bool isline;

Line() = default;

Line(const P& _s) : s(_s), isline(false) {}

Line(const P& _s, const P& _t) : s(_s), t(_t), isline(true) {}

friend ostream& operator <<(ostream& os, const Line& line) {

if (line.isline) {

return os << '(' << line.s << "@" << line.t << ')';

}

else {

return os << line.s;

}

}

friend Line operator *(const Line& a, const Line& b) {

if (a.isline && b.isline) {

return a.cross_point(b);

}

else if (a.isline && not b.isline) {

return a.symmetry_point(b);

}

else if (not a.isline && b.isline) {

return b.symmetry_point(a);

}

else {

assert(not a.isline && not b.isline);

return Line(a.s, b.s);

}

}

Line cross_point(const Line& other) const {

assert(this->isline);

assert(other.isline);

auto p1 = this->s;

auto p3 = this->t;

auto p2 = other.s;

auto p4 = other.t;

ld s1 = ((p4.x - p2.x) * (p1.y - p2.y) - (p4.y - p2.y) * (p1.x - p2.x)) / 2.0;

ld s2 = ((p4.x - p2.x) * (p2.y - p3.y) - (p4.y - p2.y) * (p2.x - p3.x)) / 2.0;

ld x = p1.x + (p3.x - p1.x) * s1 / (s1 + s2);

ld y = p1.y + (p3.y - p1.y) * s1 / (s1 + s2);

return Line(P(x, y));

}

Line symmetry_point(const Line& other) const {

assert(this->isline);

assert(not other.isline);

ld dx = this->t.x - this->s.x;

ld dy = this->t.y - this->s.y;

ld a = dy;

ld b = -dx;

ld c = this->s.y * dx - this->s.x * dy;

ld den = a*a + b*b;

ld x2 = (-(a*a - b*b) * x1 - a*b*y1*2.0 - c*a*2.0) / den;

ld y2 = (-a*b*x1*2.0 + (a*a - b*b)*y1 - b*c*2.0) / den;

return Line(P(x2, y2));

}

};

struct Parser {

string s;

string::const_iterator it;

Parser() = default;

Parser(const string& _s) : s(_s) {

it = s.cbegin();

}

Line parse() {

return point();

}

Line point() {

auto acc = term();

while (it != s.cend() && *it != ')') {

assert(*it++ == '@');

auto other = term();

acc = acc * other;

}

return acc;

}

Line term() {

if (*it == '(' && (isdigit(*next(it)) || *next(it) == '-')) {

assert(*it++ == '(');

ld a = number();

assert(*it++ == ',');

ld b = number();

assert(*it++ == ')');

return Line(P(a, b));

}

else {

assert(*it++ == '(');

Line a = point();

if (*it == ')') {

it++;

return a;

}

assert(*it++ == '@');

Line b = point();

assert(*it++ == ')');

return a * b;

}

}

ld number() {

ld sgn = 1;

if (*it == '-') {

it++;

sgn = -1;

}

ll ret = 0;

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

ret = 10LL * ret + (*it - '0');

}

return sgn * ret;

}

};

Q問題〜T問題

hr.icon

Q問題

hr.icon

code: (cpp)

struct Robot {

int y, x;

int dir;

int cnt;

void run(char c, const vector<string>& b) {

int ny = y, nx = x;

switch (c) {

case '<': dir = (dir + 1) % 4; break;

case '>': dir = (dir + 3) % 4; break;

default: cerr << c << endl; assert(false);

}

y = ny;

x = nx;

}

cnt++;

check();

}

void check() {

if (y == gy && x == gx) {

cout << cnt << endl;

exit(EXIT_SUCCESS);

}

}

bool detectsWall(const vector<string>& s) const {

}

bool operator <(const Robot& other) const {

return make_tuple(y, x, dir) < make_tuple(other.y, other.x, other.dir);

}

};

struct cond_t {

cond_t() : neg(false), type('?') {}

cond_t(bool _neg, char _t) : neg(_neg), type(_t) {}

bool call(const Robot& robot, const vector<string>& b) {

switch (type) {

case 'N': return robot.dir == 0;

case 'E': return robot.dir == 3;

case 'S': return robot.dir == 2;

case 'W': return robot.dir == 1;

case 'C': return robot.detectsWall(b);

case 'T': return true;

}

assert(false);

}(type);

return ret ^ neg;

}

bool neg;

char type;

};

struct Parser {

vector<string> b;

string s;

string::const_iterator it;

vector<int> brackets;

vector<int> brackets2;

Robot robot;

Parser() = default;

Parser(vector<string> _b, string _s) : b(_b), s(_s) {

it = s.begin();

int sy = 0, sx = 0;

gx = gy = 0;

rep (i, 0, h) {

rep (j, 0, w) {

sy = i;

sx = j;

}

gy = i;

gx = j;

}

}

}

robot.y = sy;

robot.x = sx;

robot.dir = 0;

robot.cnt = 0;

stack<int> stk, stk2;

brackets.resize(s.size(), -1);

brackets2.resize(s.size(), -1);

rep (i, 0, s.size()) {

stk.push(i);

}

int from = stk.top();

stk.pop();

}

stk2.push(i);

}

int from = stk2.top();

stk2.pop();

}

}

}

void parse() {

program();

}

void program() {

while (it != s.end() && *it != '}' && *it != ']') {

sentence();

}

}

void sentence() {

if (*it == '[') {

if_sentence();

}

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

while_sentence();

}

else {

runner();

}

}

void if_sentence() {

int j = distance(s.cbegin(), it);

assert(*it++ == '[');

cond_t cond = condition();

if (cond.call(robot, b)) program();

assert(*it++ == ']');

}

int depth = 0;

void while_sentence() {

int j = distance(s.cbegin(), it);

assert(*it++ == '{');

cond_t cond = condition();

int i = distance(s.cbegin(), it);

set<Robot> visited;

for (it = s.cbegin() + i; cond.call(robot, b); it = s.cbegin() + i) {

program();

if (visited.count(robot)) {

cout << -1 << endl;

exit(EXIT_SUCCESS);

}

visited.insert(robot);

}

assert(*it++ == '}');

}

void runner() {

robot.run(*it++, b);

}

cond_t condition() {

cond_t cond;

if (*it == '~') {

assert(*it++ == '~');

cond.neg = true;

}

assert(isalpha(*it));

cond.type = *it++;

return cond;

}

};

R問題

hr.icon

和訳すると、

この行列を構文の通り操作します。

例えば、

構文解析自体は再帰降下で良いです。

行列のシフトは、

という行列で表せば良いです。

これで行列のシフトの合成が十分高速に計算できます。

code: (cpp)

using M = vector<vector<ll>>;

struct Parser {

string s;

string::const_iterator it;

ll n;

Parser() = default;

Parser(const string& _s, ll _n) : s(_s), n(_n) {

it = s.cbegin();

}

M parse() {

return expr();

}

M expr() {

M acc = term();

while (it != s.end() && *it != ')') {

M other = term();

acc = plus(acc, other);

}

return acc;

}

M term() {

if (*it == '(') {

assert(*it++ == '(');

M res = expr();

assert(*it++ == ')');

ll num = number();

M ret = iota2();

while (num) {

if (num & 1) {

ret = plus(ret, res);

}

res = plus(res, res);

num >>= 1;

}

return ret;

}

else {

char c = *it++;

M ret = iota2();

ll num = number() - 1;

if (c == 'L') {

int i = num;

}

else if (c == 'R') {

int i = num;

}

else if (c == 'U') {

int j = num;

}

else {

assert(c == 'D');

int j = num;

}

return ret;

}

}

M plus(const M& a, const M& b) {

M ret = a;

rep (i, 0, n) {

rep (j, 0, n) {

int r = v / n;

int c = v % n;

}

}

return ret;

}

M iota2() {

M mat(n, vector(n, 0LL));

rep (i, 0, n * n) {

}

return mat;

}

};

S問題

hr.icon

この問題がすべての基本です。

code: (cpp)

# include <bits/stdc++.h>

using namespace std;

struct Parser {

string s;

string::const_iterator it;

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

int parse() {

return expr();

}

int expr() {

int acc = 0;

int sgn = +1;

while (it != s.end()) {

if (*it == '=') {

it++;

break;

}

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

break;

}

else if (*it == '(' || isdigit(*it)) {

acc += sgn * term();

}

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

sgn = +1;

it++;

}

else {

assert(*it == '-');

sgn = -1;

it++;

}

}

return acc;

}

int term() {

int acc = 1;

int type = 1;

while (it != s.end()) {

if (*it == '+' || *it == '-' || *it == '=' || *it == ')') {

break;

}

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

type = 1;

it++;

}

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

type = 2;

it++;

}

else {

assert(*it == '(' || isdigit(*it));

int v = fact();

if (type == 1) acc *= v;

else acc /= v;

}

}

return acc;

}

int fact() {

if (*it == '(') {

it++;

int ret = expr();

assert(*it == ')');

it++;

return ret;

}

else {

assert(isdigit(*it));

return number();

}

}

int number() {

int ret = 0;

while (isdigit(*it)) {

ret = 10*ret + (*it - '0');

it++;

}

return ret;

}

};

int main() {

int n;

cin >> n;

for (int i = 1; n--; i++) {

string s;

cin >> s;

int ans = Parser(s).parse();

cout << ans << endl;

}

}

T問題

hr.icon

この問題も基本です。

この問題が理解できれば、ほとんどの構文解析問題の構文解析パートは解けるようになります。

code: (cpp)

# include <bits/stdc++.h>

using namespace std;

struct Parser {

string s;

string::const_iterator it;

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

bool ok;

int parse() {

ok = true;

int a = expr();

int b = expr();

return a == b && ok;

}

int expr() {

int acc = 0;

int sgn = +1;

while (it != s.end()) {

if (*it == '=') {

it++;

break;

}

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

break;

}

else if (*it == '(' || isdigit(*it)) {

acc += sgn * term();

}

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

sgn = +1;

it++;

}

else {

assert(*it == '-');

sgn = -1;

it++;

}

}

return acc;

}

int term() {

int acc = 1;

int type = 1;

while (it != s.end()) {

if (*it == '+' || *it == '-' || *it == '=' || *it == ')') {

break;

}

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

type = 1;

it++;

}

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

type = 2;

it++;

}

else {

assert(*it == '(' || isdigit(*it));

int v = fact();

if (type == 1) acc *= v;

else acc /= v;

}

}

return acc;

}

int fact() {

if (*it == '(') {

it++;

int ret = expr();

assert(*it == ')');

it++;

return ret;

}

else {

assert(isdigit(*it));

return number();

}

}

int number() {

int ret = 0;

if (*it == '0') {

if (isdigit(*next(it))) ok = false;

}

while (it != s.end() && isdigit(*it)) {

ret = 10*ret + (*it - '0');

it++;

}

return ret;

}

};

string solve(string s) {

for (int x = '0'; x <= '9'; x++) {

string t = s;

for (char& c : t) if (c == 'X') c = x;

bool ans = Parser(t).parse();

if (ans) {

return string(1, x);

}

}

return "NA";

}

int main() {

string s;

while (cin >> s) {

s.push_back('=');

cout << solve(s) << endl;

}

}

U問題〜V問題

hr.icon

U問題

hr.icon

構文は単純ではありますが、本質考察が難しいです。

制約的にBitDPがしたくなりますが、うまくいきません。

となります

code: (cpp)

# include <bits/stdc++.h>

# define len(v) (ll(std::size(v)))

# define all(v) std::begin(v), std::end(v)

# define rep(i, a, b) for (ll i = a; i < ll(b); i++)

using namespace std;

using ll = long long;

using ld = long double;

using pll = pair<ll, ll>;

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

constexpr ll MOD = ll(1e9) + 7;

constexpr bool stand(int mask, int i) {

return mask & (1 << i);

}

struct Parser {

string s;

string::const_iterator it;

string a;

int ord;

char target;

map<char, int> f;

Parser() = default;

Parser(const string& _s, const string& _a, int _ord, char t) : s(_s), a(_a), ord(_ord), target(t) {

it = s.cbegin();

}

bool parse() {

char c = expr();

return c == target;

}

char expr() {

if (*it == '(') {

assert(*it++ == '(');

char lhs = expr();

char op = *it++;

char rhs = expr();

char c = cmp(lhs, op, rhs);

assert(*it++ == ')');

return c;

}

else {

assert(isalpha(*it));

return *it++;

}

}

inline char cmp(char lhs, char op, char rhs) {

if (lhs == target && rhs == target) {

return target;

}

else if (lhs != target && rhs != target) {

return op == '<' ? lhs : rhs;

}

return op == '<' ? rhs : lhs;

}

else {

return rhs;

}

}

else if (lhs == target && rhs != target) {

if (op == '<') return stand(ord, i) ? rhs : lhs;

else return stand(ord, i) ? lhs : rhs;

}

else if (lhs != target && rhs == target) {

if (op == '<') return stand(ord, i) ? lhs : rhs;

else return stand(ord, i) ? rhs : lhs;

}

else {

assert(false);

}

}

};

void solve(int n, string a, string s, string t, const vector<ll>& fact, const vector<int>& popcount) {

ll ans = 0;

const int a_size = len(a);

rep (i, 0, a_size) {

rep (ord, 0, 1 << (a_size - 1)) {

bool ok = true;

if (ok) {

}

}

}

cout << ans << endl;

}

void Main() {

vector<ll> fact = {1};

rep (i, 1, 17) {

fact.push_back(fact.back() * i);

}

vector<int> popcount(1 << 15);

rep (i, 0, 1 << 15) {

}

while (true) {

int n;

cin >> n;

if (!n) break;

string a, s, t;

cin >> a >> s >> t;

solve(n, a, s, t, fact, popcount);

}

}

V問題

hr.icon

構文解析パートはG問題を参考にしてください。以下、本質考察のみ解説します。

次のような木DPを考えます。

子の順番は自由に変更できます。よって、

また、子の順番が自由に変更できて、かつ左の子を根とすることができるので、葉以外のすべてのノードを根とすることができます。

全方位木DPと同じ発想で高速化することを考えます。遷移は同じで、添字のみを工夫します。

こうしておけば、根を変更したとしても計算結果を使いまわすことができ、十分高速に動作します。

code: (cpp)

struct Node;

using pNode = shared_ptr<Node>;

struct Node {

Node() = default;

Node(ll v, int i) : val(v), op('?'), index(i) {}

Node(char c, int i) : val(numeric_limits<ll>::min()), op(c), index(i) {}

bool isleaf() { return op == '?'; }

vector<pNode> nodes;

ll n_childs;

ll val;

char op;

int index;

};

struct Parser {

string s;

string::const_iterator it;

int id;

Parser() = default;

Parser(const string& _s) : s(_s), id(0) { it = s.cbegin(); }

pNode parse() {

return expr();

}

pNode expr() {

vector<pNode> nodes;

nodes.push_back(term());

char op = '?';

int n_childs = nodes.back()->n_childs + 1;

while (*it == '+' || *it == '-') {

char cur_op = *it++;

if (op == '+') {

if (op != '?') assert(op == cur_op);

}

else {

if (op != '?') assert(op == cur_op);

}

op = cur_op;

nodes.push_back(term());

n_childs += nodes.back()->n_childs + 1;

}

pNode root = make_shared<Node>(op, id++);

root->nodes = nodes;

root->n_childs = n_childs + 1;

return root;

}

pNode term() {

if (*it == '(') {

assert(*it++ == '(');

pNode res = expr();

assert(*it++ == ')');

return res;

}

else {

assert(isdigit(*it));

ll val = number();

pNode node = make_shared<Node>(val, id++);

node->n_childs = 0;

return node;

}

}

ll number() {

ll ret = 0;

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

ret = 10LL*ret + (*it - '0');

}

return ret;

}

};

int main() {

while (true) {

string s;

cin >> s;

if (s == "-1") break;

Parser parser(s);

pNode root = parser.parse();

const int n = parser.id;

vector<vector<int>> graph(n);

vector<Node> nodes(n);

{

queue<pNode> que;

que.push(root);

vector<bool> visited(n, false);

while (not que.empty()) {

pNode now = que.front();

que.pop();

for (pNode to : now->nodes) {

que.push(to);

}

}

}

struct DP {

vector<ll> mins, maxs;

bool visited;

DP() : visited(false) {}

ll min(char op) {

if (mins.size() == 1) {

}

else if (op == '+') {

assert(len(mins) <= 3);

return accumulate(all(mins), 0LL);

}

else {

assert(op == '-');

assert(len(maxs) <= 3);

ll res = numeric_limits<ll>::max();

rep (i, 0, len(mins)) {

}

return res;

}

}

ll max(char op) {

if (maxs.size() == 1) {

}

else if (op == '+') {

assert(len(maxs) <= 3);

return accumulate(all(maxs), 0LL);

}

else {

assert(op == '-');

assert(len(maxs) <= 3);

ll res = numeric_limits<ll>::min();

rep (i, 0, len(maxs)) {

}

return res;

}

}

};

constexpr ll inf = (1LL << 62) - (1LL << 31);

vector<vector<DP>> dp(n);

vector<pll> edges;

rep (i, 0, n) {

}

}

}

DP ret;

return ret;

}

DP acc;

int to = -1;

to++;

if (child == par) continue;

DP dpc = self(self, child, now, to);

acc.mins.push_back(dpc.min(op));

acc.maxs.push_back(dpc.max(op));

}

return acc;

};

ll ans = -inf;

rep (i, 0, n) {

}

cout << ans << endl;

}

}