online-judge-template-generator

A simple template generator for competitive programming


License
MIT
Install
pip install online-judge-template-generator==4.8.1

Documentation

Online Judge Template Generator

test PyPI LICENSE

ใพใ ไธๅฎ‰ๅฎš็‰ˆใชใฎใงๅ˜˜ใŒๅ‡บๅŠ›ใ•ใ‚Œใฆใฆใ‚‚ๆ€’ใ‚‰ใชใ„ใงใญใ€‚ ใใฎใ†ใกๅฎŸ่ฃ…ใ™ใ‚‹ใ“ใจใฎใƒชใ‚นใƒˆใฏ TODO ใซใ‚ใ‚Šใพใ™

ใ“ใ‚Œใฏใชใซ

็ซถๆŠ€ใƒ—ใƒญใ‚ฐใƒฉใƒŸใƒณใ‚ฐใƒ†ใƒณใƒ—ใƒฌใƒผใƒˆใ‚’ไฝœใฃใฆใใ‚Œใ‚‹ใ‚„ใคใงใ™ใ€‚ kyuridenamida/atcoder-tools ใ‚’ๅ‚่€ƒใซใ€ใใฎๆœฌ่ณช้ƒจๅˆ†ใ ใ‘ใ‚’ๆŠœใๅ‡บใ—ใฆๅ†ๅฎŸ่ฃ…ใ—ใพใ—ใŸใ€‚

ไธป็›ฎ็š„ใฏไปฅไธ‹ใฎใตใŸใคใงใ™:

  • ไธ้ฉๅˆ‡ใชๅ…ฅๅ‡บๅŠ›ๆ–นๆณ•ใ‚’็”จใ„ใŸใ“ใจใซใ‚ˆใ‚‹ TLE ใ‚’ๅ›ž้ฟใ™ใ‚‹ใ“ใจใ€‚ใŸใจใˆใฐใ€ŒCodeforces ใง std::endl ใ‚’ไฝฟใฃใฆ TLE ใ™ใ‚‹ใ€ใฟใŸใ„ใชใฎใ‚’ใชใใ—ใŸใ„
  • ใƒฉใƒณใƒ€ใƒ ใ‚ฑใƒผใ‚นใ‚’็”Ÿๆˆใ—ใฆใฎใƒ†ใ‚นใƒˆใ‚’ๆฐ—่ปฝใซ่กŒใˆใ‚‹ใ‚ˆใ†ใซใ™ใ‚‹ใ“ใจใ€‚ใŸใจใˆใฐใ€ใ‚ตใƒณใƒ—ใƒซ AC ใ—ใฆๆๅ‡บใ—ใฆใฟใŸใ‚‰่ฌŽใฎ WA ใŒๅ‡บใŸใจใใ€Œใ“ใ‚Œใƒฉใƒณใƒ€ใƒ ใ‚ฑใƒผใ‚น็”Ÿๆˆใ—ใฆๆ„š็›ด่งฃใจๆฏ”่ผƒใ™ใ‚ŒใฐๅŽŸๅ› ๅˆ†ใ‹ใ‚‹ใ ใ‚ใ†ใ‘ใฉใ€้ขๅ€’ใชใ‚“ใ ใ‚ˆใชใ€ใฃใฆใชใ‚ŠใŒใกใงใ™ใŒใ€ใ“ใฎ้ขๅ€’ใ‚’ๅŠๆธ›ใ•ใ›้ซ˜้€Ÿใซใƒ‡ใƒใƒƒใ‚ฐใงใใ‚‹ใ‚ˆใ†ใซใ—ใŸใ„

How to Install

$ pip3 install online-judge-template-generator

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

  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)

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