Atcoderで茶色になったよ

TL;DR 入茶した

この記事が出たということは多分入茶してるはず。執筆時点(2024-05-05 21:29:37)ではまだギリ入茶していないんだけど、入茶する頃と知識量はもう変わらないはずなのでここまで頑張ったことを記しておきたいと思って筆に取りました。文才は雀の涙ですが気になったら読んでくれると嬉しいです。

入茶したらこの記事を出そう！とは思ってるけど、大口たたけないので限定公開でひっそりとTwitterに上げます。

スペック

• 名前:りっとー(莉杜)
• 学歴:大学4年~社会人1年目
  • 偏差値45~50程度の文系大学
  • 旧課程高等学校学習指導要領¹での数学知識はIAのみ、数学IIB未履修
  • 旧課程での物理基礎/化学基礎/生物基礎の記憶は真っ白
  • 情報の授業ってあったっけ
• プログラム歴:
  • mcfunction(マイクラのコマンド²)2020年4月～
  • Python 2021年4月～
  • C 2023年1月～(ただしほぼ忘れた)³

正直2020年~2023年に至るまでの間はmcfunctionしかやっておらず、Pythonは大学の授業から少し出た程度でした。情報系の学部どころか理系でもありません。

経緯

そもそも競プロを始めたのはりっとーの長く仲良くしてる友達がきっかけで、楽しいからやってみない？と言われてホイホイ始めました。言語はPythonで、上のスクショでわかるように基本毎週土曜日開催のAtcoderBuginersContest(ABC)に参加していました。
デビューが丁度今年の1月の最初のコンテストである1月6日のコンテスト(ABC335)で、そこから大体半年いかないくらいで茶色になりました。本当は3月中に茶色行けるといいな、と思っていたけど無理でした。とはいえ、プログラムの知見が増えてる実感も強くて楽しいので特に萎えたりはせずに続けていました。このあたりのことについて、Discordサーバーでりっとーがコンテストの度に記録をしていたので記録を見ながら以降茶色になるまでに知ったことについて書いていきます。

競プロを始める前に既に知っていたこと

スペックの項を見ればわかる通り、私が競プロを始める前でのプログラミング知識は最低限のものでした。

• 順次(上から順に命令が進むこと)
• 四則演算
• if文の条件分岐
• for文/while文での繰り返し
• input()での入力
• print()での出力
• int,str,float程度の基本的なデータ型
• 配列(List,Dict)
• ライブラリが使えるということ

大学で授業をやってから全く何も触れてない、というわけでもなかったので多少は知っていましたが、とはいえA問題を解くくらいの知識だと思います。特にアルゴリズムに関する内容はまったく知りませんでした。

競プロを始めてからの知見

理解したこと

｢Pythonよくわからない｣ので、理解したといっても自分が使う範囲での機能くらいのものです。全部が全部理解したとは到底思えませんが、AtCoderで必要に応じて出来ることを列挙します。

• データ型に関すること
  • set型
  • map関数
  • defaultdict,deque
• アルゴリズムに関すること
  • キューとスタック
  • 二分探索 ※正直ちょっと不安
  • DFS(深さ優先探索)
  • BFS(幅優先探索)
  • 累積和
  • 配列のソート(List.sort())
  • C問題で出る程度の難易度がそう高くないDP(動的計画法)
• その他細かいこと
  • 等差数列の和の公式(知らなくて損した)
  • オーダー記法(計算量の見積もり)
  • 実行言語の選択(PyPy3.10かCpythonか)

正確にはset型は知っていたような気もしなくはないですが、間違いなく競プロで使うために調べなおしていて覚えたと思います。
その他は必要になったから調べて、使って、そのうちに覚えました。あと単純に大きいのは2秒という実行時間制限のなかで何回の計算量まで出来るか、の見積もり。とりあえず2*(10^8)回までの処理回数であれば2秒に収まるんだろうな、とそう考えています。
それからDFSとBFSは結構自信あって、これらが必要になる問題が出たら割と安定して取れるようになりました。キューとスタックについての知識はこれらの付随して必要になって覚えたって感じです。

知ったこと

存在を知ったもの。
よくわからないけどこういうのがあるんだ、へー、くらいのものです。つまり、このあたりの知識は調べていて行き当たったから見覚えはあるけど理解が困難だったか、何らかの理由で必要ではなかったものです。

• データ型
  • SortedList(ソート済み配列)
• アルゴリズム
  • UnionFind
  • しゃくとり法
  • 強連結成分分解
  • DP(動的計画法)
    • ダイクストラ法
  • セグメント木
  • 連結リスト(双方向リスト/単方向リスト)
  • ヒープ木
  • ヒープキュー(優先付きキュー)
  • ソートアルゴリズムの類
  • 平衡二分木

第二要素(ツリーの2段目)は重要度が高いと思っているもの順に並べました。
データ型についてはかなり理解が進んだのか..と言えなくもないかもしれませんが、多分そんなことはないと思います。データ型はその性格上知ってさえいれば適切なタイミングで使うだけっちゃだけなので、理解することが少ないです。したがって｢知って使う｣までが比較的速いということもあり理解できないまま放置したものは少ないかも。
アルゴリズムはもともと全く知らなかったことから学んでいくにつれて芋づる式に出てきました。UnionFindはDPと組み合わせて使ったりするのでいつか必要になるはずですが、現状DFSとBFSを駆使して回避してることが多い気がする...。

茶になるまでに解いた問題

ABC過去問

執筆時点(2024-05-05 23:33:30)で、以下のようになっていました。

主にABC308前後までさかのぼったA~Cの問題を解いていました。灰色の問題は大方解けて、茶色の問題は時間を掛けて半分くらい解けるって感じ。緑の問題は時間かかって解説ACか、おしいところまで書いてコーナーケースに負けるかでほとんど自力ACはしていないと思います。

EDPC

https://atcoder.jp/contests/dp
DPといえばコレ！とよく言われる問題集。
ただこれ難しくて、ABCDEとなぜかHだけ解いていました。

競プロ典型90問

3問だけ。

まとめ

未来に、茶色から緑色になったらこういう記録をまた残したいです。その時に、この記録と突き合わせて分かったものと新しくわからないことに気づいたものなどをまとめられたらいいと思っています。
今のところの目標はひとまず今年中に緑色になりたい。大きくはいつか水色になりたいですね。
ここまで読んでくれてありがとうございました。

文責:りっとー/莉杜

付録

今使っている競プロ用コピペテンプレートを置きます。

import sys,itertools,math
from collections import defaultdict,deque
from sortedcontainers import SortedSet, SortedList, SortedDict
dict=defaultdict
def input(): return (sys.stdin.readline()).rstrip()
# s=list(input())
s=input()
n=int(input())
a=list(map(int,input().split()))
h,w=map(int,input().split())
board=[list(input()) for i in range(h)]
#Lit_to

1. 私の1つ後の代から数学IIICが追加されているなど、課程が変わっています ↩

2. マイクラのコマンドなんてプログラム言語に入るの？と思った方へ、githubではきちんと言語判定が入ります。すごい。→https://github.com/search?q=language%3Amcfunction%20&type=repositories ↩

3. 卒論でC言語書かされました。死ぬほど大変だった。 ↩