はじめに

hossie - AtCoder

2023/04/01 に AtCoder 入水しました (参加者の上位 10% ほどにあたる水色レートに到達)。参加から一年ほどでした。

本記事は色変に関する、まとまりのない長文ポエムです。

入緑の色変記事

スペック

開発環境
- Microsoft Surface Laptop 2 + Windows 11
  - 外付けディスプレイ、外付けキーボード、マウスは使っていません
- Visual Studio Code + Rust + cargo-compete
中の人
- 44歳、子育て世代
- プログラミング歴35年ほど
  - Basic, C++, Ruby を 10年以上書いています
  - Rust は未経験から AtCoder 参加
- 東大の情報系学科に昔在籍していました
  - 確かこの頃 DP を書いたことがあります

若い方が多く参加している競技プログラミング ¹ に、昔取った杵柄で参加しようとしてみた形です。そして甘くない世界と言うことを知りました。

参加のきっかけ

最初のきっかけは 2020 年に購入した Rust 本です。新しいプログラミング言語を覚えようかと眺めていたところ、「Rust を覚えるために競技プログラミングで使ってみるのもアリですよ」のようなことが書かれていました ²。でも軽く読んだ後、Rust をインストールすることもなく積んでいました。

その 1年半後に、会社の中でも競技プログラミングの話を聞くようになりました。 2か所でアンテナに引っ掛かりましたから、これはやってみようかなと。

子供に「週に 1回パソコンの日があるからよろしく」が通じるようになってきたこともあり、週末参加をはじめてみました。

結果

体感的な変化

入緑から入水までの体感的な変化です。

変わったこと
- Rust が人気の理由が分かってきた
- 早解き力、間違えた時の対応力が付いたつもり
- F 問題以降の解説文が、以前より読めるようになってきた
- UnionFind (Disjoint Set) や Fenwick Tree (BIT) が自然なものに見えてきた
変わっていないこと
- 「時間をかければ解ける問題」の種類はさっぱり増えていない

Rated 参加での AC 取得時間

ABC Rated 40 回参加での AC 取得時間をグラフで振り返ってみます。 1年間の横軸が ABC251 などの開催回、縦軸が解いた時間です。誤答ペナルティーは含めていません。

最初のころは ABC 3問正解までで時間を多く使って、DE のどちらか易しい方が間に合えばラッキーという感じでした。後半になると早解きに慣れてきています。

また、D 問題が以前より安定し、制限時間 100分で解ききれるようになってきました。³

しかし、全然水色に実力が届いているとは思っていません。緑の延長という感じです。

過去問挑戦数

AtCoder Problems より:

493 問。うち ABC は 247 と半分弱。 @e869120 さんの問題集を多く解いていました。

問題を解いた数の折れ線グラフ。今年に入ってペースを上げました。易しい問題も早解きにはつながっていると思います。

やったこと

やったことと、AtCoder レート向上に役立ったかかどうかをあわせて書きます。

◎ Rust とライブラリーを学ぶ

このあたりを読み、練習コードを書きました。 C++ など他言語の経験もあり、 3か月くらいで競技プログラミング本番中に使う範囲での Rust の文法 ⁴、ライブラリーの検索方法 ⁵ が分かってきました。

このあたりで緑色になりました。しかし同時に、Rust 力を付けても水色に進むのは難しいと感じ始めました。

◎ cargo-compete コマンドラインでテスト実行とコード送信する

最初は「AtCoderコンテストにRustで参加するためのガイドブック」の通り進めていました。でもこの手順通りですと、テストケースのコピペに毎回時間をかけることになります。早解きなのに毎回単純作業があるのは勿体ないと思っていました。

きっと Rust でもうまい方法があるはず、と思って探したところ、 cargo-generate が見つかりました。

21:00 になるとすぐ、次のコマンドを実行します。すべてのテストケースをダウンロードし、すべての問題ページをブラウザで開き、VS Code でフォルダーを開きます。

> cargo compete new abc296
> cd abc296
> cargo compete open
> code .

問題を解いたら単体テストして、良ければサーバーに送信。

> cargo compete test a
> cargo compete submit a

A 問題だとうまくいくと 3分くらいで終わります。早解きにはツールが大事。重宝しています。

△ アルゴリズムの記事と本を読む

アルゴリズムの説明を読みました。知らないアルゴリズムが多いですし、知っているつもりの DP でも区間を扱うとか派生形を含めるとやっぱり知らない、とか。読んでいて楽しいです。

読むだけでも楽しいですけれど、読むだけでは本番中に実装しきれるようにはなりません。半年ほどレートが横ばいでした。

○ 過去問と演習問題を解く

競技プログラミングの鉄則の演習問題を Rust で解き終えた感想 - Qiita

力を付けるのに必要だと分かっています。でも私の場合、知らない問題に挑戦するにはとても重い腰を上げることに。本などでおすすめ問題がまとまっていると、この重い腰が少しだけ軽くなります。

Twitter でたくさん過去問に挑戦している方を見ると、すごいと思います。

○ コンテスト直後の感想戦

コンテスト後に、解ききれなかった問題の解説を見ることや、Twitter で他の方がどんな感じで進めていたのかを見ていると、勉強になります。

コンテスト中に解けた問題: もっと綺麗に解く方法があるかも
コンテスト中に解けなかった問題: 問題まではコンテスト中見ていたので、解説だけに集中できる

単純に色が上のレートの方のコメントを見ても参考になります。こんな風に解き方を思いつくのか、と。

そこで、私もコンテスト後は Twitter で感想をつぶやくようにしています。

そういえば年齢が半分以下の頃に学校で受けていたテストも、テストの点数はわりとどうでも良くて、それよりも間違え方を確認してどう次回につなげるかの方が大事なのでした。コンテスト直後に結果と解説が見られるのは嬉しいことだと思います。 ⁶

△ レートが下がりそうでも気にせず Rated 参加する

以前は、疲れているときなど、時間は取れるけれどレートが下がりそうなら Unrated 参加、としていました。レートに影響しないと気軽に参加できます。

でも、Rated も Unrated も同じ 2時間くらい使うのに、経験値は Rated の方が増えるわけで。ちょっとレートが下がるくらいなら経験値でお釣りがもらえるくらいだと思います。

Unrated 参加を続けていると、Rated 参加するのに不安が出てきて、もっと参加しにくくなりました。それもあまり良くないです。

○ 検索しやすいソースコードを書く

bit 全探索、幅優先探索など、使って問題を解いたことはありますけれど、実装ミスしやすいからあまり 1から書きたくない、というものもあります。

こういうときは、過去に問題を解いたソースコードを検索してコピペしています。たとえば、

bit 全探索する: 1 << で検索して、周辺の実装をコピペ
幅優先探索する: dfs( で検索して、関数をまるごとコピペ
グラフを組み立てる: let graph で検索
Fenwick Tree (BIT) を使う: Fenwick や Binary で検索

検索して見つかるように、変数名・関数名・コメントを付けておくと良い感じです。

hossy3/atcoder-solutions: AtCoder solutions (mainly ABC A-E) by rust

過去のソースコードを置いています。完全に自分用です。もし他の PC で競技プログラミングに参加したくなったら、こちらを持ってくるつもりです。

× 競プロネタの記事を Qiita に書く

競プロネタの記事、もしくは競プロにまつわるネタ記事を Qiita に書きました。

記事を書くのは、レートを上げるためにはコストパフォーマンスが低いです。過去問を解く方をおすすめします。

でも記事を書くのは楽しいのです。

これからやりたいこと

ライブラリー・コードスニペット整備

「検索しやすいソースコードを書く」の通り、過去に解いた問題については探せます。とは言え 500問ほど溜まってくると、無理が出始めている感じもしています。

検索に時間がかかる
ソースコードが検索で見つかっても、以前に解いた問題を忘れていて使い方が分からない
2次元の行列計算など、過去問に使う一部機能しか実装していなくて、使いまわせないことがある
- 全部揃っている外部ライブラリーなら使いまわせるけれど、大げさな感じ

良く使うものはスニペットですぐ呼び出せるようにするのも、と思い始めています。

ARC 参加

AtCoder に参加し始めた茶色の頃に、ARC (Regular) に挑んで 1問も答えられずに凹んだことがありました。ARC は怖いところだと思い、その後ずっと手を付けていません。 ABC (Beginner) 専門で取り組んでいました。

水色になりましたし、そろそろ再挑戦しても良いかなと。見慣れた緑色に戻ったらそのときはそのときで。

しばらく見送るつもりのこと

バーチャルコンテスト参加
- 平日参加は時間を取るのが大変です。バーチャルコンテストなしでは、これ以上の色変は難しい感じもしますけれども。
AHC (Heuristic) に参加
- こちらも、あまり手を広げすぎても、と
他のプログラミング言語で挑戦する
- Zig, Nim, Codon などは実行速度が速く、競技プログラミングすると楽しいかもと思っています

最後に

参加して良かったです。プログラミング言語を一つ覚えて、ある程度ロジックを書けるようになりました。これからもよろしくお願いします。

とくに Twitter で一緒の方は、上達をお祝いしながら続けられれば良いな、と。

競プロer大宴会2023春参加者色々まとめ - Qiita を見ると、イベントに参加した強い方の平均年齢は 26歳ほどだとか。 ↩
この Rust 本を書いている方の一人 kenkoooo さんが、AtCoder Problems の作者ということをあとから知りました。すごい。。 ↩
ABC288-D が、青 diff で D にしては難しすぎると話題になっていました。この回たまたま不参加でした。参加していたら途切れていたと思います。 ↩
所有権などの競技プログラミング本番中に使わない文法については、 1年経ってもヒヨコレベルのままです。 ↩
分かったのは検索方法までです。いまだに A 問題で使う文字列処理をライブラリー検索して書いています。 ↩
解説を見ても実装のバグが取れない、ということもあります。そのときは無理せず、数か月後に Dropbox でテストケースが公開された後に再挑戦が良いです。 ↩

40代で Rust を触り始めて 1年で AtCoder に入水できた件