算数の教養がほとんどないプログラマが1年間AtCoderをやった結果の振り返り

こんばんみんみん。
バーチャル幼女プログラマーという肩書でインターネットをやっているきりみんちゃんというものです。

去年の7月に競技プログラミングのAtCoderを始めてだいたい1年くらい経ったので、勉強したこととかを振り返りたいと思います。

で、誰？

YouTubeでAtCoderの過去問を解く配信をしたり、Twitterで無限にAtCoderについてつぶやいたりしているVTuberです。
普段の仕事での専門分野はAndroidアプリ開発です。

半年くらい前にAtCoderを普通の社会人エンジニアに布教するエントリを書きました。

また、技術書典で「AtCoderの歩き方 -数学が得意じゃないエンジニアにこそ競技プログラミングを布教したい！-」という本を出したりもしました。

AtCoderの歩き方 -数学が得意じゃないエンジニアにこそ競技プログラミングを布教したい！- - - BOOTH

現在のAtCoderコミュニティの中心層は理系の学生やもともと数学がかなり好きなタイプの人たちです。
一方きりみんちゃんはプログラマでありながら数学にコンプレックスがあり、それどころか小学2年までしか義務教育を受けていないため、中学、高校レベルの基礎的な数学の教養が全くありませんでした。

そしてAtCoderが自分のように数学やアルゴリズムなどに苦手意識を持ってるエンジニアが数学やアルゴリズムを学び直すのにいい題材なんじゃないかなと感じ、問題に取り組むとともに布教活動をしたりしてきました。

そんな自分がAtCoderに真面目に取り組んでどうなったかというのを書いていきたいと思います。

勉強したこと

過去問解き
おそらく一番オーソドックスなAtCoderの勉強です。
界隈では「精進」と呼ばれたりします。
6/22現在、過去問を453問解いています。問題は簡単なものからむずかしいものまで色々ですが、基本的にはABCコンテストの050以降のC問題までを埋めるのを目標にやっていました。
この目標はいくつかの高難易度回を除きほぼ達成しています。

ABCにちょうどいい問題がなくなってきてからはAtCoderProblemsのRecommendationで他のコンテストの自分にあった難易度の問題を選んだりしています。

典型アルゴリズムの学習
競技プログラミングにはいわゆる典型と呼ばれる問題があります。
AtCoderは言語のすべての機能を自由に使うことが出来るほか、コンテスト中にググったりするのも自由なので、ソートアルゴリズムの実装などほとんどの言語に関数が組み込まれているようなアルゴリズムは出題されませんが、もう少し複雑なアルゴリズムは色々と出題されます。

きりみんちゃんは以下のような典型アルゴリズムを解説エントリなどを読んでオーソドックスな問題であれば解けるようになるまで学習しました。

・DP(動的計画法)
・幅優先探索(BFS)
・深さ優先探索(DFS)
・累積和
・しゃくとり法
・再帰による全探索

データ構造や関数の知識
過去問やコンテスト本番で出題されたデータ構造や計算や高速化で使用する以下のような知識を覚えました。(元々知っていたけどあまり実用したことがなかったものなども含む)

・HashSetによる有無判定の高速化
・HashMapによるメモの高速化
・IntとLongの使い分け
・PriorityQueue
・BinarrySearch

計算量の意識
クライアントアプリエンジニアだったためあまり実務で計算量を意識することはありませんでしたが、だいたいのO(n)やO(n^2)、O(√N)などよくある計算量は見積もれるようになり、問題の制約(N <= 10^9)を見てだいたいどの程度の計算量が求められているのかが分かるようになりました。

数学の公式
元々は全く数学が出来ず、公式や用語などは何もしらなかったのですが、AtCoderに取り組むことで以下のような公式や知識を学びました。(ただし暗記しているわけではなく概念を理解し必要な時にメモを取り出してこれるという状態)

・約数
・最大公約数
・最小公倍数
・素数
・素因数分解
・平方根
・ユークリッドの互除法
・エラトステネスのふるい
・xy上の2点間の距離
・三角関数
・期待値

余談ですが、アルゴリズムや数学に関して学んだことはメモしてすぐに取り出せるようにしています。

整数論(算数)
後述しますが、だんだん過去問を解くだけではレートがあがらなくなっていき、ボトルネックが数学以前の算数の教養にあると気づき、それに関する学習をしました。
具体的には四則演算の法則や除算の余りを使ったグルーピング、数列の法則性を見つける考え方などです。
このあたりは数学というよりも中学受験で勉強するような内容に近いらしいです。

読んだ本

競プロの学習のために読んだ本です。
ネット情報での学習が主だったためあまり多くないです。

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

それほど専門的な内容ではないですが、有名なデータ構造やソートアルゴリズムの他に、グラフの探索や暗号化に関するアルゴリズムも非常に分かりやすい図で解説されていて良い本です。

数の悪魔―算数・数学が楽しくなる12夜

普及版 数の悪魔―算数・数学が楽しくなる12夜

子供時代に算数が好きだった人にとっては馴染み深い本らしいです。
具体的な数式などは出てきませんが、様々な数の法則などを面白く紹介している本です。整数への入門に読みました。

プログラマの数学

プログラマの数学第2版

数学ガールなどで有名な結城先生の本です。
こちらも数学というタイトルですが、数学の公式などを解説しているわけではなく、実際は算数または整数論について主に書かれた本で、まさにAtCoderで求められるような数の法則の見つけ方や問題の論理的な分解方法、組み合わせなどについて解説している本です。

この本は本当に読みやすくかつ数学問題に馴染みがない人が数学問題の解き方を考える上で必要な知識がたっぷりつまっていて、競技プログラミングの真の入門書といっても過言ではないと感じました。

Newton別冊『三角関数 改訂第2版』

Newton別冊『三角関数 改訂第2版』 (ニュートン別冊)

AtCoderで三角関数の問題が出題された時にほとんどの人が解けて自分だけ解けず愚痴っていたら「三角関数はプログラミングで非常によく使う」と全方向から指摘されたため覚えるために読みました。
この本とネットで解説しているサイトなどの情報を咀嚼してだいたいの概要を理解することが出来ました。

現状の成績

さて、ここまで長々と学習したことについて書いてきましたが、ここではその結果を紹介したいと思います。

結論から言うとレートという意味では目標に達することが出来ず挫折しました。

AtCoderではレートごとに色が設定されていて、きりみんちゃんは緑色になることを目標に1年間取り組んできました。
緑色はレート800以上なので、春頃には一度あと一歩のところまで行ったのですが、その後調子が悪くなり伸び悩んだまま今に至ります。

AtCoderのレートとその実力の相関には様々な意見がありますが、古くからのユーザーの間では「茶色までは基本的なプログラミングが出来れば到達でき、緑もそこから少し競技プログラミングの知識があればすぐに到達出来る」くらいの認識がされていることが多いです。

実際、色々な人のふりかえりエントリなどを読むと優秀な人の多くはAtCoderを始めてすぐに緑色前後までは到達し、そこから伸び悩んで過去問を解いたり典型アルゴリズムを学んだりといった勉強を始めたという人が多いようです。

温度感を詳しく知りたい方は以下のエントリが参考になると思います。

AtCoder（競技プログラミング）の色・ランクと実力評価、問題例 - chokudaiのブログ

AtCoder コンテストについての tips - Qiita

特にAtCoder社長のChokudaiさんのエントリにある以下の文章はきりみんちゃんがどうしても緑に到達したいと思っていた感情に大きな影響を与えています。

情報系の学生が茶色であれば、ちゃんと勉強してるなって印象になる
派遣で来たプログラマがAtCoder茶色だったら結構安心する
茶色があればエンジニアとしてアルゴリズム面においての安心感があるかと言われたら、正直物足りないみたいな印象があります。スキル的には、標準入出力、if、forなどの単純な操作はできる
問題文を正しく理解し、仕様通りの実装をすることが出来る
複雑な問題や、数学的処理が必要な問題を解決する能力はない
という印象です。コーディング試験でおなじみFizzBuzzは簡単に組める水準です。

悪く言えば自分にとって呪いの言葉になっていました。

数学が苦手な人間から見たAtCoder

まず前提として知っておいてほしいことは、AtCoderは数学好きによる数学好きのための競技プログラミングコンテストだと(少なくとも自分は強く感じると)いうことです。

運営や作問者、コミュニティ内のアクティブなユーザーのほとんどは数学が得意で数学に慣れ親しんできた人々だと思います。
そのため、問題には難易度とあまり関係なく中学高校レベルの数学の知識が含まれます。
しかしそれ以上に大きいと感じるのは、算数の教養が強く問われるということです。

これは例えば四則演算を駆使して差分を計算したり数列の法則性を見つけ割り算や余りを使って数列の法則性を見つけたりする能力です。
自然言語の問題文を計算式に変換し移項などを使って記述可能な式に変換するような能力も含まれます。

このような素養がある人にとっては、ABCコンテストのC問題くらいまでは計算自体は一瞬か少し考えれば直感的に分かり、あとは以下にコード上で式を書くかという問題に見えるため、プログラミングを始めたばかりでも基礎的な文法さえ覚えればとても簡単に解けるように思えるようです。

一方で自分のように算数の思考に慣れていない人間はまず計算の仕方を考える段階で詰まってしまうため、プログラミング以前に問題が解けません。

受験勉強などで長年数学の文章問題を解いていたり数学が得意な人にとってはこれらは特別にむずかしい公式を使うわけではなく直感的に分かるレベルの要素のため、「これは別に数学問題ではない」と言います。
そして「このただ式を書くだけの問題が解けないなんて信じられない」と思うようです。

この感覚の差が、AtCoderのレートに対するレベル感の認識が数学の得意な人と合わない原因となっていて、数学があまり得意ではないが計算ロジックをあまり書かないような分野で長年プログラマとしてコーディングが苦手だとは思っていなかった自分のような人間のプライドを引き裂いて来ます。

また、最近AtCoderのコンテスト参加者数は急増しているのですが、AtCoderの成績は相対評価のため、アルゴリズムなどは過去問や解説エントリなどが充実すればするほど平均レベルがあがっていき解けなかった時のレートの下がりは激しくなります。
急増している参加者も今のところは数学が得意な人が多いようで、数学的問題(特にO(1)と呼ばれるループなどをせず計算式さえ導き出せれば四則演算のみで解ける問題)のDifficulty(解いた参加者の内訳によって算出される問題の難易度)はかなり低くでます。

このような傾向はどんどん強くなっていっているような感覚があり、半年くらい前と比べても同じ実力では全然パフォーマンス(コンテストのスコア)がでなくなってしまった気がします。

レートにこだわるのをやめて総括エントリを書いている理由

元々、レートが緑になったら「算数が全く出来ないプログラマが緑レートになるまで」のようなエントリを書くつもりでした。
しかし、このままいくと緑レートになるまでずっとストレスと自己肯定感の喪失を味わった状態が続いてしまい、そして緑レートになるのはすぐにはむずかしいと感じたため、一区切りつけるためにこのエントリを書いています。

正直、緑になれなかったという挫折を表明するのはとても嫌だったのですが、そもそもAtCoderは順位を競い合うオンライン対戦ゲームとして運営されているもので教育的要素はおまけ程度だと明言されており、作問者は参加者の能力を測るためではなくユニークで面白い問題を作ろうとしていますし、コンテストの結果は相対評価のため環境の変化でレートというゴールポストは変動し続けます。
それなのに勝手にレートを学習のマイルストーンにしてしまったために、いくら時間を費やして学習しても自分が全く成長していないように感じてしまい良くない状態に陥ってしまいました。

また、前述したように最近のコンテストは特に算数の基礎体力を競い合うような側面が強く、これはいくら過去問を解いたり典型アルゴリズムの知識や実装力を高めたり数学の公式を学んだりしてもレートにはあまり反映されず、簡単には身につかない能力であるということが分かってきたということがあります。

自分と同じような人へ

きりみんちゃんは過去に「AtCoderは数学に苦手意識がある人でも数学やアルゴリズムの学習の題材にちょうどいい」というような布教をして(実際それは事実だと今でも思っています)、きりみんちゃん経由でAtCoderを始めたという方がそれなりの数いたり、きりみんちゃんが競プロに取り組む姿に励まされて応援しているという声を頂いたりもしているので、そういう人に対してきりみんちゃんが積極的に緑レートを目指すのを一旦諦めると表明することはハシゴ外しのようでよくないのではとも思いました。

しかし、逆に考えると同じようなモチベーションで始めた人たちがレートにこだわりレートが上がらないことで消耗したりプログラミング自体に苦手意識が生まれてしまったりしては本末転倒だということに気が付きました。

TwitterでAtCoderのコミュニティを見ていると学生でプログラミングを始めたばかりだけど緑レートどころかその上の水色や青色だという人がゴロゴロいるように見えるため、感覚が狂ってしまいますが、AtCoderは求められるプログラミング以外の能力がとても高いため、比べても仕方がない面があります。(数学オリンピックをやっていた人が大学に入ってAtCoderを始めたりしている)

きりみんちゃんは別にスーパーエンジニアでもフルスタックエンジニアでもありませんが、一応フリーランスのAndroidエンジニアとして長年有名な企業も含めいろいろな組織でアプリ開発をやってきた経験から書くと、茶色(レート400以上)どころか、灰色(レート400未満)でもABCのA問題とB問題が問題なく解けるレベルであればプログラマとして特に劣っているということはないと思います。
正直Web系も含め世のエンジニアがみんなAtCoderをやったら元々数学が得意な人以外で茶レートまで到達出来る割合も1割にも満たないのではないかなと思うし、業務時間外に競技プログラミングに取り組んでいるというだけで相当プログラミングが好きな方だし勤勉で向上心がありすごいことだと思います。

もちろんアルゴリズムや数学の知識はあれば役に立つこともあるだろうし出来る仕事の幅も広がると思うので、競プロを通してそれらを勉強することはとても良いことだと思います。
ただし、学習目的であればレートを目標にするのは能力以外の不確定要素が多すぎるのであまりよくないと思いました。
コンテストに参加して一喜一憂するのは楽しいですが、コンテストの結果は別にプログラミングの成績表というわけではないため、気にしすぎるとストレスになります。
スプラトゥーンのウデマエのようなものだというのが個人的には一番しっくりきます。

きりみんちゃん自身も、このエントリの前半で勉強したことを書き出してみて、「よくこれだけやったな」とあらためて思いました。
それだけやってきたことをレートが上がらないというだけで意味がないように感じてしまうのはとてももったいないと気付いたのです。

最後に

AtCoderをやめるわけではなく、コンテストは楽しいのでこれからも毎週参加すると思いますが、緑を目指すことに執着するのはやめます。

もしかしたら応援してくれている人の中にはがっかりした人もいるかもしれません。ごめんなさい。
でも今までAtCoderに取り組んできて学んだことはなくならないし、これからもいろんな事を学んでいろんな事に取り組むことで学び続けることの価値を見せていけたらなと思っています。

YouTubeもよろしくね！

きりみんちゃん kirimin-chan