AtCoderを始めて5ヶ月弱。2024/08/31 開催の AtCoder Beginner Contest 369 で入緑しました。せっかくの機会、色変記事を書けることは滅多にないと思うので初めて記事を書きました。
自己紹介
- 40代非エンジニア(仕事はITと全く無関係、文理に分けるなら完全に文系)
- 中学受験経験あり、算数は得意だった
- 中高の数学はぼちぼち、大学で完全に挫折
- 大学は情報学科+修士卒
こんな経歴なのでIT系の知識とかプログラミングには興味(未練?)があったりします。趣味として楽しむ計算機科学。
始める前(2023年後半~)
- プログラミングは大学 + 大学院で C と Ruby を少しだけ
- HTML, CSS, PHP と MySQL を使ってデータベースを使う Web サイトを作ったこともある
- 競技プログラミング自体は大学時代に同級生が取り組んでおり、存在は知っていた
- 昔からちょっとやってみたいとは思いつつ、重い腰を上げられずにいた
- AtCoder の存在は Twitter で知っていた
昔からプログラミングは学びたいと思っていたけど特に作りたいものはない、そんな僕には問題を解くこと自体が目的になる競技プログラミングが合っていました。
最近ようやくやる気になり情報を集めていたら「アルゴ式」 https://algo-method.com/ という Web サイトを見つけました。半年間ほどこれで勉強しました。理解は不完全なものの一応は大半の問題を解きました。このときにPythonを習得。たまに実行速度の遅さに足を引っ張られる(※ABC363-C)こともありますが読みやすくて良い言語だと思います。C++は学生時代のプログラミング演習でCに苦労した記憶があるのと、コードの見た目がややこしそうなので今は敬遠……。
アルゴ式での半年間の助走があったので厳密には「5ヶ月で入緑」とは言えないかもしれません。AtCoder 開始時点で既に茶色相当の実力はあったと思います。
2024年4月 開始
まずは大まかな歴史を。4月頭にAtCoderに登録。実践形式でやってみたかったのでバーチャルコンテストを使って過去問を解きました。適当にABC250を選択してそこから昇順に解き進めていきました。いきなりC問題まで解けて自分スゴイと思ったものの、これだと茶色相当でしかないことにすぐ気づきます。
「典型90問」を見つけて簡単なものから解き進めました。そして★4で詰まります。典型といいつつ割とひねった問題も多く、理解も難しく感じました。もっとシンプルで基礎的なものを求めるなら書籍の方が良いと思います(結局僕は書籍は使っていないのですが)。
しばらくして AtCoder Problems の存在を知ります。AtCoder のアカウントさえあれば登録なしで使えるというお手軽さ。非常に便利です。
初めて参加したコンテストはABC348で、いきなり3完できて大興奮。そしてABC350ではその日覚えたばかりの Union-Find が出題され、見事4完できました。とても嬉しかったです。
この頃はとにかくいろいろな技を身につけようとしていました。
特に有用だったのが以下の2点。
- list の代わりに set, dict を使い、計算量を減らす
- 全探索(itertools の活用、bit全探索も含む)
この2つを習得するだけでかなりの問題が解けるようになったと記憶しています。あらゆる場面で活躍する技なのでこれは少しでも早く身につけておくべきだと思いました。
2024年5月 入茶
ABC353で再び4完し、待望の入茶を果たします。AtCoder開始から1ヶ月強。このときはすぐにでも緑に上がれる気でいました。甘かった……。基本的に3完、たまに4完という感じだったのでD問題が目下の課題でした。ABC250以降のバーチャルコンテストとは別にABC249以前のD問題を個別に解いていくことにしました。
新しい技を覚えるためにいろいろと背伸びしていました。ネットの解説を読んで頑張って自分でセグメントツリーを書いてみたり(遅延の方は全く理解が追いつきませんでした)。また、ライブラリ化することを学びました。皆どうやってあんなに速く解いているのかここでようやく気づきます。Union-Findなんか毎回一から書いてられませんもんね。とりあえず使えさえすればいいのならライブラリを自分で書く必要すらありません。
この頃に覚えて非常に有用だったのが SortedList, SortedSet, SortedDict です(参考: https://qiita.com/Shirotsume/items/706742162db68c481c3c )。これひとつ知っているだけで簡単に解けるようになる過去問がいくつもありました。先に挙げた2つに加えてこれも基本です。
2024年6月 少しずつ背伸び
過去問のD問題が難しくなかなか進まないのでC問題も解き進めていきました。ほとんどは解けるものの、わからないものも多々あり得られる知識はたくさんありました。「ABCの200番台には典型が詰め込まれている」という発言をTwitterで見たのでそれにならい、解いていました。
ABC357で初の2完を経験。C問題がややこしかったです。配列の扱いがよくわかっていない、アルゴリズム以前にプログラミング自体の理解が浅いことを痛感します。さらにABC359でもC問題を落として2完。後で見たら過去問に類題(ヘクスを考える)があり、これが思い出せればなあと悔やみました。
この頃にはABC200番代のC-D問題をほぼ解き終えていました。diff の低いものから解いていたので難問がいくつも残っていましたが。
AtCoder Problems での AC 数は 450問程度、レートは719まで上がっていました。
Twitterで「できる人には200-299のC問題→200-299のD問題→200-299のE問題……と解いていくことを勧める」という発言を目にしましたが、自分のやり方は間違っていないんだと安心しました。
2024年7月 墜落、基礎から学び直し
200番代のC, Dが大体終わり、とうとうE問題に手をつけます。当然なかなか解けず、解説を見てばかりです。解説を読み、わかったようなわかっていないような気になりながらとりあえずAC。Atcoder Problems の diff を頼りに少しでも簡単そうな問題を探して解けないか考える。そんな状態でした。
そこで迎えたABC362。レートは753まで上がっており、早ければ今月中にも入緑できるのではという期待が高まります。そして結果は……なんと屈辱の1完。B問題すら解けなかった。後から解説を見れば三平方の定理……算数が得意なつもりだっただけに大きなショックを受けました。ショックが大きくC, D問題も全然解き方が思いつかず早々にギブアップ。レートは74下がり679。
基礎から学び直す必要を強く感じました。そこで欲を出して新たな技を身につけたり高難度の問題に挑戦したりするのを一旦やめて、100番代のC問題を解き進めていくようになりました。
2024年8月 入緑!
7月に引き続き、今度は100番代のD問題も解き進めます。最終的にはABC125からABC301までのD問題の内、大半を終えることができました。
7月末からのABC364, 365, 366で3連続の4完を決めます。連続での4完はこれが初めてでした。この3回でレートは664から763まで99も上昇。再び緑を射程に捉えます。解く速度も上がっており、基礎を固めた成果が出てきているように感じました。
そして迎えた月末、ABC369で初の5完&水パフォを決め、レートが763から829に急上昇。悲願だった入緑を果たせました。これまでの頑張りが実を結び、大きな達成感を得られました。AtCoder Problems での AC 数は 740問程度です。AtCoderを始めてから1日平均5問弱を解き続けたことになりますね。
思ったこと
基礎を固めるか、応用を学ぶか?
どちらも必要ですが僕は基礎に重点を置きました。入緑にはC問題までをほぼ確実に正解し、さらにD問題を高い頻度で正解し続ける必要があります。可能な限り苦手分野を潰してあらゆる問題に対応できるようにしておかなくてはいけません。B問題やC問題に足をすくわれてレートを大きく落とした経験からもこれを強く思うようになりました。
また、難しい問題の解説を読む際にも基礎がしっかりできていた方がやりやすいと感じました。簡単な課題から消化し、徐々にレベルアップしていくのがいいと思います。
先に書いたとおり僕はABC125-301のC, D問題の大半を解きました。典型90問の★2・★3・★4も解いています。これが難しい人は書籍を使った方がいい気がします。
コンテスト中の立ち回り
解けない問題に直面したとき、それより後の問題を見に行くか今の問題に集中するかは判断に迷う場面です。後の問題を全く見ないのはさすがにもったいないと思いますが、今のところコンテスト本番で前の問題が解けずに後の問題が解けたということは一度もありません。僕の場合は前から順に取り組んだ方がよさそうです。ここは人によって好みの分かれるところでしょう。
何を要求されている問題なのかを意識する
問題が解けなかったとき、「自分はどこに気づければこの問題を解けたのだろう」を考えるようにしていました。なんと同じことが書かれた記事がありました。https://www.geekly.co.jp/column/cat-geeklycolumn/specialtalk4_ikyu_atcoder/ また、この記事にはこんなことも書かれていました。
AtCoderで作問をやっているような人間に言わせると、AtCoder Beginner Contestの問題のうち難易度が低いA問題からC問題くらいのものは、20通りくらいのパターンに分類できてしまうらしいんです。コンテストに参加してる普通に人からすると「そんなわけない」という感じなんですが、そこまで抽象化がうまい人であればどんな問題にもうまくアプローチできますよね。
これを見て問題ごとに「何をテーマにした問題なのか」を意識するようになりました。一度分類して表にしてみたいと思いつつなかなかできていません。
加齢の影響
AtCoder に参加されている人の多くは20代の若い世代、それも学生が多いです。中には中学生の方までおられます。というわけで若者中心の遊び場の端っこの方におっさんがこっそり混ぜてもらっています。もっと若い頃に始めていれば……と思わないわけではないですが、加齢による衰えは実はあまり感じていません。というより自分のことなので自覚するのが難しいんですね。若い頃はもっと頭がよく働いていたかというとそうでもない気がします。難しい課題に直面するとすぐにあくびをしてました。
プログラミングに限らず「才能や頭の回転速度よりも経験の方が大切」というのが持論なのですが今のところ競技プログラミングでもそう思っています。もっとも、これは僕がまだ浅瀬で水浴びしてるような状況だから言えることなのかもしれません。もっともっと高いレベルを目指すとなると、きっと才能や頭の回転が必要になってくるのでしょう。
これから
とりあえず緑に上がれたことで満足していますが、まだまだ自分の可能性を試してみたいと思います。次は典型90問の★5問題を徐々に理解できるようにすること、過去問のE問題を解いていく予定です。難しすぎて思うようには進まないかもしれませんが頑張りたいと思います。
実力はともかくとして、この歳になってから新しいことを学べていること・新たな趣味に出会えたことは大きな喜びです。