468
296

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

プログラミング初心者の40代おじさんが3年半かけてAtCoder水色になった話(色変記事)

Last updated at Posted at 2024-07-30

こんにちは。六月と申します。

もう色変する日は来ないと思っていましたが、おかげさまで約2年半ぶりに色変しました。

というわけでまた、自分語りをする機会に恵まれました笑
きみたち、良かったらまた、おぢさんの話をちょっと聞いていかないか……。
お時間の許す方はどうぞお付き合いください。

なお、プログラミングの勉強を始めてから緑になるまでの経緯は
「プログラミング初心者の40代おじさんが1年かけてAtCoder緑になった話」
で詳しく触れております。よろしければ、そちらもご覧ください。

簡単な自己紹介

私は40代で、普段はIT業界ではない企業で働いています。私生活では中学生と小学生2人の3人の子を持つ父でもあります。大学は文系で、これまで情報科学の教育・訓練を受けた経験はありません。

子供が小学校の授業でプログラミングを習っているのを見て「今後はプログラミングが読み書きそろばん同様になるかも」と不安を感じ、ひょんな事からAtCoderの存在を知り、競技プログラミング(以下、競プロ)への参加を通してプログラミングの勉強を始めました。

2021年4月にAtCoderにユーザー登録。
2021年9月に茶色、2022年3月に緑色、そして今回2024年7月に水色になりました。

AtCoderにおける色と、対応するスキルについてはAtCoder公式の
「Algorithm部門のレーティングと業務における期待できる活躍」
をご参照ください。

緑コーダーになり仕事に好影響が出始める

私が従事している仕事では、プログラミングはまったく必要ありません。

ところが緑コーダーになった頃から、仕事中に「あれ?これはPythonでやれば速く終わるのでは?」というような、効率化・時短のアイデアが思いつけるようになってきました。
これは以前にはなかったことでした。

たとえば法人で自動車を購入する際、減価償却という作業を通じて費用化しますが、同じ取得価額であったとしても、新車と中古車とでは当期の償却額が異なります。当然、正確に計算しないといけません。

会社勤めをしていると、このような「つまらない。でも正確にやらないといけない」という仕事が沢山あります。私はこういう仕事については計算用のプログラムを書いて、片っ端からPythonにやらせる事にしました。

またある時は、業務管理ソフトを変更する事になり、旧ソフトでエクスポートした約10万行のcsvファイルを、新しいソフトでインポートできる形式に編集する必要がありました。

そこで、必要な置換をするプログラムをPythonで書き、約10万行を処理したところ1秒で終わりました。文字通り秒殺です。
このときは自分でもびっくりして「デュフフwww」と変な声が出ました笑
とは言えそんな大したプログラムではなく、難易度的にはAtCoder Beginner Contest(以下、ABC)のB問題くらいです。

仕事で使う事を期待してプログラミングの勉強を始めたわけではなかったのですが、競プロを通じて「Pythonでできる事」のノウハウを自分の中に積み上げてきた結果、自分のプログラミング能力が業務で活きる場面を、少しずつ見つけられるようになってきました。

競プロの成績は頭打ちに。自分の限界を知る

仕事に好影響が出始めた一方で、緑になってから、競プロの成績は完全に頭打ちになりました。灰色、茶色の頃も伸び悩みを感じてはいましたが、緑色になってからの停滞感は、それまでとは比べ物になりませんでした。

とは言えサボっていたわけではなく、むしろ可処分時間の大半は競プロの精進に費やしている状態。なので、緑になって以降はずっと「アクセルベタ踏みなのにスピードがもう出ない」みたいな感覚でいます。

緑になってから約2年半、自分なりに色々試行錯誤してきました。効果のあった精進もあれば、逆効果になってしまったものもありました。もしかしたら私と同じようにレートの伸び悩み期にいる人には、私のやってきた精進方法が参考になるかも知れません。何をしてきたか具体的に挙げていきますので、役に立ちそうなところだけ、つまみ食いして頂ければ幸いです。

令和ABC埋めによる精進

大ざっぱに言うと、緑色になるためにはABCでA~D問題の4完が必要なのですが、緑色を維持するにも4完が必要です。そこで、まずは4完を安定させるために過去問を1度全部解き直してみました。

126回目のABCから全4問→全6問になりました。このABC126以降を「令和ABC」と呼ぶことがあります。この令和ABCのA~D問題について順番に埋めていきました。水色Diff以上(Diffについては注記を参照)だと全然わからないものがあり、そういった問題はスキップしました。

この作業を通じて、D問題を解くまでに通常必要とされる典型アルゴリズムや典型思考は大部分をカバーできたように思います。とはいえ、問題量はそれなりに多く、毎週のコンテストへの参加とその復習もあるので、トータルで1年くらいかかりました。

DiffはDifficultyの略でその問題の難易度を表します。kenkooooさん運営のAtCoder Problemsで独自に算出された「その値のレーディングを持つ人が、コンテスト中に解ける確率が50%であると推測される値」です。
つまりDiffが1000の問題だと、レート1000の人の半数が解けるであろう問題ということになります。
(レート1000の人なら解けて当たり前の問題、という意味ではないという点に注意しましょう)

以降の本記事ではDiffが、

1~399の問題を灰Diff、
400~799の問題を茶Diff、
800~1199の問題を緑Diff、
1200~1599の問題を水色Diff、
1600~1999の問題を青Diff、

と表記します。

「鉄則本」による精進

2022年9月に、いい意味での激ヤバ本が出ました……。
赤コーダーのE869120さんによる『競技プログラミングの鉄則』(通称:鉄則本)です。この本はぜひ、一周まわすべきです。

私は競プロ用途でかなり本を買っている方だと思いますが、累積和の応用として、imos法の使い方を具体的に載せている本を、鉄則本以外で見た事がありません。
(もし見落としていたらごめんなさい…)
おそらく、水色Diffくらいまでの問題を解くのに必要なテクニックやアルゴリズムはほぼ網羅されているように思います。

ところで先日、ABC358のC問題でビット全探索の問題が出題されたのですが、コンテスト後にDiffを確認したら273しかなく「ビット全探索が灰Diffってヤバすぎない!?」と腰を抜かしそうになりました…

私が競技プログラミングを始めた2021年4月頃と比べると、2024年7月現在、ABCの参加者は明らかにハイレベル化しています。その理由の一端には、鉄則本のような良質なテキストが登場し、初心者からレベルアップするための学習環境が大きく整備された事もあると思います。

ライブラリの充実

競プロerには私と同じ1970年代生まれの方も沢山いらっしゃいますが、その中に日本人の暖色コーダー(黄色、橙色、赤色のこと。神の領域)は2024年7月現在、3人だけです。さらにその中でもナンバーワンが、hamamuさんです。

二分探索は有名なアルゴリズムで、Pythonでもbisect_leftといった便利な関数(C++のlower_bound相当)が用意されています。ところが私はこの二分探索が極めて苦手で、毎回bisect_leftやbisect_rightの返す値が何を意味していたのか、混乱してわからなくなってしまっていました。

そのようなグチをXに投稿したところ、hamamuさんよりその後の競プロ生活を大きく左右するアドバイスを受けました。これは実際のキャプチャを見ていただいた方が早いでしょう。

色変記事_画像1.jpg

色変記事_画像2.jpg

このアドバイスを受けて、意識が大きく変わりました。

私はそれまで、言語に標準ライブラリが用意されているのであれば、使う側がそれに慣れなければならないという先入観を持っていました。

しかし競プロの場合は極端な話、車輪の再発明だろうが何だろうが、AC(正解)が取れれば良いわけです。つまり、標準ライブラリが用意する関数の使い方にどうしても慣れないのであれば、直感的に使えるような関数を自分で作ればいいのです。

また、hamamuさんのようなトップレベルの人でも自分と同じような悩みを持っていたことには大変勇気づけられました。加えて、トップレベルの人はそういった細かいところでもライブラリ整備の手間を惜しまないのだと、感銘を受けました。

そして私は試行錯誤の結果、ある値xとソート済の配列を渡したときに

(1)x未満の要素数
(2)x未満の値の開始インデックス
(3)x未満の値の開始インデックスの値
(4)x未満の値の終了インデックス
(5)x未満の値の終了インデックスの値
(6)x以下の要素数
(7)x以下の値の開始インデックス
(8)x以下の値の開始インデックスの値
(9)x以下の値の終了インデックス
(10)x以下の値の終了インデックスの値
(11)x以上の要素数
(12)x以上の値の開始インデックス
(13)x以上の値の開始インデックスの値
(14)x以上の値の終了インデックス
(15)x以上の値の終了インデックスの値
(16)x超の要素数
(17)x超の値の開始インデックス
(18)x超の値の開始インデックスの値
(19)x超の値の終了インデックス
(20)x超の値の終了インデックスの値

と、20個もの値を返す「mybisect」という過保護な関数を作りました。我ながら超アホです。きっと混乱せずに二分探索の関数を使いこなせる人から見ればバカバカしい代物だと思います。でも私の場合これを作ってからは、二分探索の問題が出たときに添字で悩む事は文字通り激減しました。

この他にもたとえば、2次元配列を時計回りに90度回転させるといったような「書けない事はないが、ちょっと実装に時間がかかりそう」な処理を要求する問題が出たときは、コンテスト後に自作の関数を作り、ライブラリ化してすぐに呼び出せるようにしました。

なお、hamamuさんが黄色になった時の色変記事は大変参考になりますので、ご紹介しておきます。

イチから自分で書いてみよう精進

前述のライブラリ整備と正反対の趣旨になりますが、あるアルゴリズムを一から自分で書いてみるというのもよくやっていました。

たとえばABC223D問題の「Restricted Permutation」は、ただ単にトポロジカルソートをするだけでなく、さらに辞書順最小のトポロジカル順序を求める、という問題です。このようにABCでは、ある典型アルゴリズムを要求に沿って正しく改造できるか、を要求する問題が、特にD問題あたりでよく出ます。

こういった問題が出題された時に、自分用ライブラリとしては持ってるけど中身の動作についてはよくわからない、という状態だと問題を解けません。なので、私はそれまでにつまづいた問題の中から、「これは一から書けるようにしておきたかったね」というものをピックアップし、移動中などによくスマホでポチポチ書いていました。

よく書いていたのは、いま例示したトポロジカルソート以外ですと、

  • しゃくとり法
  • ダイクストラ法
  • trie木
  • Binary Indexed Tree(Fenwick Tree)
  • DFSを使ったオイラーツアー
  • 最小添字規則に基づくチーム分け(ABC236D問題「Dance」のような分け方のこと)

あたりです。

これは最悪、紙とペンでもできる精進なので、時間のない多忙な競プロerの人にもオススメです。

高難度問題による精進(失敗バージョン)

2023年7月頃、私のレートは1000近辺で停滞していました。緑になってから約1年半が経過し、日々の精進も適当にこなしているだけのような気がして、何か打開策が必要だと感じていました。

そこで、それまでに全く手をつけてこなかった、緑より2色上の青Diffの問題に手を出し始めました。ABCの問題は、基本的には複数の典型アルゴリズムの組み合わせでできているため、青Diffの問題であれば1問あたりの精進効果も高いであろう事、それに加えて、本番で青Diff相当の問題をもし解ければ、かなりの順位アップが期待できると見込んでの事でした。

結論から言うと、これは失敗でした。

というのも、自分のレートより2色上の問題になると1問を理解するのにとんでもなく時間がかかってしまって、他の事が全然できないのです。結果として、レートはどんどん下がっていきました。具体的には、本番で茶Diffくらいの問題にものすごく手こずるようになりました。ただこなすだけのように感じていた茶Diffや緑Diffの問題を繰り返し解く事も、実はレートを現状維持するのに必要な、大切な精進だったのです。

最終的に、2023年9月9日のABC319ではまさかの2完と大惨敗。このやり方はダメだと、精進スタイルの修正を余儀なくされる結果となりました。当時「約数系包除」などを履修しましたが、私が主戦場とするABCのC、D、E問題あたりでは全然出てこないので、使う機会もなく、今では完璧に忘れちゃいました笑

おそらく、レートが伸び盛りの競プロerの方は自分のレートより2色以上難しい問題であっても意味のある精進になるはずですし、やるべきです。私のように同レート帯で長期間伸び悩んでいる人だと、自分のレートより2色上のDiffの問題を精進に取り入れても、どうせ実戦で使わないし、理解するのに時間もかかり過ぎるしでデメリットの方が大きいのだと思います。

高難度問題による精進(成功バージョン)

青Diff精進で手痛い失敗をした私は、自分のレートよりどの程度Diffの高い問題であれば取り組んでも大丈夫なのかを、慎重に見極める事にしました。

そして問題の難易度や1問あたりの復習時間等を勘案して試行錯誤した結果、「精進はDiff1400までの問題にとどめておくのが良さそうだ」という感触を得ました。私の場合はDiff1400を超える問題だと、理解に時間がかかり過ぎたり、理屈はわかるがコーディングしようとしても手が止まってしまう、という事が明らかに増えたのです。

そこで、8問体制になったABC212以後でDiff1200-1400の問題だけを難易度順にピックアップし、これを易しい方から順番に埋めていきました。イメージとしては、自分の限界よりちょっとキツめの柔軟体操を続ける事で、少しずつ体を柔らかくしていく、みたいな感覚でしょうか。

この精進に取り組み始めたのは2024年に入ってからですが、実感できるくらいに効果があり、具体的にはE問題が解けて5完できる回数が明らかに増えました。なぜ今までやらなかったのだろうと、それまでの自分を恨みました笑

AtCoder Daily Training(ADT)による精進

2023年10月に、AtCoder Daily Training(以下、ADT)というサービスが始まりました。ADTは、AtCoder公式のバーチャルコンテスト(以下、バチャ)で、毎週火・水・木に、時間を分けて1日3回開かれ、ABCの過去問から出題されます。
(ただし、バチャなのでレートの変動はありません)

このADTが始まった事が、私にとって大きな転機となりました。

精進で地味に悩ましいのが、どの問題を解くか決めるのは意外に面倒だという事です。ADT以外にも色々なバチャがありますが「解く問題を自分で決めるのが面倒なので、とりあえず何かバチャに参加し、そこで出た問題をやる」という人は多いと思います。特に、社会人競プロerは皆さん精進時間を取るだけでも大変だと思うので、なおさらです。

そこで、私はできるだけADTに参加すると同時に、参加できなかった回の問題については、AtCoder代表取締役のchokudaiさん & ADT運営担当のkaede2020さんから出された「宿題」とみなし、Diff300~1400の問題を可能な限り全部解くようにしていました。

たとえばこんな感じ。
以下の表は、2024年7月第4週のADTで出題された問題のDiffを一覧にしたものです。

色変記事_画像3.jpg

1週間に出題された全81問中、私がターゲットにしているDiff300~1400の問題だけをピックアップすると、全部で25問です。これを順番に問いていきます。

灰Diff上位の問題も加えている理由は、前述の通りABCの参加者がどんどんレベルアップしていて、最近だとちょっと工夫が必要な全探索、みたいな問題が灰Diffになってしまうからです。コンテスト本番だと、意外にもそういう問題に足元をすくわれたりするので、私の場合はDiff300以上から精進対象にしていました。

このADT精進も明確に効果がありました。広く万遍なくある程度の量の問題を毎週解く事になるので、コンテスト本番でつまらない取りこぼしが減りました。同時に、問題を解くスピードは明らかに速くなりました。

また、それまでは何をすべきなのか自信が持てず、場当たり的に精進して迷走しているだけなのかもしれない、という不安感がありましたが、ADT精進を始めてからレートが伸び始めたので「やっと進むべき道が明確になった!」という安心感も大きかったです。

水色になった日

ADT精進を毎日のルーティンにしつつ、Diff1200~1400のちょい高難度精進で、少しずつ自分の限界を広げていく。

この方針で精進を続けた結果ジリジリとレートが伸び始め、2024年7月27日のABC364に出た後、レートが1200を超えて水色になりました。
実に142回目のコンテスト参加でした。

AtCoder Problemsのデータによれば、水色になるまでに私が解いた問題のユニークAC数は1707、総AC数は約5500でした。問題によっては1回しか解いていないものもありますし、10回以上解いている問題もありますが、単純に均すと1問あたり3回以上は解いているという計算になりました。

最後に ~40代を生きるということ~

30代の頃は、「体感的には20代の頃と何も変わらんね」と思っていました。

ところが40代になると老眼が始まり、目のピントは合わなくなるし、白髪は出てくるし、テレビに出てくるアイドルは全員同じ人に見えるしで、自分が生物としてピークを過ぎ、終わりに向かいつつある世代だという事をはっきり自覚するようになりました。

また、仕事も忙しいのに、子供の学校や習い事の送り迎え等で時間もお金も取られます。加えて私くらいの年齢になると、子供だけでなく自分の親の事でも時間を取られるようになってきます。最近では墓仕舞いをどうするとか、空き家をどうするとか、スーパーネガティブな用事も舞い込むようになってしまいました…笑

要するに、公私ともにやる事が多すぎて、自分の事は後回しにせざるを得ないのが、40代なのかなという気がしています。趣味は生活に彩りを与えてくれますが、40代で新しく何かを始めるというのは、状況がそれを許さなかったりするし、衰えを感じて気力が湧いてこなかったりして、実は結構難しい事なのです。まわりを見ていても、そのように感じます。

そのような状況下で、競技プログラミングという新しい趣味に出会えたのは、実はとてもラッキーな事だったんじゃないかなとしみじみ思う事があります。

これを書いている現在ちょうどパリ五輪が行われていますが、試合結果を受けて、喜怒哀楽を全開にするアスリートの気持ちにはすごく共感できます。なぜなら、私も自分なりに競プロに全力で取り組んでいて、結果が伴う喜び、結果がついてこない悲しみが痛いほどわかるからです。でも、考えてみればこの年になって、自分がなんらかの競技に参加できている事、自分の事でこれだけ熱くなれている事は、とても幸せな事だと思っています。

客観的に判断すると、能力的にも脳力的にも、おそらく私には水色が限界です。でも不思議とまだモチベーションは高いままです。どこまで行けるかわかりませんが、情熱が続く限り、この新しい趣味を大切にしていこうと思っています。

長くなりましたので、そろそろ筆を置きます。
もし私のように、同レート帯で伸び悩んでいる人の参考に資するヒントがあったならば幸甚です。
大丈夫、私にできたのだから、あなたにもきっとできます。

ここまでお読み頂き、本当にありがとうございました。
今週もADTがありますからね笑
これからも、お互い精進がんばりましょう。

468
296
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
468
296

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?