A simple template generator for competitive programming
Project description
Online Judge Template Generator
まだ不安定版なので嘘が出力されてても怒らないでね。 そのうち実装することのリストは TODO にあります
これはなに
競技プログラミングテンプレートを作ってくれるやつです。 kyuridenamida/atcoder-tools を参考に、その本質部分だけを抜き出して再実装しました。
主目的は以下のふたつです:
- 不適切な入出力方法を用いたことによる TLE を回避すること。たとえば「Codeforces で
std::endl
を使って TLE する」みたいなのをなくしたい - ランダムケースを生成してのテストを気軽に行えるようにすること。たとえば、サンプル AC して提出してみたら謎の WA が出たとき「これランダムケース生成して愚直解と比較すれば原因分かるだろうけど、面倒なんだよな」ってなりがちですが、この面倒を半減させ高速にデバッグできるようにしたい
How to Install
$ pip3 install git+https://github.com/kmyk/online-judge-template-generator.git@master
(後でやる: PyPI への登録)
Usage
oj-template
コマンドは、指定された問題に対し、入出力パートを自動生成します。
入出力解析は AtCoder と yukicoder と Library Checker にのみ対応していますが、それら以外でも一応は動きます。
$ oj-template [-t template] URL
oj-contest
コマンドは、指定された問題やコンテストに対し、テンプレート生成やサンプルのダウンロードを一括で行います。
oj が動くやつなら何に対してでも動きます。
$ oj-contest URL
Settings
oj-template
のためのテンプレートは ~/.config/online-judge-tools/template/
の下に ~/.config/online-judge-tools/template/customized.py
のように作って oj-template -t customized.py https://...
のように指定する。
テンプレート記法は Mako のものを使う。
fastio.cpp とか customize_sample.cpp とかを見てそれっぽく書けば動く。
oj-contest
の設定は ~/.config/online-judge-tools/oj2.config.toml
に次のように設定する。
problem_directory = "~/{service_domain}/{contest_id}/{problem_id}"
[templates]
"main.cpp" = "template.cpp"
"generate.py" = "generate.py"
(まだ不安定版であり、設定等の後方互換性は保証されません)
Example
$ oj-contest https://atcoder.jp/contests/abc158
...
$ tree ~/atcoder.jp
/home/ubuntu/atcoder.jp
└── abc158
├── abc158_a
│ ├── generate.py
│ ├── main.cpp
│ └── test
│ ├── sample-1.in
│ ├── sample-1.in
│ ├── sample-1.out
│ ├── sample-2.in
│ ├── sample-2.out
│ ├── sample-3.in
│ └── sample-3.out
├── ...
├── ...
├── ...
├── ...
└── abc158_f
├── generate.py
├── main.cpp
└── test
├── sample-1.in
├── sample-1.out
├── sample-2.in
├── sample-2.out
├── sample-3.in
├── sample-3.out
├── sample-4.in
└── sample-4.out
13 directories, 50 files
$ cat ~/atcoder.jp/abc158/abc158_f/main.cpp
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) ::std::begin(x), ::std::end(x)
using namespace std;
auto solve(int N, const vector<int> & X, const vector<int> & D) {
// TODO: edit here
}
// generated by online-judge-template-generator
int main() {
int N;
scanf("%d", &N);
vector<int > X(N), D(N);
REP (i, N) {
scanf("%d%d", &X[i], &D[i]);
}
auto ans = solve(N, X, D);
printf("%d\n", ans); // TODO: edit here
return 0;
}
$ cat ~/atcoder.jp/abc158/abc158_f/generate.py
#!/usr/bin/env python3
import random
import onlinejudge_random as random_oj
def main():
N = random.randint(1, 10 ** 9) # TODO: edit here
X = [None for _ in range(N)]
D = [None for _ in range(N)]
for i in range(N):
X[i] = random.randint(1, 10 ** 9) # TODO: edit here
D[i] = random.randint(1, 10 ** 9) # TODO: edit here
print(N)
for i in range(N):
print(X[i], D[i])
if __name__ == "__main__":
main()
Architecture
- download and recognize HTML with requests + beautifulsoup4
- parse the
<pre>
format in old style Lex + Yacc (ply) - generate codes with a template engine (Mako)
How it works
たとえば Library Checker の問題 Static RQM について考えてみましょう。 この問題の入力フォーマットは次のようになっています。
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法) で実装されています。
[
{"type": "var", "name": "n"},
{"type": "var", "name": "m"},
{"type": "newline"},
{"type": "loop", "counter": "i", "size": "n", "body": [
{"type": "var", "name": "a", "subscript": "i"}
]},
{"type": "newline"},
{"type": "loop", "counter": "j", "size": "m", "body": [
{"type": "var", "name": "l", "subscript": "j + 1"},
{"type": "var", "name": "r", "subscript": "j + 1"},
{"type": "newline"}
]}
]
この木を変換してソースコードにします。 木の畳み込みとか木 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]);
}
この一連の作業をよろしくやってくれるのがこのツールです。
License
MIT License
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distributions
Built Distribution
Hashes for online_judge_template_generator-2.4.2-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3df214ff25060057af48797c0cfb86956d0b174b96e41bc9b0f41c3372aa2daa |
|
MD5 | ed4c20711950a81f3d6de40cafa4c2d3 |
|
BLAKE2b-256 | d6ed04f8e30e6e496e1aa5d10e3f012bcef1bffd572e0bd401934c4c544f3a75 |