【AtCoder】入水しました！！！！！！！！！！！！！！

こんにちは、yesです。
今回はABC430で入水したので入水記事を書いていきます！！！

スペック

• 大学1年生(情報系)
• 中受経験があるので算数は得意
• 微積が本当に理解できない
• プログラミングは元々if/for文は知ってる程度(アルゴリズムや計算量の知識は皆無)
• タイピングが下手くそ。人差し指タイピングの亜種みたいなことをしている
• 音ゲーが上手い

入茶まで

せっかくなので初めから振り返って行こうと思います。

始めたきっかけは知り合いの音ゲーマーから勧められたからです。当時プログラミング経験は一応ありましたが、競プロは難しそうと思い触れられていませんでした。でも、当時通信制高校に通っていたので暇すぎるしやるかーという気分になり色々触ってみたところ、典型90問のうち1つが解けました。今思うとなんでこいつは典型90問から解きに行っているんだ？という感じですが、これが解けるなら実はやれそうと思い始めてみました。勧めてくれてありがとう。

入茶に関してはあまり語れることがありません。それもそのはず、精進をほぼしていなかったからです。
APG4bすらあまりやっていなかったので解説でmapが出た時「そんなものがあるの？？？」と普通に驚愕しました。
スクショは残っていないですが、多分茶↑Diffは1問も解けていません。DFSやBFS自体は勉強しましたが、こんなにも精進をサボっていたのに入茶出来たのは早解きが比較的得意だったからだと思います。
早く解けることは良いことですが、このままだと緑色は無理だなぁという実感はありました。

入緑まで

このままでは緑色になれないなぁと思ったので、とりあえず毎日問題を解くことにしました。
しかし、これだと灰Diffに逃げる予感がしたので毎日1問は茶Diffを解くというのを個人的な目標として頑張ることにしました。

毎日精進する、つまりCurrent Streakを伸ばすことは色々な意見があると思いますが、個人的には問題を解く機会が増えるのでおすすめです。

他にやったことを下に書いていきます。

Novisteps 2Q(〜1Q)埋め

当時TwitterのTLを徘徊していたら知りました。
毎日茶Diffを解くにあたって色々問題を見ていったのですが、やはり過去のABCの茶DiffとARC、AGCの茶Diffでは難易度差が大きすぎるなと感じました。
しかし、Novistepsでは人力でグレード分けされているためこのようなことが比較的無くなり、当時1番効果があるように感じました。

水色になった今でもかなりお世話になっています。是非やりましょう

鉄則本をやる

存在自体は知っていましたが、灰色時代に蟻本を買って挫折した経験がありあまり手が出せていませんでした。しかし大学の図書館に鉄則本があると分かったのでやってみることにしました。
めちゃくちゃ分かりやすかったです。借りてよかった
当時腐っても茶色コーダーだったので、ある程度の部分は知っているということもありNovistepsの2Q相当から埋めていました。
今は比較的得意なbitDPも鉄則本で理解できました。(この問題は解けなかったけどな！ガハハ)
今やっても収穫が多そうなのでまた借りるかもしれません。

入水まで

メインコンテンツです。

入緑したのは良いですが、当時水パフォも取ったことがないので絶望していました。とりあえず、緑色に行ったので毎日緑Diff1ACを目標にしていましたが…いつの間にか毎日水Diff1ACを目指すようになっていました(なんで？)
そんなこんなで水Diffをいっぱい解いていたのですが、並行してNovisteps 1Qも進めていました。1Qは2Qとレベルが違いすぎて当時はめちゃくちゃ絶望していました。鬼です。
そうしていたら、事件が起きました。

ABC414でまさかの早解きで水パフォ。しかも、E問題は方針は合っていて実装ミスという形でした。当時は悔しかったですが、今思うとこれを方針まで行き着いたのはすごいと思います。
そしてABC415で、

まさかの人生初のE問題が解けて1400パフォが出ました。E問題は典型よりのDPとはいえ、当時精進の成果が出て嬉しかったです。
この辺りで上振れすぎている実感はあったので、流石に落ちるやろ〜と思ったら

早解きでまた1400パフォが出ました。なんで？？？？
これにより、遠いと思ってた水色も残り半分まで来てしましました。当時の俺もあまりの衝撃にツイートしてます。

そしてここで始めたタイミングが同じ仲間の1人が入水しました。すげーと思いつつ、いつかこうなりたいなと思い頑張って精進を続けました。
この辺りからレートの伸びが鈍化していきます。と言っても、6回のコンテストで+200しているのがおかしいだけであってむしろ伸びてるだけありがたいのですが、当時は水色遠いなぁと思っていました。
ただ思うだけでも仕方がないので、Novisteps 1Dもちょくちょく触るようになりました。1Dはレベチです。あほ。
ただ、この地獄のメカニカルトレーニングにより実力は大きく伸びたと思います。しかしレートは伸びないことも多くなってきました。もうこの辺りは祈ってました。
最後の方は青Diff、なんなら黄Diffまで手を出しつつありました。ここら辺は網羅的にやるというより、得意分野を伸ばす感じです。

触れていなかったことも色々書いてみます。

ABCに毎回出る(Ratedで)

当たり前ではありますが、ABCに出ないとレートは上がりません。upsolveで知識が増えることも多いので基本的には出🉐です。

典型90問・EDPCを埋める

精進の一環でやっていました。
そんなこと知らねぇよ〜と何度もなりましたが、勉強することによって他の水Diffが解けるようになったので効果はめちゃくちゃ大きいです。まだまだ埋め切ってないので休み期間に自分の実力の範囲で埋め切りたいです。

精進木を作る

精進木とは、Twitterでリプに解いた問題をぶら下げていく活動です。(間違っていたらすみません)
僕の場合1問約1リプを心がけていましたが、いつの間にか11/1時点で395リプぶら下がっている状態になっていました。

精進木を始めたのが7/4なのでざっくり毎日3問解いている計算になります。1問だけの日もあれば10問くらい解く日もありましたが、精進木を育てるぞ！というマインドになったから出来たという説もあります。

マクロ、ライブラリの整備

僕はタイピングが遅かったのでGithub Copilotに頼っていましたが、10/3のルール変更で禁止されてしまいました。もちろんCopilotが禁止になる前も整備していましたが、禁止になったことによりより一層整備する必要性が上がったと思います。

習得したアルゴリズム諸々

どうせならこういうのも書いていこうかなと思います。思い入れがあるものを書いているため、漏れは大いにあるので参考程度にどうぞ。

使える

• 二分探索
  最初はバグらせがちでしたが、関数を事前に用意するパワープレイで解決しました。
• BFS/DFS
  DFSは下のようにmain関数の中に書くのがおすすめです。

#include <bits/stdc++.h>
using namespace std;

#define foreach(i, n) for (auto& i : (n))

using graph = vector<vector<int>>;

int main() {
	int n;
    cin >> n;
    graph g(n);
    /* いろいろ */
    auto dfs = [&](auto&& self, int v, int p) -> void {
    	foreach(nv, g[v]) {
        	if (nv == p) continue;
        	self(self, nv, v);
        }
    }
    dfs(dfs, 0, -1);
}

• ダイクストラ法
  最初知った時すげー！ってなりました。

• ワーシャルフロイド法
  最初知った時、かつっぱさんの方法を先に知ったので添字バグで死んだことはないです。

• DP(動的計画法)
  種類がめちゃくちゃ多いですが、ゲーム系と区間DP以外はそれなりに解けるようになってきました。ゲームわからん…

• Rolling Hash
  入水の決め手となりました。実装もそんなに難しくないので身につけておくと便利です。

実装は出来ないが使える

• Union-Find

• SCC(強連結成分分解)

• セグメント木/遅延セグメント木

• mod関連の計算
  この辺りはAtCoder Library (ACL)に頼り切っています。セグメント木は難しいですが、使えるだけで解ける問題の範囲が一気に広がるので使えて損はないと思います。

• 重み付きUnion-Find (ポテンシャル付きUnion-Find)
  けんちょんさんの記事が参考になります。僕はACLのdsuのように使えるよう改造しています。あまり使えたことはないです…。

• 二次元累積和
  自分で書けるようになる自信が無かったのでChatGPTに整備してもらいました。(11/2時点ではコンテスト開始前にあらかじめ生成AIを用いて作成しておいたコード等の使用は許容されます。)

使えないもの

• Fenwick tree(BIT)
  解説でこの用語が出る問題は大体セグメント木で解けるので後回しにしていました…

• Trie木
  何をやっているのか全然分かりません。たすけて

• 三分探索
  直近の問題で出たので学ぼうと思いつつ放置しています

• その他諸々

AtCoderをやって良かったこと

AtCoderに結構な時間費やしたので、良かったなぁと思うことを一部書きます

自分にある程度自信がついた

元々音ゲーはかなり上手かったのですが、やはり現実社会には活かしづらいのもありその他の面を見すぎて自己肯定感が低すぎてぐちゃぐちゃになってました。
しかし、AtCoderは現実社会に活かしやすい部類なのもあり、「ちゃんと将来に向かってる感」があって比較的自信がつきました。

物事の考え方が上手くなった

これは意外と思われそうなのですが、AtCoderの問題を解く時に色々考えた結果、したいことから逆算して必要なものを考えることが多少なりとも上手くなった気がします。
こういうのって鍛えられるんだなぁと思いました。

基本情報の科目Bが余裕になった

元々基本情報のためにAtCoderを始めたわけではありませんが、AtCoderをやっていたので科目Bの擬似言語が余裕で出来るようになりました。
応用情報は問題文長すぎて別ゲーな感じがしますが…。

今後の目標とか

元々大学4年までに水色に行く予定だったので、随分早く終わったな〜と思います。
しかし、だからと言って青色は遠すぎるので当面の間は水色維持とさせていただきます。
ちゃんとグラフ系の問題を解けるようにしたいですし、「水色コーダーさん　その問題、D問題ですよ？」と煽られないようにしないといけません。大変ですね…

AtCoder Problemsの諸々を貼るコーナー

最後に

拙い文章でしたが、ここまでのご閲覧、本当にありがとうございました！！！！！！！！！！！！！！