2017年以前
プログラミング経験はほぼないのですが、いずれできるようになりたいな、とは思っていました。一番の切っ掛けはAlphaGoです。今までできないと思われていたことが機械学習（やディープラーニング）でできるようになってきているんじゃないかと興味を持ち、どんなことができるのか雰囲気だけでも知りたいと、2017年にCourseraの機械学習コースに取り組みました。
……うん、まあ、雰囲気は分かったかも？
一応、講座中のプログラムの課題も頑張りましたが、自力で解決できなかったものも多く、やはり実際にプログラムを書いた経験がないと辛いなぁ、と実感しました。
2018年4月 AtCoderを始める
そんなこんなで、四月からプログラミングでも始めようと思い立ち、入門に何が良いのかな？ と探してて出会ったのがAtCoderでした。知人でやっている人もいたので、それ以前から知る機会はあったはずなのですが、「AtCoder」という名前をちゃんと認識したのは2018年に入ってからです。
そのときの実力は、
・数学 数学科出身なので、できなくはないはず！ とはいっても、大学の数学は全然分からず、ほとんど身に着いていないのですが……。
・プログラム 基本的には未経験。講義などを受けたことは一度もなく、まともに勉強した経験はないのですが、昔々にN88-BASICに触ったことがあります。あと、C言語入門をざっと読みましたが、Eclipseでプロジェクトを一々作成するのが面倒くさくてやる気が起きませんでした（課題は全くしていない）。あとは、前述のCourseraの機械学習コースの課題をやった程度。
という感じ。
あ、ただ、P≠NP問題、ラムダ計算といったあたりは勉強したことがあります。
AtCoderを始めるにあたって、AtCoder Beginners Selectionを解き始めたのですが、そのとき使った言語は、Courseraの機械学習コースで使っていたOctaveです。それまでプログラムには面倒くさい印象が強かったのですが、Octaveは直観的に分かりやすく、計算機の拡張という感じがあって、非常に好印象でした。
今でこそC++も多少読めるようになりましたが、CやC++やJavaしか知らなければAtCoderを始めようとは思わなかったのは間違いないです！！
ABC086C - Traveling（OctaveでACしている人もいますが、計算量的に辛い模様）以外はどうにか解き終え初めて臨んだコンテストが、AtCoder Beginner Contest 093。結果はCまでの三完、654位。
……まあまあでは？
ただ、この回のDは700点問題なのですが、プログラミング的な技術を問わない純粋な数学問題で、数学の方の伸びしろはあまりないだろうし、勉強したところでこんなのできるようにならないのでは？ と不安になりました。
ところで、記念すべきコンテスト初提出が、これなのですが……バグってますね。後で全く同じコードを提出してACもらえています。
コンテスト中は、
なんでこれでTLEなんだろう？→コメントを消したら通るかな？→提出したら通ったやったー！ コメントって消した方が早くなったりするんだね
などと思っていましたが、そんなことはないですよね。マイナー言語でやるとTLEになることがあるらしいですね。
2018年4月～5月 緑になるまで
最初のコンテスト参加後、Octaveはどうも不利らしいと知ったので、違う言語を探しました。でも、できるだけOctaveに似た言語がいいな～、と探して見つけたのがPythonです。
これが正解でしたね！
Octave以上に書きやすいし、（C++などに比べれば遅いとはいえ）PythonやPypy（同じコードでも大体Pythonより速く実行してくれる！）で間に合わない問題に出会うことはあまりない。AtCoderで青を目指すだけなら（多分、黄色も？）Pythonを選択するのが一番の近道だと思います。
他の人のC++のコードを読めないことは多少辛かったですが、Pythonの提出も少なくないのでそれほど困りませんでした。今はさらに増えているので、Pythonで競技プログラミングをする環境はさらに整ってきていると思います！
なお、IDEはずっとIDLEを使っています。行番号が表示されないのはちょっと嫌だけど使いやすいよ！ 評判悪くて、ほとんど使っている人いなそうだけど……。
というわけで、PythonでAtCoder Beginners Selectionを解き直し、次のコンテスト（ABC094）からはずっとPythonで参加しています。
この頃は、AtCoderではコンテスト参加～復習以外ではほとんど問題を解いていません。その代わりに、paizaさんのスキルチェックの問題を結構解いていました。
paizaのことは4gamersの記事（多分これ）で知ったのですが、当時は標準入力の意味が分からず挫折。いつかやってみたいと思っていました。AtCoderの問題に触れて、今なら解けるんじゃないかな、と。
paizaでの最初の提出が4/10で、五月までに約五十問（うち七割がD問題）解き、ゲームもしたりと、Pythonの文法を身につける段階ではお世話になりました。5/21にSランク取得して以降も、頻度は落ちましたが新着問題を中心に解いています。
ただ、コンセプト上仕方ないですが解説などないのと、同ランクの問題で難易度差が大きいためちょっと使いにくいですね。Sランクの問題は、大体AtCoder点数換算で400～600くらいのものが多いのですが、このとき解いた問題は200～300点程度です。
特に、最近のSランク問題は難しいものが多いようなので、簡単な数問で失敗するとSランク取得の難易度は一気に上がると思います。
さて、そうこうしているうちに、5月後半にはAtCoderで緑色にたどり着くことができました。
ABCのC問題（300点問題）は、アルゴリズム等プログラミング力ではなく数学力が試される問題が多いので、言語に慣れればそれほど苦労せず緑色になれました。
苦労せず、とはいっても、Zero-Sum Rangesが解けずAGC023が0完に終わったり、数学問題のFive, Five Everywhereを思いつけず、呆けてるなぁと実感したり、ABC097で初めてCが解けず二完に終わったり、と色々ありましたが……。
ただ、200点/300点の差は、主に論理的思考力や数学力の有無を問う部分なので、人によっては大きなギャップを感じると思います。算数と数学の差に似ているというか（いや違うかも）。問題を解いているだけでできるようになるものなのかな……。人によっては300点/400点より苦労する気がします。
そんな中、一番印象に残っているのはABC097のD - Equalsです。Union-Findを理解できず一週間近く苦しみました。
ただ、そのおかげでデータ構造の面白さや意義に気付けた気がします。今思うと、競技プログラミングに真面目に取り組むようになった切っ掛けかも？
今でもUnion-Findには愛着があります。
2018年6月～8月 水色になるまで
この時期になると、AtCoderの問題の難易度や、レートの目安が分かってきました。本質的には数学なので、数学の問題とは一番比較しやすい。大学入試の数学の問題は、AtCoder換算で300～500点の問題がほとんどという印象です。700点クラスになるとかなりの難問ですね。
また、レートですが、たとえば東大入試の数学だと、
水色……60点くらいは大体いつも取れる
黄色……90点くらいは大体いつも取れる
くらいの印象です。
青色≒東大合格という意見も目にしましたし、青になった今だとそれも納得できるところがありますが、受験数学には部分点があるのも大きいので、計算や答案の書き方の訓練をそこそこ積んでいるなら、理一・二合格は（数学に関しては）水色程度の力で十分だと思っています。
また、Beatmaniaなら、
水色……8段
青色……10段
黄色……皆伝
というprdさんのツイートを見かけました。いや私は今でも、水色は八段より難しい気がするんだけどそうでもないのかな……。緑色≒八段、水色≒十段、青色≒中伝くらいな印象なのですが。とはいえ、黄色≒皆伝という印象は私も同じです。
ただ、BeatmaniaⅡDXで皆伝になるまでに私は13年（3rd style～tricoro）かかってるので、黄色になるまでそんなにかかったら困るんですけどね！ 時間がかかり過ぎてて客観的に見られないところがある。
また、七月に、競技プログラミングをやっている知人に会って話を聞いたところ、その人が黄色だということが分かりました。
以上と、自分の能力から考えるに、
水色には、なれるはず。できるだけ早くなっておきたい。
青色には、できればなっておきたい。
黄色は年単位で努力を続ければなれるはず。
くらいかな、と。
そして、水色になるためにはABC全完しないときつい。今のままでは400点問題がほとんど解ける気がしない！ 400～500点を取れるようにするため練習量を増やさねば！
そう思い、他の競技プログラミングのコンテストに参加を始めます。
具体的には、
CSA 7/19から
Codeforces 7/26から（マラソンコンテストには7/18から参加）
（8/25に水色になっているので、以下は水色になった後ですが）
TopCoder 9/19から
LeetCode 9/9から
という感じです。そして、AtCoder優先ですが、CodeforcesやLeetCodeには今も可能な限り参加するようにしています。
（※2019年6月、追記 LeetCodeの問題は就職試験からの転載で、著作権的にどうなの？ という話があるようです。Contest問題はオリジナルだと思っていましたが、それも転載かもしれないようで。避けるのが良いかもしれません）
とはいえ、参加数を増やすのは諸刃の剣ですね。
練習量は増えますが、その分復習する時間を取りにくくなるし、生活は乱れます。ただ、他のサイトでもレートがつくのは楽しいし、続ける原動力になります。以前、囲碁クエストや将棋クエストに嵌っていたときも感じていましたが、レートがつくのは本当に楽しい！ 特に競争が好きというわけじゃない（と思う）のですが、レートで客観的な自分の能力が分かり、努力してそれを上げていく……というのは非常に面白いです。
しかし、今思うとこの時期は無駄に焦っていた気がします。
水色に早くならなきゃ、と思ってしまったせいもあり、必要以上に緊張していたような。今よりずっと一喜一憂していました。三ヶ月ほどで水色にはなれたのですが、結構辛い時期でした。
そんな中、八月あたりに自分用のライブラリを作り始めたことは良かった。何が切っ掛けだったか覚えてないのですが、前からやらなくちゃ、と思っていたことにようやっと手を付けた感じでした。
頭の整理になったし、作ること自体も楽しかった。
この頃、一番印象に残っているのは、なんといっても、ABC099のC - Strange Bankです。初めてのABC全完で嘘解法！ 結構話題になった問題ですが、この嘘解法で通した人は他にあまりいないのでは……？
今となっては笑い話ですが、当時は「最初の全完が嘘解法って良いの？」と、動揺してしまいました。
でもまあ、これが切っ掛けになったのか、その次のABCでは無事全完でき、400点なら解けることが増えていきました。
2018年9月～ 青色になるまで
水色になった記念に、昔作ったアカウントを掘り返してTwitter（@titia_til）を始めました！
まず、「競技プログラミングアカウントだからプロフィール画像とかプログラムで作った方がいいよね」とPythonを用いてプロフィール画像を作成。なお、このプロフィール画像は、同心円っぽくなるはずが、計算間違いでアステロイドっぽくなって、あれ？ と思ったやつです。
そして、Python競技プログラマーを中心に気になっていた方をフォローしました。それまでも、コンテストごとにTwitterで情報集めはしていましたが、大分やりやすくなりました。たいしたツイートできていないけど、読んでくださる方に感謝。
このブログも、その頃に解法を書いたり記録残したりしたいと思って作ったのに、一度も記事を書いてない！
水色になるとABCではレートがつかなくなる、というのは大きな差ですね。私もARC102からARCに参加するようになりました。
緑色の時代からARCに出るという人もいるようです。確かに、ABCの100点、200点問題は、緑色以上の人にはあまり練習にならないだろうから一理あると思いますが、私は水色になるまでARCに出ようとは思いませんでした。Cから解くとなると、一問もできないという不安と向き合わねばならないので……。
そして、ABC onlyの回でレートがつかなくなると、レートがつくコンテストの頻度が結構下がってしまいます。頻繁に開催されるCodeforcesがモチベーションの維持に役立ちました。
なお、水色になっても、競技プログラミングの勉強自体は、緑時代とほとんど変えていません。たくさんコンテストに出て、触れた問題（コンテスト中に読み、考えた問題）はできるだけ復習する、というのが主です。AtCoder換算で700点あたりまでの問題は解説ACしたい、と思っていますが、全部はできていませんね……。本を読んだりもしておらず、出会った問題ごとに調べているだけです。
ただ、水色ということはABC卒業なのだから、ABCの問題は全部解けるようにならなきゃまずい、と思い、ABCを001から解き始めました。これが（難しいとは聞いていましたが）予想していた以上にきつく、勉強になった気がします。
非公式時代のABCは、やや難しいけれど典型、という問題が多く出題されており、水色～青色で必要な知識を身に着けるにはちょうど良かった。このおかげで400～500点問題の正答率がかなり上がった気がします。
600点以上の問題はいまだにほとんど解けませんが。
あと、一応、敬遠していたC++の勉強も少ししています。
IDEはCode::Blocksを使用。プロジェクトを作らなくて良く、すぐに実行結果を見ることができるものなら何でも良かったのですが、よく勧められているVisual StudioやVSCodeで開発環境を作るのは私には無理でした……。
Code::Blocksなら（コンパイラーのセッティングで、C++17にチェックを入れることさえ気付けば）、ほとんど何もせずに上の条件を満たしてくれたのでありがたかったです。
AtCoder Programming Guide for beginners の第一章は読んだので、C++の基本的な読み書きなら分かるようになりました！ どうしてもTLEになる、というときは使いたいと思っています。
ただ、やっぱりPythonの方が記述は簡単だし、「（Pythonで）TLEなコードを書けて、計算量的にC++では収まっている」ならACはもらえないけど実質（数学的には）正解じゃない？ わざわざACコードまで書かなくても良いんじゃ？ という気持ちもあるので、本当にいざというときにしか使わないと思います。
そして、新年一発目のAISing Programming Contest 2019で、早めの四完により最高パフォ2400＆青色到達しました！
それまでの最高パフォは、CADDi 2018のときの2130だったのですが、このときは、D - Harlequinの嘘解法が通ってしまったおかげなんですよね。嘘解法で最高パフォというのはなかなかに屈辱だったので、それを払拭できたのも良かったです。
まとめ
各コンテストについて。
・AtCoder……発想力重視の面白い問題が出題され楽しいが、典型手法を身に着けるにはあまり向いていない
・Codeforces……雑多な出題で、面白い回もあればそうでない回もある。系統立てて勉強するには向かなそう。難読問題も多い。
・LeetCode……ABCよりやや難しいくらいの難易度。典型問題が多いので勉強向き。ただ、標準入出力じゃないのにちょっと戸惑う。特に、Binary Treeのclassを扱う問題がよく出るけど、これって一般性あるの？
という感じ。
TopCoderはDiv.1とDiv.2の難易度が離れ過ぎている（最近はそうでもないようですが。私はDiv.1に上がって三回連続でeasyも解けなくてやる気が落ちた）印象があってあまり出ておらず、出題傾向等は分かってません。
青になって十日ほど経っていますが、現在のコンテスト参加数は、
AtCoder 43回（非公式コンテストやマラソンコンテストを除く）
Codeforces 42回（Ratedのみ）
LeetCode 19回
TopCoder 4回
yukicoder 3回
Hackerrank 1回
Hackearth 1回
三桁超えてるんですね。AC数は、
AtCoder 489
CodeForces 193
TopCoder 3
LeetCode 69
AOJ 9
yukicoder 11
Hackerrank 2
Hackearth 11
paiza 約120
合計2000ACになる頃には黄色になれたらいいなぁ……。
今は、ABC埋めが終わったら、ARCかLeetCodeを埋めるのが良いのかなぁ、と思っています。
緑色のときくらいから、「自分にはもうほとんど伸びしろがないんじゃない？」とか、「次の色まではなんとかいけても、二つ上は不可能なんじゃない？」とか思ってましたが、青色になってもまだまだ勉強・練習すべきことは残っているし、ありがたいことにまだ多少の伸びしろはありそう。
また、競技プログラミングは他の勉強より効果が現れやすい。
というのも、解けなかった問題を解説ACするとき、解説を読んで「頭の中で再構成して」コードに直す、という工程を経るので、一問一問理解して次へ進むことができるから。それに、他の人のACコードが読めるなど、解説を読んで理解できなかったときの勉強の材料も揃っている。
なので、今の自分に適正な問題（AtCoder換算で500～700点あたり）を300～500問くらい解けば、次のステップにいけるはず、という気がしています。
青色は一つの目標でしたが、先が見えているうちは先へ進みます。
あ。
当初の動機だった機械学習系には、競技プログラミングに嵌ってしまったこともあって、一切手をつけてないのですが、それもいずれ……？
0 件のコメント:
コメントを投稿