【WebエンジニアのAtcoder記】入緑しました！

先日行われたABC215にて，ついに入緑しました！！
かれこれ，1年以上かかった結構長い道のりになったので，これまでの勉強過程と現時点の自身のスペック等をまとめます．

自己紹介

• Webエンジニア2年目
  • Web系の企業で開発運用業務に従事
• 学部は機械系,研究室配属(学部4年時)以降と修士の2年間では情報検索，NLPの研究
  • 修士在学中，JASSO奨学金免除達成(半額)
  • 学部が情報系のバックグラウンドではない※1
  • ※1:そもそも思い出すと大学2年に進級するとき主専攻振り分けがあるのですが，情報系を選ばなかったのははじめの授業でC言語で周りが優秀で自分にはプログラミングの適性がないと諦めていたのが大きいなと...（周りに回って結局今はエンジニアをしているわけですが)
• 基本情報技術者試験取得(2021/03)
• そもそも学部時代に情報系を専攻していたわけではなく，機械系学部から情報系修士，現職という経歴で一般的な情報学部卒で習うべき授業を体系的に学んでいない事によるコンピューターサイエンス(CS)に関する知識の引き出しの少なさというのは修士のときに感じていました．

Atcoderで使用している言語

• Java: 2021/01 以前
• Python 3.8.1 (PyPy) 2021/01 以降

そもそもなぜAtcoderを始めたか？

• 研究室の後輩や会社の同期（いずれも優秀）が学生時代にやっていたのがきっかけです．(そしてみんな緑コーダー)
  • Atcoder緑レベルの実力があれば，エンジニアとしてやっていく上である程度の実装力を担保できると感じました．
• アルゴリズムの基礎力の重要性を意識しました，
  • 上述にもあるとおりですが，修士を通して研究する間にCSの基礎力の重要性を痛感しました.CSの基礎知識的な部分は，目に見えないところでその人の作業効率を上げているということに気づきました．(あるタスクに対してそれを解決するためのイメージの道筋が立つ速度が変わってくる．)　エンジニアの最初のキャリア1,2年は多少回り道しても，基礎を習得するための時間として確保すべきだと思い基礎的なアルゴリズムの実装力を高めるためにAtcoderを始めました．
• Javaの言語に慣れるため
  • 仕事で使う言語がJavaであったため，Javaにいち早く慣れるためはじめの頃はJavaでコンテストに参加していました．

なぜ社会人でAtcoderを続けようと思ったか？

社会人だと単純に比較して学部生より，時間を取りにくいかもしれません.それでも続けていた理由は

• 最初はJavaに慣れるまでにしようと思っていた．
  • 問題を解いていくうちに,やればやるほどハマっていき土日夜のABC参加が習慣的なイベントになっていった．
• やってはいけない(計算量やメモリ使用量を考慮しない)実装をしないようになれる,他にも大量のリクエストが発生した場合の負荷やデータ量を意識してコーディングをするようになれるのでは?と思ったから．
  • 問題を解くにつれ,結果的に業務においてもコーディングの速度や正確性の意味で実力につながるのではと思ったため．
  • (大量データの本番移行作業が伴うときに，書いたコードが問題を起こさないか，少し意識してコーディングしました．(なにか特別なアルゴリズムを使ったわけではありません))

使用した学習コンテンツ

基本的にAtcoderの過去問を解いていました．精進したい時期ごとに主として使っていた情報源が少し違います．
これらのサイトを使って解く問題を選んでいました．期間はそれをメインの題材として使っていたというだけで，その期間以外には使っていないということではありません．

Atcoder Problemsで過去問を解く【2020/10 ~ 2021/02】

• (言わずもがな?)過去問を一覧で問題を見たいときに便利でした．
• 直近の過去問のC,Dレベルの問題を順に解いていきました．
• 正直このときは成績がほしいというよりかは，Javaに慣れたいなというモチベーションが高かったです(なので，言語選択はJavaで参加していました．）
• 途中，基本情報の試験対策を優先していた時期もあったので，そんな精進量は多くないと思います．
• 2021年1月頃，ハイスコアを出すため自分が慣れている&ライブラリが充実している&シンプルに記述可能なPythonの方が圧倒的に効率がよいと思ったので，完全にPythonにシフトしました．

入緑した日の精進量

参考:Atcoder Performances

Atcoder ProblemsのTraining機能　【2020/03 ~ 2021/06】

• あまり注目されている機能ではない(?)ですが，Atcoder Problemsには,Trainingの機能があります．個人的にはとても活用させていただきました.
• Easy,Medium,Hardのレベルがそれぞれ灰,茶,緑の問題を中心に100問ずつで構成されています．問題のDifficultyごとにソートされているので，徐々に難易度が上がっていくことがわかります．各問題を解けるユーザーのレベル感をつかみやすかったかなと思うと同時に，自分のレベルにあった問題を探すのにもちょうど良かったように思います．
• 茶色は100問解きました．緑も現時点で約半分(55問)解いています．灰色はあまり解いていません.
• これを解いている最中に,競プロ典型90をtwitter上でよく見かけるようになり，そちらを優先的に解いていくようになりました.
• 問題を解くとき全般に言えることですが，僕は解説ACも多い方だと思います．完全に自力で問題を解くことで自分の力になるとは思いますが，ずっと考え込んでいても仕方ない部分はあるという考えのもと，ある程度(1,2hのときもあれば，１日置くこともある)時間が経過したら，解説を見て次に進むということもしていました．

競プロ典型90 【2021/06 ~ 2021/08】

• E869120さんが企画されていた，Atcoderで頻出の問題を網羅した問題セットとなっています．
• 各問題におおよそ一枚のスライドでまとめられた解説スライドが作成されており，要点がわかりやすくまとまっています.
• 網羅されている問題も非常に考えられており，漏れと重複なく，作り込まれているコンテンツだと思います．(企画の期間中からもっと参加してもよかったなと今になっては思います)
• ☆4以下を優先的に解きました．特に☆4,☆5あたりの問題は初見で解けないことが多かったです．これを機に勉強して次類題に遭遇したときにACしたいという気持ちでやっていました．
• 最近は,競プロ典型90の類題が出題されるとその問題の正答率が上がる傾向にあると思います.

番外編: Leetcode 【2020/04 ~ 2020/07】

• Easy~Mediumレベルの問題を解きました入出力の方法が異なるのと自由にサンプルケースを実行できる点がAtcoderと異なりますね．木系の問題がAtcoderに比べると多い印象です．(逆にAtcoderは，高校数学ⅠAの問題が問われることが多い印象)

現時点で習得済みのアルゴリズム

アルゴリズム列挙の際に参考にさせていただきました． 【AtCoder】普通の人である私が緑になるまでにしたこと
各アルゴリズムを使った直近の問題も載せておきます．(必ずしも想定解でない問題も含まれています．)

アルゴリズム	理解度(◎,○,△,×)	コンテスト中に解けたか？(Sample)
Bit全探索	◎	ABC197-C
二分探索	○
一次元累積和	○
二次元累積和	△
約数列挙	◎	ABC215-D
GCD・LCM	◎	ABC215-D
貪欲法	○
幅優先探索(BFS)	◎	ABC204-C
深さ優先探索(DFS)	○
しゃくとり法	○
動的計画法(DP)(簡単め)	○
動的計画法(DP)(中級以上)	×
bitDP，区間DP	×
最長増加部分列(LIS)	△
優先度付きキュー	◎	ABC212-D
ダイクストラ	◎	ABC211-D
ワーシャルフロイド	×
Union-Find	○
座標圧縮	○

◎はコンテスト中に解けたアルゴリズムで，○は実装したことあるが,コンテスト中には解いたことがないアルゴリズムです．
累積和+二分探索といった組み合わせが必要な問題は，今のレベルだと解けないかなと思います．
中~難のアルゴリズムを余裕を持って使いこなせている状態というよりかは,易~中のアルゴリズムを正確にそこそこのスピードで解くことができるレベルであると自負しています.ただ得意不得意な問題は個人差がありそうです.(僕は累積和ちょっとニガテ...な一方，幅優先探索，ダイクストラ,bit全探索あたりは比較的解ける)

コピペ用ライブラリ

コンテスト中，util関数を使えるときは，コピペしちゃってます.

最大公約数

def gcd (a,b):
    """a,b の最大公約数, gcd
    Args:
        a (int): num
        b (int): num
    Returns:
        int : a,bの最大公約数
    """
    while b:
        a, b = b, a % b
    return a

最小公倍数

def lcm(a, b):
    """a,bの最小公倍数
    Args:
        a (int): num
        b (int): num
    Returns:
        int : a,bの最小公倍数
    """
    return a * b // gcd (a, b)

約数列挙

def divisor(n): 
    """n の約数列挙
    Args:
        n (int): num
    Returns:
        約数のリスト
    """
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

素因数分解

def prime_decomposition(n):
    """素因数分解
    Args:
        n (int): num
    Returns:
        [list]: nを素因数分解したリストを返す
    """
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

素数判定

def is_prime(n):
    """素数判定
    Args:
        n ([int]): num
    Returns:
        [boolean]: 素数の場合: True, 素数でない場合: False
    """
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

ncr計算

from operator import mul
from functools import reduce
def ncr(n,r):
    """ncr 計算 (import文 も必要)

    Args:
        n ([int]]): 
        r ([int]): 

    Returns:
        [int]: [description]
    """
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

階乗計算

def factorial(n):
    """階乗計算 n!
    Args:
        n ([int]]): 

    Returns:
        [int]: [ans]
    """
    mod = pow(10,9)+7
    ans = 1
    for i in range(1,n+1):
        ans *= i
        ans %= mod
    return ans 

他にはUnion-Find も自作のライブラリを用意しています．

勉強方法など

• 自分が余裕で解ける問題ばかりやっても意味がないは真かと思います．多少は負荷をかけたほうがいいかなと.

時間や曜日によっておおよそ以下の問題のグループを目安に解いていました．

問題グループ

• グループ1 :余力を持って解ける問題(A問題,B問題に相当)(自分の予想正答率75%以上の問題)
• グループ2 :解けるか微妙な問題(自分の予想正答率25%~75%程度の問題)
• グループ3 :もしかしたら思いつくかもしれないけど現時点の実力では解くことが難しい問題(自分の予想正答率25%以下の問題)

いつ解くの？

• あまり気分が乗らないとき：グループ１
• 平日の朝(業務前):グループ２(1h以内に終わればよし！終わらなくても後で途中から再開)
• 休日など時間が取れるとき:グループ３の問題で必要となるアルゴリズムの習得，グループ2の問題を多めに消化する.

といったやり方で進めていました.

競プロのモチベーション維持の方法

• やりたくない日はやらないほうがいい．(疲れてる日もある)
• 自分より少し上くらいの人twitterアカウントをフォロー&Atcoderのお気に入り追加する．
  • コンテスト中や振り返りをするときにどのくらいのレベル感を目指せばいいかがわかる．
• レート上昇の傾きが大きい人は(いい意味で)気にしない.
  • 界隈には，圧倒的傾斜角でレートを上げる人もいますが，いい意味であまり気にしないようにしていました．自分は自分です．
• 変に「1日1問!」といったSteaksを伸ばすことを意識しないほうがいいかなと思います．
  • その目標を重視する上，簡単な問題で妥協するのは，あまり良くないという考え
• わからない問題があると長い時間夜遅くまで考えてしまうタイプではあります．しかし,集中ができていないときや頭の回転が悪いときはいっそ早く寝て次の日もう一度考えてみると案外解けるみたいなことがよくありました．睡眠大事.

最近のABCの傾向

• 日々精進しないとレートが下がりそうな感覚がある．(早解きしないとレートが下がりそうという恐怖感との戦い)
• 早解く正確に解く力(コーディング力)，典型アルゴリズム力の2軸をそれぞれ鍛えていくイメージ
• ARCには出たほうがいいか？
  • 参加したとしてもレートを上がりにくいかなと感じました．レベル相応の問題が解けても，あまり上がらなかったように感じました．参加するとその分復習すべきスタックされている問題に着手できず，更にスタックに問題が溜まってしまいます．(ほぼ)毎週開催されているABCに参加するだけでほぼ十分のように感じました．

WebエンジニアにAtcoderの実力は必要か？

• ひとえにエンジニアと言っても様々だと思いますし，その人の目的によって変わるのではないかと思います．ただ業務上"直接"役に立つことは少ないかなとは感じます． 個人的にキャリアはじめの1,2年は，エンジニアとしての基礎力をつけたいという思いがあったのと，単純に面白いから趣味としてやっていました．
• はっきりいうと，アルゴリズムの理解や実装力がなくてもできる仕事は多いと思います．そもそもWeb開発に求められる技術とAtcoderで得られるスキルの方向性は違いますよね． ただ一方で，アルゴリズムをきちんと理解している人が書くコードの質はそうでない人のコードと比べて多少はコードの質に差が出る部分はあるのではないかというのが僕の見解です．特にPythonのようなライブラリも充実していて自由に記述できる言語だといかにも書きようがあるので. 周りを見渡しても程度の差こそあれ,アルゴリズムをちゃんと理解している(情報学部での勉強をしっかりやってきた)人はかねがね，エンジニアとしても優秀な印象があります．(そうでない人が優秀でないということでは全くありません)
• Webエンジニアとして，他人のコードを読んで，処理内容を理解する作業は必須です． Atcoderをやる中で，他人のコードをたくさん読む機会も増えます(それもアルゴリズムの記述なので理解に時間がかかることも多いです)．そういった鍛錬を繰り返す中で,コードの読解速度は上がったように感じます．(このスキルはもちろんAtcoderでなくともその力を身につけることができます)

参考にしていた入緑記事

• 【AtCoder】普通の人である私が緑になるまでにしたこと
• 僕がAtCoder緑になるために意識したこと
• AtCoderでついに入緑しました！！！

最後に

• あくまで個人的な感想も多く含みます.
• 色々と書きましたが，今後(来週?w)，茶落ちする可能性は十分考えられます．結局はここが完全ゴールではないですからね．
• ただ非情報学部出身でも緑コーダーになれたので，実装力にある程度の自信をつけることができました!!自分の目標は達成です！
• 主催者と競プロコミュニティに感謝します.
• 継続は力なり！