【競技プログラミング】Pythonでも入力をエレガントに処理する

Rustで競プロはだるい

おれが競技プログラミングを最後にやったのはもう３年前のことで、もうずっとコンテストに参加していないのだが、そのうちまたやりたいなぁとは思っている。

でも、Rustではもうやりたくない。おれが競プロをやめた理由は色々あるが、そのうち些末でないものの一つとして「Rustで競プロをしたくないから」というのがある。

Rustは、実システムを開発する上では非常に強力な言語だ。しかし、Rustのある種の堅さが競プロのコードを書く上ではかなり邪魔になる。理由を一言でいうとそういうことだ。

具体的にいうと、Rustで競プロをすると、

整数型をキャストしまくることになってだるい
整数型が１つでないため、ライブラリのデザインが悩ましくなってだるい
クロージャが再帰出来ないため、メモ化再帰などがかなりだるい
文字列処理がだるい

など、本質的ではないコーディングをたくさん強いられることになる。おれは競プロをするためにだるいことはしたくない。

Pythonを使う上での２つの問題

もう一度競プロをする場合に有力な言語は何かと考えた結果、 Pythonということになった。 Pythonは「動く疑似コード」と呼ばれるように、アルゴリズムを簡潔に書くことに優れていて、競プロのために作られた言語といっても過言ではない。

しかし、問題が２つある。

１つは、速度である。

Pythonの実行速度は死ぬほど遅く、これは競プロにおいて２つの点で不利になる。１つは、RustやC++では通るようなコードが通らない。もう１つは、Pythonを書く上でも少し凝った書き方をしないとまともな速度が出ないことがある。この場合、ふつうのコードを書くことすら許されなくなり、これでは何のためにPythonを使ってるのかわからなくなる。

Pythonの文法を保ったまま性能の高い処理系を作るという試みは死ぬほど行われていて、そのうち有名かつAtCoderでもサポートされているものはPyPyである。しかしPyPyよりも速いものが出現した。それがCodonである。

Codon is a high-performance Python compiler that compiles Python code to native machine code without any runtime overhead. Typical speedups over Python are on the order of 10-100x or more, on a single thread. Codon’s performance is typically on par with (and sometimes better than) that of C/C++.

こうして、性能問題については解決された。

残るもう１つの問題は、競プロ的な標準入力処理のだるさである。

Rustでは、tanakhがproconioという、マクロによって標準入力を処理する手法を開発したためこれが広く使われており、もはやRustを使う理由の１つにすらなっているのではないかと思うほど素晴らしいものだが、おれが調べた範囲でいえば、Pythonではこのような手法は開発されていない。少なくとも、同様にマクロで実装することは出来ないように思えた。

変換器を作る

このままでは競プロに戻ることが出来ない。

そこで、proconio的な形式で書かれた宣言から Pythonコードを生成するような変換器を実装することにした。

例えば、例として以下のような宣言を変換器に通すと、

1
2
n: int
a: [int; n]

構文解析されて、

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
Root(
    [
        Line(
            [
                Definition(
                    Var(
                        "n",
                    ),
                    UnitType(
                        Int,
                    ),
                ),
            ],
        ),
        Line(
            [
                Definition(
                    Var(
                        "a",
                    ),
                    TupleLike(
                        Array(
                            Array(
                                Int,
                                Var(
                                    Var(
                                        "n",
                                    ),
                                ),
                            ),
                        ),
                    ),
                ),
            ],
        ),
    ],
)

入力処理のためのコードが生成される。

1
2
3
4
xs = input().split()
n = int(xs[0:(0 + 1)][0])
xs = input().split()
a = [int(x) for x in xs[0:(0 + n)]]

リリースについて

このソフトウェアは現在、デモがぎりぎり出来る程度にしか開発していないが、基本的な枠組みとしては作り込んであり、より一般的な形式もサポート出来るようになる予定である。

競プロでは、1-indexでグラフの連結が表現されることがあり、これが結構うざいため、 int0という型を用意し、これを指定することで0-indexに変換してくれる機能も組み込んである。

今後のリリースとしては、このソフトウェアの需要を見ながら決めていきたいと思う。例えば、このソフトウェアはよく練って開発をしてはいるものの、実装としては特殊なことは何一つしていないため、貢献したい人がいないならばコードは公開する必要がないと思っている。貢献とはたとえば、Python以外の言語用にコードを吐けるようにしたいとかだ。

そのため、まずはAPIサーバかウェブアプリとしてのリリースを考えていて、そこで様子を見ていこうと思っている。コードを公開しないリリースとしては、dockerイメージとしての公開もあるだろう。他には、vscodeやneovimのプラグインを実装するというアイデアもある。

もし、何かコメントがあるならばメールやTwitterなどで連絡してほしい。

追記：ウェブアプリのリリース

使ってみてほしい。

https://akiradeveloper.github.io/procon-input/

バグ報告や機能要望は、サポート用リポジトリを作ったのでそちらからお願いします。

仕様については例をみればわかると思うので、後日、サポート用リポジトリにドキュメントを書くつもりです。