Welcome to online-judge-template-generator’s documentation!

onlinejudge_template.generator package

Submodules

onlinejudge_template.generator.about module

onlinejudge_template.generator.cplusplus module

the module to generate C++ code

この module は C++ のコードを生成します。

以下の関数を提供します。

次のように利用することが想定されています。

#include ...
...

${cplusplus.declare_constants(data)}
${cplusplus.return_type(data)} solve(${cplusplus.formal_arguments(data)}) {
    ...
}

int main() {
${cplusplus.read_input(data)}
    auto ${cplusplus.return_value(data)} = solve(${cplusplus.actual_arguments(data)});
${cplusplus.write_output(data)}
}

加えて、ランダムケースの生成のために、以下の関数を提供します。

onlinejudge_template.generator.cplusplus.actual_arguments(data: Dict[str, Any]) → str[source]
onlinejudge_template.generator.cplusplus.declare_constants(data: Dict[str, Any], *, nest: int = 0) → str[source]
onlinejudge_template.generator.cplusplus.formal_arguments(data: Dict[str, Any]) → str[source]
onlinejudge_template.generator.cplusplus.generate_input(data: Dict[str, Any], *, nest: int = 1) → str[source]
onlinejudge_template.generator.cplusplus.read_input(data: Dict[str, Any], *, nest: int = 1) → str[source]
onlinejudge_template.generator.cplusplus.return_type(data: Dict[str, Any]) → str[source]
onlinejudge_template.generator.cplusplus.return_value(data: Dict[str, Any]) → str[source]
onlinejudge_template.generator.cplusplus.write_input(data: Dict[str, Any], *, nest: int = 1) → str[source]
onlinejudge_template.generator.cplusplus.write_output(data: Dict[str, Any], *, nest: int = 1) → str[source]

onlinejudge_template.generator.hook module

onlinejudge_template.generator.hook.register_filter_command(command: List[str], *, data: Dict[str, Any]) → None[source]

onlinejudge_template.generator.python module

the module to generate Python code

この module は Python のコードを生成します。

以下の関数を提供します。

加えて、ランダムケースの生成のために、以下の関数を提供します。

onlinejudge_template.generator.python.actual_arguments(data: Dict[str, Any]) → str[source]
onlinejudge_template.generator.python.declare_constants(data: Dict[str, Any], *, nest: int = 0) → str[source]
onlinejudge_template.generator.python.formal_arguments(data: Dict[str, Any], *, typed: bool = True) → str[source]
onlinejudge_template.generator.python.generate_input(data: Dict[str, Any], *, nest: int = 1) → str[source]
onlinejudge_template.generator.python.read_input(data: Dict[str, Any], *, nest: int = 1) → str[source]
onlinejudge_template.generator.python.return_type(data: Dict[str, Any]) → str[source]
onlinejudge_template.generator.python.return_value(data: Dict[str, Any]) → str[source]
onlinejudge_template.generator.python.write_input(data: Dict[str, Any], *, nest: int = 1) → str[source]
onlinejudge_template.generator.python.write_output(data: Dict[str, Any], *, nest: int = 1) → str[source]

onlinejudge_template.generator.topcoder module

onlinejudge_template.generator.topcoder.class_name(data: Dict[str, Any]) → str[source]
onlinejudge_template.generator.topcoder.is_topcoder(data: Dict[str, Any]) → bool[source]
onlinejudge_template.generator.topcoder.method_name(data: Dict[str, Any]) → str[source]

onlinejudge_random package

onlinejudge_random.randint(a: int, b: int, *, type: str = 'auto', r: random.Random = <module 'random' from '/home/docs/checkouts/readthedocs.org/user_builds/online-judge-template-generator/envs/latest/lib/python3.7/random.py'>) → int[source]

randomly choose an integer

onlinejudge_random.rooted_tree_parents(nodes: int, *, base: int = 0, type: str = 'auto', r: random.Random = <module 'random' from '/home/docs/checkouts/readthedocs.org/user_builds/online-judge-template-generator/envs/latest/lib/python3.7/random.py'>) → List[int][source]

randomly choose a rooted tree

onlinejudge_random.sequence(size: int, kind: int, *, base: int = 0, type: str = 'auto', r: random.Random = <module 'random' from '/home/docs/checkouts/readthedocs.org/user_builds/online-judge-template-generator/envs/latest/lib/python3.7/random.py'>) → List[int][source]

randomly choose a sequence

onlinejudge_random.tree_edges(nodes: int, *, base: int = 0, type: str = 'auto', r: random.Random = <module 'random' from '/home/docs/checkouts/readthedocs.org/user_builds/online-judge-template-generator/envs/latest/lib/python3.7/random.py'>) → List[Tuple[int, int]][source]

randomly choose a unrooted tree

How it works

Summary

  1. download and recognize HTML with requests + beautifulsoup4
  2. parse the <pre> format in old style Lex + Yacc (ply)
  3. generate codes with a template engine (Mako)

An example (Japanese) / 具体例 (日本語)

たとえば Library Checker の問題 [Static RQM](https://judge.yosupo.jp/problem/staticrmq) について考えてみましょう。 この問題の入力フォーマットは次のようになっています。

n m
a₀ a₁ … aₙ₋₁
l₁ r₁
⋮
lₘ rₘ

これをまず以下のようなトークン列に分解します。 愚直に貪欲をするだけで、やばい規則もないのでほぼ O(n) です。正規表現で便利に書ける既存のツールがあるのでこれを利用しています。

[
    "ident(n)", "ident(m)", "newline()",
    "ident(a)", "subscript()", "number(0)", "ident(a)", "subscript()", "number(1)", "dots()", "ident(a)", "subscript()", "ident(n)", "binop(-)", "number(1)", "newline()",
    "ident(l)", "subscript()", "number(1)", "ident(r)", "subscript()", "number(1)", "newline()",
    "vdots(1)", "newline()",
    "ident(l)", "subscript()", "ident(m)", "ident(r)", "subscript()", "ident(m)", "newline()"
]

このトークン列を解析して次のような木へ変形します。 まず文脈自由文法で解析できる範囲を処理して木を作った後に、文脈依存ぽい部分を ad-hoc に処理してより整理された木に組み換えています。 文脈自由部分は O(n^3) の愚直な区間 DP (CYK法) でもよいですが、規則を列挙すれば残りをいい感じにやってくれる既存のツール (Yacc) に任せてほぼ線形 (LALR法) で実装されています。

この木を変換してソースコードにします。 木の畳み込みとか木 DP とか言われる O(n) か O(n²) ぐらいの愚直をします。 何をやっても変換はできますが、(1.) まずフォーマット木を C++ の構文木に写し、(2.) それを最適化し、(3.) これを行の列に直列化し、(4.) インデントを整えて出力する、という 4 段階に分けると実装が楽かつ出力がきれいです。

int n, m;
scanf("%d%d", &n, &m);
std::vector<int> a(n);
for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
}
std::vector<int> l(m), r(m);
for (int j = 0; j < m; ++j) {
    scanf("%d%d", &l[j], &r[j]);
}

この一連の作業をよろしくやってくれるのがこのツールです。

Indices and tables