高卒30歳が三ヶ月でAtCoder緑になれたので色変記事書く
似たような記事はいくらでもありますが、自分を追い込むために記録しておきます。
こんだけイキリ散らしておいて茶ランクに落ちたら相当恥ずかしいぞ俺。
レート推移
緑二回目のコンテストで参加回数14回なので、緑に上がったのは13回目のコンテストですね。
スペック
タイトルはちょっと盛っていて、高卒は高卒でも大学中退です。大学は一応理系でしたが、プログラミングとは全く無関係。
業務ではVBAを使っているくらいで、IT業界は未経験。
AtCoderでは独学で身につけたRubyを使っています。
AtCoderを始めた理由
転職したかったんです……。(結論)
詳述すると、某転職サイトにて転職活動していた所、そのサイトに競技プログラミング機能がありました。
企業へのアピールになるとの事で挑戦してみたのですが、最高ランクの一歩手前で行き詰まってしまったのです。
こりゃダメだ、というわけで、とりあえずAtCoderで緑を目指してみる事にしました。
未だに転職できていません。
緑ランクになるまでにやった事
勉強以外
まずは環境設定。Rubyインストール、vsCode導入、標準入力設定など。
また、標準入力を1セットにしました。標準入力はどの問題でも絶対に使います。最初は以下のページからコピペしていました。
そのうち手間にキレて標準入力だけをまとめたファイルを作り、ファイルごとコピペしてから使わない入力を消すようにしました。だんだんそれも面倒になって、6ファイルをまとめたフォルダを作ってそれをコピペしてリネームしています(コンテストは基本的に六問構成)。今はそれすら億劫になり、1クリックでコピペ・リネームが終わるバッチファイルを書きました。
勉強
AtCoderを始めた直後は「円グラフは知っていてもエッジとノードの方のグラフは知らない」「剰余の加減乗算はできても逆元の計算はできない」という惨状でした。むしろ転職サイトでよく次点ランクまで行けたな。
自分の実力の把握
二回ほど受けてみて、しょうもないケアレスミスさえなければABCのA,B問題は解けそうな気がしました。なので「いかにABCのC問題を解けるようになるか」を目標に設定。 例えばここに挙げられた10問も前7問は無視し、ラスト3問だけ解きました。
アルゴリズムの学習
実はAtCoderを始める前に転職サイトの兢プロでTLEを連発しており、「どうも自分は無駄な計算を繰り返しているらしい」という事は薄々感づいていました。
この予感は、ABCのC問題がTLE祭りになった事で確信に変わりました。計算量を類推する訓練をして、計算量を大きく削減する定石を学ぶ必要がありました。
定番アルゴリズム一通りの知識
最初に読んだのが「なっとく！ アルゴリズム」で、
次に読んだのが蟻本です。
今から考えると、わざわざ金払わなくてもこういうサイトで十分だったかもしれません。
そもそもアルゴリズムの参考書・参考サイトで使われているのはほぼ全てがC++かPython。Rubyの知識しかない私にはサンプルコードが読めず、自分が正しく理解しているか確かめられません。
大体、数学理科の公式だって漢字だって英単語だって、参考書を読むだけで丸暗記なんかできません(私見)。それらを使って問題を解くに限る、という事で演習に入ります。
演習問題
参考にしたのが以下のページです。
ここの100問のうち、ABCの問題を全部解きました。(良い子のみんなはJOIも解きましょう。できればAtCoder以外の問題もアカウント作って解きましょう。)
また、この頃になるとAtCoder Problemsの存在を知ります。精選問題のABCを埋め終わった後は、緑diffと水色diffだけに絞って解いていきました。
やらなかった事
簡単すぎ、難しすぎな問題
茶diff以下の問題は、解いても実力が付かなさそうだったので無視する事にしました。また青diff以上の問題は、解説を読んでも理解出来なさそうだったので後回しにしました。
この決定はRubyも遠因です。低diff問題にもオーバーフローや小数精度など、C++にとっては罠になっている部分があって訓練になります。しかしオーバーフローがなく、分数(Rational)クラスがあるRubyでは単純作業になってしまいます。また実行速度が遅いため、高diffの問題は想定解法どおりにアルゴリズムを組んでもTLEになってしまう事もあります。高難易度問題の高速化で四苦八苦するよりは、中難易度の問題に多く触れようと考えました。
毎日AC
ヒートマップは穴だらけで、ストリークは全然伸びません。
私はこの手の継続記録伸ばしすぎると、うっかり途切れさせたときに全てのやる気をなくす人間です。そこであえて継続記録を無視し、「ちょいちょい辞めてちょいちょい戻る」スタイルにしました。時間がない日に簡単すぎる問題を1問だけ解く、通称「虚無埋め」は人を選ぶやり方だと考えいます。私にとっては無意味どころか、むしろ時間がある日にも難しい問題を解かなくなって逆効果になるのが私です。簡単すぎる問題の演習をやめた意味がありません。
解説AC縛り
解説を見てACを出す、通称「解説AC」は「自力で解けない事を認めるようで嫌だ」みたいな人もいるらしいです。ちゃんと測ったことはありませんが、私は平均5分、長くても20分で解説を見てしまっていると思います。
勉強とは「解けない問題を解けるようにする事」、分解すると「解けない問題を探して」「それを解けるようになる事」だと思っています。逆に言うと自力で問題を解いている部分は「解けない問題を探して」いる段階であり、ここで全部の問題が解けちゃったらむしろ勉強にならないわけです。解けない問題に固執するより、早めに解説を見てしまって次の問題に行った方が時間コスパは良さそうな気がします。
緑に上がるまでにACした問題数
緑以上のACは50問か60問くらいです。こんなに灰ACいらんやろ。
パフォーマンス推移
まぐれで1500代出して緑ランクに滑り込んだのがバレバレですね……。
時々悲惨なパフォーマンスを出していますが、これはネトゲのイベント消化しながらコンテストを受けた時です。
今後の予定・目標
緑diff問題演習を控え、水色diff問題に集中
前述の通り、私は簡単な問題を解くことには否定的です。(本番コンテスト以外では)解けそうでギリギリ解けない問題の解説をたくさん読みたいので、緑diffは捨てて水色diffを解きまくっていこうと思います。青diffは無理です、少なくとも今は。
コーディング速度改善
AtCoder Type Checkerで測ってみた所、「解くのが遅い」(その分高得点を取ってレートを釣り上げている)と言われてしまいました。
タイピング速度が遅い自覚がありますが、いくらなんでもRuby使いの私がC++メインのAtCoder平均に負けるのはおかしいでしょう。つまり書き始めが遅い、なぜならアルゴリズムを考えている時間が長いからだと推測できます。脳内の計算量オーダーを削減するため、脳内データベースを充実させて検索するだけにしていきたいです。
DP補強
私は数あるアルゴリズムの中でも、DPが特に弱点です。問題文を見てもどんな漸化式を立てていいかわからず、解説を見ても何を言っているかわからない問題がよくあります。 まずはここらへんを勉強して、それでもまだ苦手だったら ここでDP問題漬けになる予定です。
転職サイトのランクを上げ、転職
忘れちゃダメですがAtCoderはサブ目標で、メイン目標は転職です。
「転職するまでウマ娘始めないの誓い」を立てているので、いつまでたってもウマ娘やれない……。
Discussion