AtCoder ABC155における言語差問題について

おれは今、AtCoderには参加せず、Codeforcesに参加し続けている。 レートも

Codeforcesで青色に昇格しました!!!AtCoderとの違いや活用法を紹介します。

に書いたように、 青までは上がり、その後はあまり調子が良くなくてついに水色に落ちてしまったものの、 実力的には日々精進して、コンスタントに伸び続けている感覚がある。 紫に上がったらAtCoderにまた戻りたいと考えていて、それはそう遠い未来ではないと信じている。 その頃にはRustのバージョンが上がっていてほしいものだ。

競技プログラミングではモチベーションの維持が難しくなることがあって、 おれが過去にAtCoderに対して「具合が悪くなった」ことがあったのは今まで書いてきたとおりだが、 今のおれは日々頭がへとへとになるまでCFの過去問を精進し、 頻繁に開催されるコンテストに参加することを楽しみに出来ている。 おれはこんなところで止まる人間ではないはずだという謎の自信があるからだ。

参加はしないものの、一応、AtCoderの問題はコンテスト後に覗いている。 最近はAtCoderも良い典型問題を出すようになったし、勉強の教材としては良いものだと評価出来る。 ただ、開催頻度の高いCF div2との両立は疲れるというのと、 やっぱりたまにふざけた問題があってうんざりすることがあるから、 参加に気が滅入るということで、今は意図的に避けている。 おれはそういう問題を「だから何なの問題」と呼んでいる。 ただ最近は、ABCは王道の問題を揃えているなという印象だった。

今回も、問題をパラパラっと見て、 ふつうに良い問題だなぁと思った が、Fを考えてもピンと来ないので、 ツイッターで検索をかけてみると、解法のアイデアをツイートしている人がいて なるほどなぁと見ていると、隣に不穏なツイートを発見した。

その後、このkichiくんという子はついにAtCoderのアカウントを削除してしまったようだ。 中2の時に競プロに出会い、それから2年間精進してきたが、最近はレートが伸びずにモチベーションを保つのが大変だった、 今回のコンテストをきっかけにして引退しようと思う、という旨が彼のブログで語られている。

競技プログラミングから身を引くことにしました

解かずに論じるのはあまりにもエアだから、とりあえずやってみたが、 Rustで書いたこのコードは126msでACした。

fn solve() {
    let out = stdout();
    let mut out = BufWriter::new(out.lock());
    input!{
        n: usize,
        s:[String;n]
    }
    let mut s = s;
    s.sort();
    let rls = run_length_compression(&s);
    let m = rls.len();
    let mut maxfreq = 0;
    for i in 0..m {
        let n = rls[i].1;
        chmax!(maxfreq,n);
    }
    for i in 0..m {
        let st = rls[i].0.clone();
        let n = rls[i].1;
        if n == maxfreq {
            writeln!(out,"{}",st);
        }
    }
}

しかしこれがC#でやると、文字列のソートが非常に遅い実装になってることが原因で、 コンテスト中には、TLEの山を築いたようだ。

問題の難易度はというと、はっきりいって競技プログラミングというまでもないレベルに 簡単なあまりにバカバカしい「ただやるだけ」の問題であり、当然このkichiくんもそう思ったであろう。 こんな問題でメンタルブレイクし、引退に追い込まれてしまったkichiくんがかわいそうになる。 特定の言語を狙い撃ちしたなどと言ったのは怒りのぶつけどころがなかったからだろうと思う。 冷静になってみれば、そんなわけがないことはわかるはずだ。

実際にAtCoder社としては、特定の言語を狙い撃ちしたということは一切なく、 ただC#でテストをしたわけではないからこういうことが起こってしまったというわけだ。 そして、C#でやるにしても、ACさせる方法はあったようである。

この「言語によっては通らない場合がある問題」は競プロが複数の言語を許していることに根ざしている本質的な問題である。 ある言語ではACが出来ることが保証されていることをAC保証というが、 AtCoderでは、C++とJavaくらいでしかAC保証をしていない。 つまり、比較的速い言語の部類であるRustであっても、 想定解法を実装したとしてTLEせずに解けるかどうかは保証されていないのだ。 想定解法をストレートに実装してもTLEするというのは、Pythonではよくあることで、 だからPythonユーザはnumpyを使って高速化するとか、ちょっとした飛躍を必要とする場合がある。

では、Pythonなど遅い言語を基準にして問題を作成したらどうかと思うかも知れないが、 そうすると今度は、C++など速いコードでは多少計算量の大きいアルゴリズムを実装したとしても 間に合ってしまうということが起こる。 だから結局、速い言語に合わせるしかなくなるのだ。

この問題に対してプレイヤーはどう考えればよいのか。 おれはRustをずっと使い続けているが、 この言語は競プロの使い捨てコードを書くにはあまりに 保守的で、アルゴリズムを書きづらく感じることがある。 だから、C++でやればよかったなぁと思うことはままある。 しかし、競プロをやる上でもRustの方がC++より良いといえる部分もあり悩ましいのだ。 エコシステムでも、 tanakhさんが作ったinputマクロや、hatooさんが作った cargo-snippetなど、優れたものが存在する。

では、RustでもC++でもなかったら何を使うかというと、 自分ならばPythonを使う。 Pythonは「動く疑似コード」と呼ばれるほどコードがシンプルで、 速度が足りずに解けない場合があることを差し引いても 選択肢として十分にアリだと思う。 おれは、これから競プロを始めるのであればPythonでやることをオススメする。 勉強をしていく上でも、コードをシンプルに書けるというのは効率が良いのだ。

今回のようなことが起こるなら、 今に至っては非現実的ではあるけど、 競プロではPythonしか使えないということにしても良いのではないかと思うこともある。 そうすれば、言語差は存在しなくなるし、 アルゴリズムだけが試されることになってよりピュアになるからだ。 むしろ、そうならず、こんなに多様な言語を認める方向に 進化してしまう方が不自然で、なぜそうなったのかを不思議に思う。 何か歴史的な経緯があるんだろうか。


このエントリーをはてなブックマークに追加

See also