今日も8時間睡眠
888文字のブログです
🕒 2019/12/16 この記事は大体8888文字ですプログラミング

【長文】AtCoder、始めてました

🏅

今月は、今年始めたものをいくつか書いていこうと思っています。今日は、2019年の3月末から始めている、AtCoderについて書いていきます。ちなみに、今時点でのレートは、水の中をさまよっている感じです。競プロに役立つ内容はなくて、ほぼ自分語りです。

【目次】

競プロとは

AtCoderは、競技プログラミングのサイトです。競技プログラミング（競プロ）は、要求を満たすコードを速く正確に書く、プログラミングのコンテストです。

競プロについてもう少し詳しく書くと、次のようになります。まず、「こういう入力が与えられるので、こういう結果が出るようにしてください」という感じで問題が出題されます。入力値については、制約が与えられます（整数であるとか、どういう範囲の値であるとか、個数がいくつとか）が、具体的に何かはわかりません。コードを提出すると、サイト側が用意した各入力値に対して、提出したコードの出す結果が要求していたものと合っているかがチェックされ、すべて合っていれば正解となります。こうして、コードを提出するまでの速さと正確さを競います。

例えば、「100以下の正の整数nが与えられるので、1からnまでの整数の和を求めるコードを書いてください」というような問題が出たとしましょう。コードを提出して、サイト側で用意した結果と同じ内容が出力されるかが判定され、一致していれば正解となります。間違っていても、どの入力値について間違った結果が出ているかはわかりません。

和を求めるには、for文を使ってもいいですし、和の公式「n(n+1)/2」を使っても構いません。実行時間やメモリの制限もありますが、結果が合っていれば、コードはどのように書いてもOKです。

数学っぽい問題だけでなく、迷路のスタートからゴールまでの最短移動回数を求めるとか、ゲームのルールが与えられるのでその勝者を答えるといった、数学っぽくない問題も出ます。

paizaとの出会い

僕が「競プロ」に近づくきっかけになったのは、paizaです。paizaは、競プロサイトというよりは、転職サイトです。paizaには、スキルチェックの機能があり、これが競プロで使われているシステムとほとんど同じです。

スキルチェックでは、問題が与えられて、コードを提出します。そのコードが、事前にサイト側で準備していた結果と同じものを返すかどうかで判定されます。この部分が競プロと共通しています。自動でコードが判定されるスキルチェックの仕組みはすごく画期的でおもしろいと感じていたのですが、競プロとして昔からあった仕組みだったんですね。

paizaはコンテストではなく、あくまでもスキルチェックという立ち位置なので、他の人と競争するわけではありません。普通の競プロでは、他の人よりも速く、多く問題を解くほうがいいのですが、paizaは基準を超えるかどうかだけが重要なので、少し考え方が違います。この難易度の問題をクリアできれば、あなたはこのランクです、このランクだとこういう企業に応募できます、というふうに話が進んでいきます。

paizaを使って、一度内定が出たこともあった（参考：1年間の無職期間を経て就職したので、無職期間を振り返ってみる）のですが、ランク自体はAからなかなか上げられませんでした。どうやって上げればいいか、まったくわからない感じでした。

このときは、計算量の考え方や、グラフとかアルゴリズムの話など、まったくわかっていませんでした。なので、A問題はたまに実行時間オーバーになっていましたし、S問題は実行時間オーバーになるか、まったくコードが書けないか、のどちらかでした。

また、解けなかった問題の解説もない（まだ他の人が挑戦するため）し、何を勉強すれば解けるようになるのかもわからず、モヤモヤしていました。「書いてある通りの処理を実装してるのに、なぜ時間オーバーになるのかわからない」（＝計算時間を短縮することを知らない）という状況だったので、S問題は惨敗し続けました。ランクを更新するために各問題に挑戦できるのは初めの1回だけなので、今となっては貴重な機会を無駄遣いしてしまったなという感じです。挑戦できる問題が減っていくのはもったいないので、ある時期から遠ざかりました。

だいぶたってから、本屋で「プログラミングコンテストチャレンジブック」（いわゆる蟻本）をたまたま見つけ、「これで勉強すればいいのか！」と思い、興奮して購入しました。が、難しくて序盤ですぐに力尽き、コードを試して学ぶ気にもなれず、結局paizaも蟻本も長期間放置することになってしまいました。

AtCoderとの出会い

蟻本を見ていたので、競プロの存在は知っていました。そんな中、たまたまAtCoderを見つけました。

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

後で調べてみよう。こういう系のやつはpaizaしかやったことないし。

2019/02/12 11:30

これは今年の2月で、この時点ではまだ登録はしていませんでした。しかし、ネットでバズっていた次の記事で変わりました。

こうしてGoogleに入社した(kumagi編) - Software Transactional Memo

この記事の中で「AtCoderで緑だったけど、Googleのコーディング面接に通過できた」とあって、俄然やる気になってきました。別にGoogleに行くつもりはない（というか行けない）けど、自分の力がどれくらいなのか知っておくことは安心感につながるじゃないですか。

そういうわけで、この記事を読んだ3月26日に、即、AtCoderに登録しました。

そして、けんちょんさんの過去問精選10問をもとにつくられたAtCoder Beginners Selectionをさっそく全部解きました。paizaでAランクなら、これらの問題はだいたい解けます。以後、3月30日のコンテストから参加しています。だいたいほぼ毎回出て、スコアは水色の下半分あたりをうろうろしています。

名前を知っていたものの、AtCoderにはなかなか登録できずにいたのですが、それはサイト自体がちょっと近寄りがたかった、というのがありました。説明されていないことがいろいろあって、たとえば、どういうコンテストがあって、それらはどう違うか、みたいな全体図を説明してるようなのがあまりなくて、いろいろ不安でした。提出したコードは全部公開されますが、それを消したり非公開にすることはできないのかもよくわからず、この点でも躊躇していました。今となってはダメなコードを世界中に公開されることに何のためらいもなくなりましたが。

paizaは昔に比べてアニメ絵が増えて、あれはあれで近寄りがたくなったのですが、AtCoderよりはすんなり登録したと思います。上のブログを見て勢いで登録していなかったら、まだ登録してなかったかもしれないです。

競プロと数学

僕は、なかけんの数学ノートという数学サイトを運営していて、大学でも数学を専攻していたので、全人類で見ると、ある程度数学はできるほうです。競プロでは、数学をやっていると有利だという話が出てくるのですが、ここからはこの話題について書いていきます。

数学をやっていて良かった点

数学をやっていると競プロで有利か、というと、それはそう、です。

高校まででやった数学の公式や考え方をそのまま使う場面があります。場合の数とか整数に関連する問題はよく出題されるし、数列の内容もよく出てきます。式の計算、ルート、指数の計算を使う問題もあります。あると便利、ではなく、ないとダメ、な問題もあります。

問題文に苦手な数学のワードがあれば、「あ、このワードはわからないからこの問題は解けないな」となるのでいいのですが（本当はよくないのですが）、問題文を読んだだけでは解けそうなのに時間をかけても解けず、解説を見たら「数学のこの定理を使います」と書かれていれば、「数学がわかってないとできないじゃん」と、（怒）になることもあるでしょう。これがきっかけで去っていく人もいるかもしれません。

数学をやっていればどんな定理でも知っている、というわけではないですが、こういう解説に出くわしても、「なるほど、この定理はこう使うのか」となって、理解にもそんなに時間はかからないし、次に同じような問題をみたときに応用することもそんなに大変じゃないです。見たこともない定理を理解するところからだと、やっぱり時間はかかってしまうので、そういう意味では数学をやってた人の方が、問題を解きやすいし、復習してからの伸びも速いと思います。

具体的な例でいうと、フェルマーの小定理というのがあります。pが素数でaがpと互いに素なら、aのp-1乗をpで割った余りは1となります。この結果は知っていましたが、二項係数を計算する際、mod pの世界で逆元を求めるために、aのp-2乗を使うことを知り、「競プロの世界では、フェルマーの小定理をこう使うのか」とすごく感動しました。この内容を書きたいなと思って、自分の更新している数学サイトで【競プロ】記事の一覧に記事を書き始めました。力尽きてますけども。

ここまでの話は数学の知識が競プロに使えるという話ですが、もっと根本的なものもあります。そもそもですが、競プロの問題への取り組み方が、数学の問題への取り組み方と似ているので、その点でも有利になります。

例えば、問題文を読んで、すぐに絵をかく、線で表すといった基本動作は、競プロでも行いますが、もちろん、数学でも行います。問題を考えるときも、具体例で考える、簡単な例で考える、場合を分けて考える、極端な例を考える、といった切り口は、競プロでも数学でも共通して使います。負の場合を正の場合に帰着させるとか、同じか違うかで場合分けをするとか、必要条件から攻めるとか、ある整数で割った余りで分けるとか、こういった発想は、競プロで役立ちますが、数学でも頻繁に行っています。

つまり、数学の問題を考える姿勢が身についていると、競プロの問題も似たような姿勢で考えられるので、有利になる、というわけです。

ただ、競プロをやるために、数学を単体で一からやり直すというのは、遠回りです。実際には、数学的な「知識」は、出会うたびに身に着けていく、数学的な「考え方」は、競プロの問題を考える上で養っていく、というのが効率がいいんじゃないかと思います。「いや俺は競プロの頂点を目指す」というなら、数学はどこかのタイミングでやる必要はあると思います（大学レベルを含む）が、僕はそのレベルじゃないのでちょっとわからないです。

数学をやっていて良くなかった点

数学は競プロの問題を解くのに役立ちますが、たまに邪魔になることもあります。

記憶に残っているのが、ABC 135 D - Digits Paradeです。0から9までの数字と?が含まれている文字が与えられるので、?に数字を入れて、13で割った余りが5になるものがいくつあるかを答える、というものです。

文字がすごく長い（最大で10万文字）ので、直接13で割ることはできません。こういう場合、倍数判定法というのが使えることがあります。簡単なものは、2の倍数とか5の倍数ですね。これは一の位を見るだけで判定できます。

あまり自明でない例だと、3の倍数や9の倍数です。各桁を足して割ったときの余りと、元の数を割ったときの余りが一致します。このことは中学や高校でも習います。

マイナーではありますが、13の倍数についても判定法はあります。【応用】倍数判定法（7と11と13の場合）にも書いていますが、下から3桁ずつ区切り、符号を変えながら足していって、その答えが13の倍数かどうかを判定すればOKです。

僕は、このことが頭をよぎり、この内容を使って解く方法を考えていました。下から3文字ずつ切って、符号を変えていきながら足す。いやでも?のところには数字を入れないといけない。うーん、どうするんだこれ。めんどくさいな。

実はこの問題は競プロで使うもっと典型的な方法を使って解きます。コンテスト中に僕もたまたまその方法を思いつけたのでよかったのですが、数学の知識を振りほどくのに結構時間を使ってしまいました。

数学の内容を使える場面もあるのですが、必要のない場面で使ってしまったり、逆に面倒になるような場面で使ってしまうこともあります。つまり、数学を競プロでどう使うかをよく身につけておかないと、道具が多すぎて時間をロスしてしまうことにもなります。

競プロは数学ゲームか？

競プロと数学との関係について最後に書いておきたいのは、数学の応用の仕方はいろいろあるということです。

数学を学問として学ぶことと、数学（や数学に関係のある内容）の問題を解くことには乖離があります。例えば、難関中学の算数の入試問題は、ほとんどの人が解くことができません。しかし、使っている道具は小学校で学ぶものばかりです。ではなぜ解けないかと言うと、道具の応用方法を身に付けるには練習が必要だからです。補助線の引き方や割合を使った解き方などは、よく練習をしていないとなかなか使うことはできません。

これは、高校入試もそうだし、大学入試でもそうです。東大や京大の問題であっても、使っている道具は高校数学の範囲なのですが、その道具の使い方・組み合わせ方は練習が必要だし、結論にたどり着くまでの論証の構築の仕方なども練習が必要です。

競プロでも数学の内容を使うものがありますが、どのように応用するかは練習しないとダメです。また、入試問題にはない特徴はあると思います。細かく見ると、競プロのサイトによっても違うでしょう。なので、数学をやってる人が皆、競プロもできるというわけではありません。

また、数学を勉強していた人の中でも、数学の分野によって得意・不得意はあるし、競プロの問題を解く上で必要なアルゴリズムやデータ構造まですでに知っている人は少ないです。

数学の素養があれば問題が解きやすいし、レートも上がりやすくなることは事実ですが、数学だけで結果が決まるわけではなく、それ以外の要素も結構あります。例えば、僕には実装力が全然ないです。解説を読んで数学的な部分が理解できないことはあまりないし、考察の部分ができていることもありますが、どう実装すればいいかで詰まることがよくあります。

例えば、これはネタバレにもなりますが、ABC 127 F - Absolute Minimaという問題を解いていたときのことです。これを見た瞬間に、これは中央値を考えればいいとすぐにわかりました。自分が数学サイトに書いた、【発展】分散はなぜ2乗して求めるのかでも同じ式を扱っていますし、結果は知っていました。ただ、中央値を求め続けるコードは、コンテスト中には書けませんでした。

実装の部分まで解説に書いていることは少なく、解説動画や他の人が書いたコードを読みといて学んでいくことが多いですが、なかなか身に付けづらいところだと思っています。

競プロは業務に役立つか

競プロは業務に役立つか、という話題もよくあがります。

競プロの問題を解くには、プログラミング言語の文法を知っていないといけませんし、アルゴリズムの知識なども必要になってきます。そのため、コードを書く仕事に役立つという意見もあります。一方で、競プロで出てくる問題が非現実的であるとか、みんなが提出しているコードが読みにくいこともあり、役立たないとか、逆に悪い影響を与えているという意見もあります。

個人的には、自分の業務に競プロはほとんど関係していません。業務で書くとしたらVBAがメインなので、競プロとはだいぶ距離があります。趣味で触るのもphpです。paizaではphpで解いていたし、AtCoderもはじめはphpで挑んでいました。ただ、それでは競プロの問題を解くのが厳しくなってきたので、C++を使い始めましたが、競プロ以外ではまったく使ってないです。

ただ、世の中には、競プロでやる内容が役立つ業務もあるんだろうなぁ、とは思います。実行時間やメモリの制限があったり、大規模データを扱ったり、データ構造が複雑であったり。そういう業務は、高度過ぎて僕には関係のない世界ですが、すごく難しい課題を解決しないといけない大きな企業ではそういう業務もあるんでしょうね。

競プロが業務に役立たないという人の意見もわかります。実際の業務では、言語やシステム、ビジネスの理解のほうが重要で、アルゴリズムとかデータ構造はそんなに必要ないということもあるでしょう。僕もVBAでコードを書くときには、アルゴリズムよりも、エクセルの機能について詳しい方が重要な場面が多いです。エクセルが白くなってTLEするとダメですが、人間は2秒以上待ってくれるので多少遅くても問題ないですしね。

まぁそういうわけでおもしろくない結論ですが、競プロが役立つ業務と役立たない業務があるんでしょう。たぶん、世の中の多くのプログラマーは、競プロが役立たない業務（というか、競プロ以外に役立つものがたくさんある業務）をしていると思います。上の方でもリンクしたchokudaiさんの記事からもわかる通り、水色や青色なら実務上は十分でしょう。

AtCoderにどう取り組んできたか

水色のレベルなので参考にはならないと思いますが、3月末から今にかけてどういうことをやってきたかを書いていきます。

まず、C++の勉強をしました。競プロを解くときにしか使わないのですが、やってて損になる言語ではないと思ったので、今の業務に必要かどうかは気にしていません。

本やサイトも見ています。蟻本は結局前半しか読めていませんが、まだそのレベルの問題で悪戦苦闘しているので十分でしょう。ネットにあるものでは、問題解決のためのプログラミング一巡りがまとまっていて、とてもいいです。

AtCoderの問題を解説しているサイトも見ています。けんちょんの競プロ精進記録が多いです。他にも解説しているサイトはありますが、自分にとっては行間が広すぎるものが多いです。公式の解説ページか解説動画でわからなければ、他の人の提出コードを見て考えることもあります。

他の人のコードは、なかなか自分に参考になるものを見つけるのは難しいです。よくやる検索方法は、速く正解したものの中から、コードの長さが短いものをいくつか見る、という方法です。コードが長い場合、マクロ登録が多く、コードが読みにくいケースが多いのでパスしています。

自分がコードを書くときも、他の人のコードをまねしてマクロを使っていた時期もありましたが、最近はVSCodeでスニペットを使うように変えました。マクロを使うと短く書けることもあるのですが、使い方をミスってしまうこともあったので。

GWに過去のC問題を全部解くつもりだったのですが、昔のC問題は難しいものも多く、かなり時間がかかってしまいました。4月の末から始めて、6月の中旬にようやく終わりました。中にはわからなくて解説ACをしたのもあります。今は、AtCoder Problemsに上がってくるオススメ問題の中から適当に選んだりして、毎日1問は解くようにしています。時間があるときは難しめのを、ないときは過去のA問題とかを解いています。

過去問を解いた後は、どの問題をいつ解いたか、どういう問題でどういう風に考えて解いて、どういうところでミスしたか、解説とはどう違ったか、ということを、ローカルでメモするようにしています。効果があるかは謎です。

過去問の解説を書くこともいくつかやってますが、レートが高くないこともあって、あんまり気が進まないです。古い問題は解説がないこともあるので、解説を書きたくなることもありますが、「こんなに古い問題の解説を書いても、誰も読まないだろうな」となって、やる気が出ません。

当初はできなかったけど、ある程度理解できるようになったものは、動的計画法、二分探索、深さ優先探索、幅優先探索、二項係数の計算、XORの問題、ビット全探索、しゃくとり法、グラフでの最短経路問題、などです。

今年の後半では、「数か月前の自分だったら絶対に解けなかっただろうなぁ」という問題が解けることも多くなり、成長が実感できるようになってきました。解ければ解けるほどレートが上がる状況が続いていたのですが、今年の終盤になってからは、ミスしたら即レートが下がる状況となってきました。ミスれないのはつらいです。できる問題の種類を増やしていかないと維持することすら難しくなってきたので、しんどい時間帯が続きそう。

アルゴリズム実技検定について

12月14日に行われたAtCoder アルゴリズム実技検定を受けました。検定ビジネスはいろんなところがやっていて、うさんくさい内容のものもありますが、AtCoderはコンテストの実績があるからまったくそんなところはないですね。

実は受けるかどうか迷っていたのですが、結果的には受けてみてよかったです。今年から競プロを本格的に始めて、1年間の総まとめ的な役割になりました。結果は、70点の中級でした。

これからも少しずつ精進していきたいですね。当面は、ABCの問題が全完できることや青色になることが目標です。

(8887文字)

バックリンク