AtCoder青になったので水色から青までの一年半とついでに今まで書きそびれた黒から水までも全部書く

自己紹介

DivineJKです。地元の友達からは苗字で呼ばれています。

10月2日に、AtCoder青になりました。数学が強いタイプです。

音楽は主に洋楽メタルが好きです。最近はK-POPも聴き始めました。

あとふわふわツインテールとか好きです。なんというか、ツインテールに限らずハーフアップとかポニーテールとかとりあえずなんでも好きです。嘘かもしれません。

ゆめロリとか甘ロリとかも好きです。というか、原宿系の趣味があります。その影響でメイクを勉強中です。

あと、たまにイラストを描いたりしてます。最近は女子の制服を描くのとかマイブームです。正直イラストの方の精進もしたいんですよね。

このご時世で最近はなかなかできないのですが、地下アイドルのヲタをやったりもしてます。推しのアイドルは、Twitter（@realDivineJK）できいてくれたら教えます。

趣味の話はさておき、軽く自分の経歴を紹介します。

大学では物理学を専攻し、もう一回遊んでから卒業しました。ママ、パパ、ごめんな。まじで朝起きれないし電車乗ると吐き気する。

で、そのもう一回遊ぶときに、単位数確保のためにフラッと別の学部のプログラミングの授業でPythonに触れたら、見事にハマってしまいました。ハマりすぎてBCH公式の各項の係数計算や、スピン合成の固有状態の計算なんかも自主的に組んでました。そんなわけでPythonで遊びながらTwitterサーフィンしていると、顔の前に手を置いて何かを考えているアイコンのとある社長のツイートで、競技プログラミングやAtCoderの存在を知りました。

僕は今まで数学オリンピックとか情報オリンピックとかに無縁の人生だったので、競技学問ってちょっとハードルが高いなーとか、凡人の自分には無関係かなーと思っていました。僕は科学オリンピックや開発や研究ですごい成果をあげたとか、中学高校がとんでもない進学校だったとかそういうわけでもなかったので。

しかし、実際にAtCoderの問題を開いてみると、意外に解ける！となって、それからどんどん問題を解く楽しみを味わっていきました。多分、僕の探していたものはこれだったんじゃないか、僕の適正はここなんじゃないかとか思えてきて、もう少し早く出会いたかったなって思いました。

とりあえず自己紹介はこれで以上です。他何か聞きたいことがあったら僕のTwitter（@realDivineJK）のリプとかDMにでも質問してきてください。答えたくない質問はスルーしますけど。

びふぉーあふたー

これが、

こう。

ジャスト+400！

およそ1年半かかりました。Ratedコンテスト初参加からなんと2年1ヶ月（！）

水になるまでのハイライト

1997/08/27 誕生

生まれました。

やったこと：

• 生まれる

2019/09/01 黒から灰になる（ABC139）

成長して、その過程で世の中の色々な理不尽や矛盾と闘いながら、そんな中でも家族や友達と笑い合える束の間の幸せを噛み締める日々を過ごしているときにAtCoderに出会い、黒から灰になりました。

やったこと：

• AtCoderを知ってコンテストに出る

2019/11/04 灰から茶になる（AGC040）

AGCに参加したら茶色になりました。この当時は灰色もAGC ratedだったのだ。

やったこと：

• コンテストに出る

2020/01/11 茶から緑になる（第6回ドワンゴからの挑戦状 予選）

スマホコーディングで青Perfとって緑！w 8級から7級すっ飛ばして6級！w

バイト帰りにスマホから参加。A問題でRE出たときは初めての冷えを覚悟しました。スマホの充電残り7%でB問題が通ったときは街中でスキップしてました。AtCoderはじめた当初は緑ぐらいを目指して終わろうかなと思ったのですが、競プロの知識は結構面白かったので続けることにしました。

やったこと：

• mod逆元

2020/03/28 緑から水になる（ABC160）

3ヶ月で緑から水になりました。あとワニが死にました。

2020年になってから人が変わったように水Perfがとれるようになりました。ちなみに初水Perfより初青Perfのほうが先という謎の現象が起こっています。

やったこと：

• Union-Find
• BFS
• FFT
• 形式的冪級数を少し

水から青のふりかえり

ABC161〜ABC168（2020/04/04〜2020/05/17）

Rating 1203 -> 1311

水色になってもだいたい緑のときと同じようなPerf（1300くらい）をとっていて、これ1300になったらどうしようとか思いながらコンテストに参加していたら、いつのまにか1300台にのってました。

なんというか、このときは自分が青になる世界が想像できてなかったです。きっとレートは上がるけど青にはなれないだろうな、みたいな。でも青にはなりたかったです。

AGC044〜ABC171（2020/05/23〜2020/06/21）

Rating 1311 -> 1245

AGC044で0完太陽をとってしまい、およそ半年ぶりの茶Perfで激冷えしました。それ以来、NoSub戦略というものを選択肢にいれつつコンテストに参加していました。

また、ABC169で全完のチャンスだったのですが、自分の実装力の無さというか、実力不足で結局冷えになってしまったのが悔しかったです。

ABC172〜AGC048（2020/06/27〜2020/10/18）

Rating 1245 -> 1349

ABC172で初めてtourist出しというものをやってみました。これが大成功（Perf 1988）して以来、先のNoSub戦略と合わせて、企業コン以外のABCは「Eが解けたら出す、解けなかったら出さない」と決めてコンテストに参加するようになりました。

ARC106〜ABC186（2020/10/24〜2020/12/19）

Rating 1349 -> 1494

ARCで2回黄Perfとって一気にHighest1500台になりました（は？）。ただ、ABC181で緑diffのEが通せなくて、ここで自分の実装力の無さやあいまいさと直面することになりました。

ABC186以降はNoSubを繰り返すなどして空白の3ヶ月になりました。

ARC112〜ABC199（2021/02/13〜2021/04/24）

Rating 1494 -> 1477

復活します。もうこの時期からNoSub戦略に飽き出したというか、レートを落とす覚悟で行くか、と考え出しました。

ここから3回青以上のPerfが取れて、Highestが1576になったときは青見えた！やばい！青見えた！と思いました。

しかし、ABC198とABC199で激冷えして戦意喪失しました。このときは、もう自分は競技者としての適性がないんじゃないかとも思えて、引退も考えました。また3ヶ月近くコンテスト不参加の日々が続きました。

ちなみに、3月に大学を卒業して、4月頭からプログラミング系のアルバイトを始めました。

ABC212〜ABC221（2021/07/31〜2021/10/02）

Rating 1477 -> 1603

やっぱり問題が解けない、解けない問題が多いのは嫌だったので、人々の影響もあってABCバチャをやることにしました。

8問ABCになるので出てみるか、という軽い気持ちで出たらABCDGの5完で激温まりました。嬉しかったので、またコンテスト参加をはじめることにしました。

レートが1579になったとき、体調不良で参加できなかったABC219のバチャに参加したら、

本番なら黄Perfの成績でした。せつない。

このときから僕は「実質青」を名乗っていました。

そして、レート1563で迎えたABC221。

僕はこの回で青になれるとは思ってなくて、まああったまったらいいかな、青Perf取れたらいいな、ぐらいの気持ちでした。

そしたら、ABCDまで順調に進み、E問題の解法もすぐに浮かびました。BITに数を入れる処理でmodとり忘れてTLEでペナしたけど、ペナ含め47分でEが解けたのはわりと順調だなと思い、順位表を見たら...。

...ええ、250位とかになってました。

これ、このまま行けば黄Perf出るじゃないですか。AtCoder参加して初めてペナルティの5分に対する後悔を覚えました。

というか、ペナ消化した後の順位の下がり方がえらい鈍くて、え、これワンあるのでは？青コーダー誕生ちゃいますか？そう思い、ac-predictorを見に行ったら、1563->の矢印の先に青い数字が表示されていて、僕は落ち着きを失いました。

もうそのあとはPerfが1888以下にならないことを祈るのみ。でもやっぱり落ち着かないので、FとかHを解いて順位を解いて順位を少しでも上げようと頑張りました。結局解けずに終わったんですが。

コンテスト終了後も順位表は見れませんでした。Perfが1888になる順位が大体わかっていたので。必死にAnthrax聴いて気を紛らわせていました。

で、Twitterの人々がコンテスト結果をツイートした瞬間に自分のプロフィール画面を観にいきました。自分の名前が濃い青になってて思わず手を叩いてコロンビアになってました。

レートが1579で元Highestのときですら青になれる実感が湧かなかったので、まさか青が実現できるなんて驚きと嬉しさが隠し切れないですね。

あと心の余裕がなかったので画像が準備できなくてすみません。

水から青になるまでにやったこと

過去問解くやつ

AGC044からABC199までは停滞期と呼んでいいかもしれません。そして停滞期の時期は、コンテストをレート上げのためのものだと思っていたかもしれません。レートが上がれば嬉しいし、レートが下がったらカス以外の感想がなかったです。

しかしあるとき、「僕のヒーローアカデミア」1巻を読みました。デクくんが雄英合格に向けて積み上げを繰り返してるシーンは親指を立てながら涙なしにはみられませんでした。

そして、このシーンで僕はあることを思いました。

「レートは一時的に上下するかもしれないけど、解いた問題数は下がることはない。そして、解いた問題数が多いほどレートが上がる確率が高くなるから、過去問を積み上げない手はない！」

というわけで、一旦レートはおいといて、解いた問題数を積み上げていくことにしました。

特に、ABCではバンバン解説を開けて知らない知識を勉強していこうという気持ちで臨みました。僕は今まで特別な天才エピソードもなく、本当にただの凡人なので、解法が思いつくのを待つよりは解説を読んで理解するほうが効率がいいかなーとも思ったのです。

なんというか、パズルを解く楽しさより知識を得る喜びを求めたというか。知らない知識に触れたり知識を積み上げていく日々は刺激に溢れて充実してました。

そうして知識積み上げの日々を過ごすと、レートが落ちてもまた上げればいいしな、みたいに思えて冷えに対する抵抗が減ったと思います。

そういう充実した日々を過ごすと、自然と人は笑顔が増えていくものです。

笑顔で明るく、穏やかな気持ちで過ごしている人とは関わりたいじゃないですか。そんなわけで、ゆったりとしたそんな気持ちで過ごしていたらおよそ3ヶ月で性別、国籍問わず友達がめっちゃ増えました。

緊急事態宣言が出てたのでリモートだったのですが、飲み会なんかもやったりしました。

そして、その中の一人の女性とお付き合いすることになりました。

出身は宮城で、去年東京にきたんだそうです。まだ東京慣れしてなくて、休みの日は原宿デートがメインですが東京探訪をしています。

彼女はとても感情豊かで、話しているととっても癒されます。この間も、コンテストで冷えたことを報告したら泣きながら僕の胸元に抱きついて慰めてくれました。

仕方ないので、僕が頭を撫でていると、気づいたら僕の胸元で寝ていました。まったく、どちらが慰めてるのか、って感じですね。

そんな感じで、青になった今も楽しく問題を解いています。今では彼女と結婚に向けた話を進めているところです。

データ構造・アルゴリズム・知識

水の時期にやったと思われる内容をほぼ全て紹介します。

• Segment Tree
• Lazy Segment Tree
• Binary Indexed Tree
• Slope Trick
• Li Chao Tree
• 重み付きUnion-Find
• Euler Tour
• 木の半径
• 非再帰DFS
• 形式的冪級数
• グレイコード
• Suffix Array（SA-IS）
• Manacherのアルゴリズム
• Run-Length Encoding
• Z-algorithm
• 偏角ソート
• 円の共有点、包含関係
• 全方位木DP
• 凸包（O(N²)）
• 2次元アフィン空間
• SCC
• LCA
• 木の重心
• ベルマンフォード法
• ダイクストラ法
• クラスカル法
• TSP
• bitDP
• 牛ゲー
• ワーシャルフロイド法
• NTT
• 中国剰余定理
• Garnerのアルゴリズム
• 高速ゼータ変換
• 高速メビウス変換
• 高速アダマール変換
• 離散対数
• レピュニット数
• 約数系包除
• FloorSum
• and畳み込み
• or畳み込み
• xor畳み込み
• スターリング数
• カタラン数
• 分割数
• 多点評価
• 多項式補間
• LIS
• 半開区間は便利
• 桁DPをやるときは母国語でコメントを書いた方がいい
• 中央値を求めたいときは、ある数以上のものを1、そうでないものを0として二分探索して調べる
• 二次元配列は一次元に直した方が気持ち軽くなることがある
• Union-Findではサイズが大きい集合に繋ぎ直すと計算量が落ちることがある
• インドゾウの足の裏の面積からインドゾウの体積を求める方法（Sreekumar Function）
• 日焼け止めは将来のためにどんな理由にせよ塗っておいた方がいい
• コンドームを付けて致すと手は洗ってもベタベタだけどゴミが少なくなるしにおいも汚れも少ない
• 半蔵門線は水天宮前駅で日比谷線の人形町駅と接続するというが、それは真っ赤な嘘
• アヴ様の誕生日は8/27ではなく9/27
• セグ木の二項演算は抽象度を上げるために外部から入れた方がいい
• 睡眠は大事

イベント

• 卒論執筆
• 大学卒業
• 大学院入試
• プログラミング系アルバイト
• 正社員登用

ちなみに、過去問のとこで述べた彼女の話は全て作り話です。

まあこんな下手くそな嘘で騙されるような純粋な方はさすがにこの世に存在しないとは思いますが、万が一騙されたという人がいれば、今度インチキ量子論セミナーに送り込んでやるので覚悟しておいてください。

ファッション

スカートパンツを買いました。結構良いんですけど、自転車に引っかかりそうで怖くて着れてないです。

あと化粧水と乳液でのケアを始めました。

アイドルヲタ

推しが卒業とグループ解散を経験し、現在活動が第3章です。

イラスト

カイリューさんにファンアートをプレゼントしたり、きりみんちゃんのイラストを描きました。

蟹江もなみさんときりみんちゃんの4コママンガも描きました

これからやる予定のこと

これからの目標というか、これできたら強そうとか強くなれそうだなとかさまざま。

• AtCoder Rating1800 → 達成できたらARC出る
• 任意modFPS
• フロー
• 2-SAT
• Segtree beats
• Codeforces復帰、Rating1900
• MojaCoder作問
• 問題解説記事執筆

さいごに

青になるのは難しいですが、青diff以上の問題は面白いです。解説ACでもやってみる価値ありです。

ごめん言い忘れた

少なくとも水色安定したいのであれば、BITとセグ木のライブラリは忘れずに整備しておきましょう。

それでは、今日はこの辺で。

黄色になったときの色変記事に続きます。