JUNのブログ

JUNのブログ

活動記録や技術メモ

AtCoder緑になりました

Algorithm Python

5ヶ月くらい前ですが, 2021年7月31日にAtCoder緑になったのでその振り返り記事を今更ながら書きます.

f:id:JUN_NETWORKS:20211231232320p:plain
レーティング変動

自分のスペック

  • 高校数学は多少やったけど大体忘れてる
  • 42Tokyoでプログラミング勉強してる
  • 数学オリンピックとかとは無縁の人間
  • 言語はPython

やったこと

  • 毎朝典型90の問題を1問解く
  • 新しく知ったアルゴリズムやデータ構造などは手元にメモしてコピペで使えるようにライブラリ化する
  • ABCにはなるべく毎回参加する

毎朝典型90の問題を1問解く

これは書いてある通りで, 毎朝典型90の問題を解きました. ★2から★4の問題までを一日1問ずつやりました. これのおかげでABCで頻出のアルゴリズムや考え方を知ることが出来ました.

自分は競プロの精進をめっちゃやってるような人でも無いので, そもそも手札(選択肢)が無いので, 手札を増やすという意味でも典型90は素晴らしい教材だと思います.

今回緑レートに達成できたのは典型90のおかげだと思います.

新しく知ったアルゴリズムやデータ構造などは手元にメモしてコピペで使えるようにライブラリ化する

これはかなり役に立っています.

UnionFindやセグメント木, BFS, DFS, ダイクストラ など新たに知ったアルゴリズムやデータ構造はある程度汎用的に使えるようにライブラリ化してローカルのマークダウンファイルにアルゴリズムの説明と共に書いています.

ABCにはなるべく毎回参加する

ABCに参加して解けた問題, 解けなかった問題を振り返ると, 「成長したな」と思うこともあれば, 「もっと頑張らねば」と思うこともあり, ちょっと無理してでも毎回出るのはモチベーション的にも大事だと思います.

使ったアルゴリズムやデータ構造

自分の手元にある 競プロメモ.md の目次をコピペします.

- 競プロで使えるコード, テクニック集
    - 計算量
        - Python の処理速度の目安
        - リスト
        - collections.deque
        - set
        - 辞書
    - 設定
        - 入力高速化
        - 再帰呼び出し上限
    - 注意すべき点
        - float('inf') の生成は整数リテラルとは違い生成に時間がかかる
    - プロファイラ
    - データ構造
        - デキュー
        - 辞書型
            - defaultdict
            - Counter
        - UnionFind
        - Priority Queue
            - 使い方
            - 最大値の取り出し
        - セグメント木 (RMQ)
            - 遅延評価セグメント木 (RUQ)
            - 遅延評価セグメント木 (RAQ)
    - グラフ
        - 用語
        - グラフの表しかた
            - 隣接リスト (Adjacency list)
            - 隣接行列 (Adjacency matrix)
        - 探索
            - 幅優先探索 (BFS)
                - 応用
                    - 01BFS
            - 深さ優先探索 (DFS)
        - 最短経路探索 (重み付きグラフ)
            - ダイクストラ法
                - 特徴
                - 実装
            - ワーシャルフロイド法
                - 特徴
                - 実装
            - ベルマンフォード法
                - 特徴
                - アルゴリズム
            - ジョンソン法
        - 強連結成分分解 (SCC)
        - 辺に対する周遊性
            - 用語
            - オイラーグラフの判定
            - オイラー回路の求め方
        - 巡回セールスマン問題 (TSP)
        - 木の直径
        - 最小全域木
            - クラスカルのアルゴリズム
            - プリムのアルゴリズム
        - 最近共通祖先(LCA)
        - 木の表現方法
            - 左子右兄弟表現
            - 二分木
    - ソート
        - 複数のキーでソート
        - 複数のキー(1 つはリバース)
        - 比較関数を基にソート
        - トポロジカルソート
    - 探索
        - 二分探索
            - ライブラリを使う場合
        - bit 全探索
    - 文字
        - 全アルファベットのリスト
    - 数学
        - 素数で割った余りを求めよ
            - 割り算の余り
        - 倍数の性質
        - 総和
        - 順列・組み合わせ
        - 繰り返し二乗法(二分累乗法) (a^b % c を高速に求める)
        - 累積和
        - いもす法 (多次元対応累積和的なやつ)
        - 2 つの数の最大公約数 (GCD)
        - 最小公倍数 (LCM)
        - 素数判定
        - 素数列挙
        - 素因数分解
        - 約数取得
        - 平方数の判定

こんなに無くても緑コーダーになれるかもしれないですが, ある程度典型的な使い方を知っておくだけでもコンテスト中の選択肢が増えるので良いと思います.

その他

言語はPythonを使っています. 最初はC++とかを使おうかとも思ったのですが, 自分が最も慣れている言語がPythonだったのでPythonを使っています. 勿論提出時はPyPy3です.

完走した感想

緑レート達成した時に記事書けばよかったなーとおもってたんですけど, 友人と喋っていたら, 「別に今から書いてもよくね?」と言われ, 確かに〜 って感じだったので書きました.

AtCoder始めて3年経っての緑レートってことでとても嬉しいです. (まぁ1年単位で空白の期間があるわけですが)

自分は競プロ200問解くとか,C問題埋めとかは特にせずに緑コーダーになったわけですが, これは完全に典型90のおかげだと思います.

余談ですが, この記事を2021年中に公開しようと思って書いていたらいつの間にか日付が変わって2022年になっていました. あけましておめでとうございます.

ではでは〜〜👋👋