見出し画像

子育てしながらAtCoder水色になりました。

こじま

色変記事です。ABC369(2024-08-31)でようやく水色になれました。まずは成績の紹介から。

ABC369で水色になりました。コンテスト参加回数は107回です。
総ACは828問です。
D問題を多く解いてます。
茶〜緑Diffが多いです。
青Diffを少しだけ解いてます。黄Diffは4問だけ。

プロフィール

  • プログラミングとはまったく縁のない仕事をしています。

  • 国立大学理学部卒。数学系の学科でした。

  • 20年ほど前に基本情報技術者試験は合格済み。

  • Pythonを使い始めたのは2021年の夏から。Progateに1ヶ月だけ課金しました。

  • ニュースやSNSでAtCoderを知って参加。初めてのRatedはABC220（2021-09-26）でした。

競プロ学習の達成度は？

主に、E869120さんの記事（以下、『上達ガイドライン』）を参考にして勉強してきました。『上達ガイドライン』では、水色コーダーに到達するためのステップとして、

  • 標準ライブラリ 25個

  • 基本アルゴリズム 12個

  • 基本データ構造 3個

をマスターすることが推奨されています。これらの達成度を確認してみたいと思います。

標準ライブラリ 25個

『上達ガイドライン』では、C++の標準ライブラリから25個をピックアップしています。Pythonに読み替える際に、特に重要だと感じたものは以下の7つでした。

1. queue → collections.deque

Pythonでは両端キュー。BFSで必須なので頻繁に使います。超基本。dequeは「デック」と発音することを今知りました。

2. priority_queue → heapq

優先度付きキュー。「要素を追加しながら、最小値を高速に取り出せるデータ構造があればいいのに！」と競プロ初期に悩んだものです。便利なものがありました。ダイクストラ法で必須です。

3. map → dict / collectons.defaultdict

連想配列。defaultdictが便利すぎて、気がついたら使ってます。本当に便利で、競プロでPythonを使う喜びを感じられます。

4. lower_bound → bisect

二分探索。使用頻度はやや低め。sortedcontainersが使えるようになってから、更に出番が減った気がします。

5. set → sortedcontainers

順序付き集合。以前はPythonの泣き所でした。sortedcontainersが使えるようになるまで、tatyamさんのSortedSetとSortedMultisetに頼りきりでした。感謝。

6. next_permutation → itertools.permutations

順列の生成。使用頻度が上がっている気がします。順列を扱う問題が増えているのでしょうか？

7. bitset → ビット演算

ビット集合の型。Pythonなら各種ビット演算子を使います。灰〜茶色では、ビット演算を使うことは稀でした。ビット全探索やビットDP、二分累乗法を使うようになってから、ビット演算の重要度が増してきた気がします。

以上、標準ライブラリについてでした。Pythonで分からないことは、すぐにnkmkさんのところで検索しています。たいへんお世話になってます、ありがとうございます。

基本アルゴリズム 12個

『上達ガイドライン』で紹介されている基本アルゴリズムは12個あります。水色になるために必要な程度には理解できているだろう、と自己評価してます。緑色になった頃の自分と比較すると、問題にアルゴリズムを当てはめる力もつきましたし、実装もスムースになってきました。

アルゴリズムごとに、感想、理解を深める手がかりとなった問題、ヒントになった記事などを紹介します。

1. 全探索

全列挙、ビット全探索、順列全探索など。ABCに参加し続けるだけで、全探索の基本は自然と身につきます。ビット演算やpermutationsも、繰り返しチャレンジしていたら慣れました。

半分全列挙はまだ一回しか見たことがありません。解けるようになりたいですね。

2. 二分探索

バグらせがちでしたが、めぐる式二分探索のおかげで苦手意識はなくなりました。二分探索を使うべきかの見極めが、もっとスムースにできるようになりたいです。

Yokan Partyは必須です。やりましょう。

3. 深さ優先探索（DFS）

どちらでもよいときには、BFSに頼りがち。書く機会が少ないため、やや苦手なままになってます。コンテストでDFSが必要な問題に出会うと、うっかり間違えてしまうことが何度もありました。

Pythonで再帰を書くときは、おまじないが必要です。スニペットに登録して使っています。

4. 幅優先探索（BFS）

頻繁に使うので、ごく自然に書けるようになりました。Pythonで競プロを始めると、最初にimportするのはdequeだと思います。

01-BFSを学んだ問題です。この問題のおかげで、その後のダイクストラ法がとても理解しやすくなりました。

5. 動的計画法（DP）

沼です。様々なパターンがありますが、「値が確定しているところから始める」という原則が大切だと思っています。Educational DP Contestは半分も解いていないので、まだまだ伸びしろがありそうです。

最長共通部分列問題。『上達ガイドライン』を見直したところ、基本問題扱いになっていました。やりましょう。

『上達ガイドライン』より、区間DP。あまり使ったことがありませんが、この機会に解いてみました。「円環は2周にする」は、好きな基本テクニックです。

AC済みで区間DPの問題もありました。やや難しいです。

6. ダイクストラ法

heapqが使えればOKです。グラフを扱うテクニックを身につけるほうが大切な気がします。

7. ワーシャルフロイド法

3重ループが必要なアルゴリズム。制約を見れば使う場面かどうか分かるので安心です。

水色入りを決めた一問です。基本アルゴリズムの組み合わせで解けるタイプの問題。直近のコンテストでは、残念ながら知識不足で解けない問題が続いていました。水色手前で足踏みしていましたが、ようやく解ける問題が来てくれて、ほっとしました。

8. クラスカル法

あまり使わないので、出会うたびにアルゴリズムの正当性が気になりがち。軽い辺から順番に、Union-Findすれば上手くいきます。

9. 高速な素数判定法

『上達ガイドライン』では試し割り法が紹介されています。あまり使っていません。それほど大きくない素数の判定では、エラトステネスの篩で素数表を前計算して済ませることが多いです。ライブラリとして持ってます。

また、試し割り法による素因数分解と、約数列挙もライブラリに入れてあります。便利そうなのですが、問題に合わせて使いこなすのが案外難しいですね。

10. べき乗を高速に計算するアルゴリズム

二分累乗法です。指数法則の賜物。応用として、ダブリングもあります。

ビットごとに先に計算しておくと速い、という発想。かっこいいです。

11. 逆元を高速に計算するアルゴリズム

pow(a,-1,MOD)でOKです。以前、第二引数の-1でハマったことがありましたが、現在のジャッジでは問題ありません。

むしろ逆元を取ってからがスタートです。期待値DPや確率DPが待ってます。

12. 累積和

超重要。DPと同じくらい使用頻度が高いです。いもす法もよく使います。

区間和の計算を高速化できることに喜びを感じるタイプの人間が、競プロにハマっていくのではないかと思います。データ更新がある問題で時間を溶かして、セグ木の存在を知るところまでがセットです。

以上、基本アルゴリズムの振り返りでした。

基本データ構造 3個

基本データ構造については手短に。『上達ガイドライン』で紹介されているデータ構造は、グラフ・木・Union-Findの3つです。

アルゴ式をやりました。すべて埋めてはいませんが、基礎知識を押さえることはできたと思っています。

また、Union-Findはアルゴ式で作ったものをライブラリとして長年使用していました。現在はACL for Pythonを入れているので、Union-Findはdsuを使っています。

セグ木は練習してますが、まだ本番で上手に使えたことがありません。fenwicktreeはやっと使うことができました。今後の課題です。

今後について

  • アルゴは青色までは挑戦したいです。競プロを始めた当初は「だいたい1〜2年で青色にはなれるんじゃね？」と思っていたものです。見積もりが甘かったです。レーティングも厳しくなりましたね。

  • 2025年は「ABCにRatedで12回出て、水色を維持する」ことができれば良しとしたいです。土曜は毎週仕事がありますし、子どももまだ1歳で手がかかりまくりです。無理せず休みましょう。

  • ヒューリスティクは時間を溶かしすぎる予感。止めておきます。

  • 鉄則本か蟻本には手を出すかもしれません。

  • 応用情報は取るかもしれません。

  • 解けない問題に悩みすぎないように。時間を決めて解説を見ましょう。

  • しっかり寝る日は早寝しましょう。睡眠大事。

終わりに

今更ながら、ようやく色変記事をまとめました。自分の理解度を確認するためでしたが、自分と同じようにPythonで競プロをしている方にも、何か役立つものとなっていれば幸いです。ここまで読んでいただき、ありがとうございました。

書籍や他のサービスもありますが、自分の場合は『上達ガイドライン』が一番の拠り所でした。競プロを始めた当初に読んでから、たびたび読み返しては勉強をしてきました。E869120さんには特別な感謝をお伝えしたいです。

AtCoder運営の皆さま、SNSで交流させていただいている競プロ仲間の方々にもたいへん感謝しています。手軽にプログラミングに挑戦できる環境があること、一緒に問題に取り組んでいる人たちがいることで、ここまで自分も歩むことができたと思っています。良い時代ですね。ありがとうございます。

もうひとつ。すばらしい解説の数々に助けられてきました。自分では思いもよらない発想や、簡潔で美しいコーディングに、いつもほれぼれしています。これからも沢山教わっていきたいです。今後もよろしくお願いいたします。

おまけ：子育て×競プロについて

色変記事ですから！
もうすこしだけお付き合いください！！

2023年に第一子が産まれました。子育てをしながら競プロに参加するのは、しばしばとても大変でした。とはいえ、何かに没頭する時間を持つことは、自分のために大切なことだと思い、競プロを続けてきました。

がらっと話は変わりますが、テレビ東京系の赤ちゃん番組『シナぷしゅ』も心の支えでした。せっかくですので番組屈指の名曲『もうけもん』を、ここまで読んでくださったあなたにも聴いてただきたいです。

（視聴してから続きをどうぞ）
（もしくは、後ほどご視聴ください）

赤ちゃんを育てている最中の親だけでなく、幅広い世代に届く歌だと思います。あまり知られていないとしたら、ああ、もったいない！

続いて、ごく個人的な、子育て×競プロの日々もプレイバックしてみます！
それではどうぞ、ご覧ください。

今後も子どもと共に精進してまいります。
最後まで読んでいただき、ありがとうございました。

いいなと思ったら応援しよう！