AtCoder黄色になりました！

こんにちは、ゆうです。先週のABC190でAtCoder黄色になったので、初めて色変記事なるものを書いてみようと思って画面に向かっています。再来週からARC＊2やAGCが控えているので、そこで落ちたりする前に書いておこうという魂胆です。一貫としたストーリー性はありませんが、色変記事といえばこういう話題があるでしょ！というのを一通りやりたいです。

１：自己紹介

yuusanlondon.hatenablog.com

自己紹介記事に書いてあることと少し重複しますが、競プロと関係してくるところでざっくり言うと、

• 修士1年（1年しかない修士）、数学科。
• 競プロ前のアルゴリズム経験はほぼ０、プログラミングは大学の宿題でMatlabをいじった程度。
• 高校2，3年のころは競技数学、競技科学が好きで（下手なりに）やってました（情報には手を出しませんでしたが）。

という感じです。競プロは去年4月に、コロナで大学が休学になったところで友人に誘われて始めました。

２．なにをやったか

AtCoder Problemsの Diff別進捗円グラフ

Rating-history のサイト別AC数

黄色になったのに黄色AC15、橙以上0はまずくないか。。？という気がします。これからは暖色Diffにも積極的に手を出していきたいです。

精進の方法：

AtCoderを時間無制限のゲームとしてとらえているので、レートを伸ばすために精進したい、という気持ちと、楽したい楽しくやりたい（ほとんど変わらないじゃん）という気持ち両方を成立させようとしています。すると、一番楽しくて効果的な精進は本番で、次にバチャ*1となるので、この二つをメインにやっていってます。後は解説ACについてですが、解けなかった問題でもう考えが出尽くしたけど、答えが知りたい、と感じるものは解説を読むのですが、解説ACは面倒でやっていません。なので、実際に読んだ問題は上の数より多いと思います。

３．学んだデータ構造・アルゴリズム

賢いデータ構造・アルゴリズムと出会い習得することが競プロの醍醐味だと思いますが、その習得フェーズをちゃんとやるのを面倒がってしまい、さらにデア解説をさらっと読むだけだと忘れてしまう記憶力なので、知っているデア（以下の「自分では書けないけど。。」まで）はほぼほぼ必要最小限だと思っています。*2まあさらに言うと、レートが1900ぐらいになったころから、「黄色になったら勉強しよう」と後回しにする理由ができてしまったので、今まで以上にサボってしまっていました。

正直ここまできたら、入黄して、色変記事に「勉強したくないそこのあなた、黄色になるには、表立った知識はこれさえ抑えれば、後は経験でどうにかなります！(時間はかかるかも、ちゃんと勉強した方が速いかも)」って書いてやるんだ。。と思ってる

— ゆう🛸@多次元配列は1次元に直す（過激） (@yuusanlondon) 2021年1月25日

（だいたい）使える：

• 高校までの数学全般（√Nで因数分解、とかも含みます）
• 全探査（bit全探査なども）
• ポインター使ってえいや！するやつ（語彙力。。。）
• ダイクストラ
• 二分探索
• 非再帰DFS（こどふぉで再帰を書くと詰みます）
• BFS（あまり使わないしライブラリ化してるダイクストラをコピペしてちょっといじることが多いですが）
• deque, heapq, dict, set
• 累積和・imos法
• DPという考え方（DP、奥が深くて「使える」とは多分一生言えないですが、「いらない情報を捨てて・圧縮して操作回数を減らす」、というアイデアは頭に入れてあります。またLCSとか*3の初等典型も知ってます）

自分では書けないけどライブラリを拝借してコピペしているもの。広義「使える」

• Union-Find木
• セグ木・BIT（遅延セグ木もついこの前こどふぉで初めて有志pythonACLからコピペしてみましたが、システスTLE落ちしました(´；ω；`)ｳｯ…）
• 線形操作を行列に詰め込んで、繰り返し二乗法とかで速くする奴

解説を読んだことあって、用途は分かってるけどどうやってやるかは覚えてないもの

• ベルマンフォード、ワーシャルフロイド、最小全域木
• 尺取り法
• トポロジカルソート
• オイラーツアー（この前読んで、やり方も覚えているんですが、まだ書いてないし、再帰を使わずに書く方法をまだ研究してません）
• LCA
• 3分探索

名前を聞いたことあるけど用途は知らない

• フロー、最大流（多分これが次に覚えないといけないやつだという印象です）
• 形式的冪級数、FPS（Call of Duty?)
• FFT
• 座圧（重たそう。。。）
• Z-アルゴリズム
• Mo'ｓアルゴリズム (バーテンダーが発明したアルゴリズムみたいな名前してますね）
• ローリングハッシュ（ロリハ、語感は好きです）
• 2－SAT

４．言語について

僕は✞Pythonista✞を名乗っていますが、pythonという言語自体についてはあまり詳しくありません（他の言語はもっと詳しくありません）。でも、こういう言語への理解が薄い人でも使える、「直感的にやってほしいこと」をだいたいやってくれるという面でやっぱりpythonをお勧めしてます。というのは、この前実行時間対策にC++の勉強をしてみたのですが、もう難しくて難しくて。。。灰Diffも自由に解けませんでした。挙動が謎ですし、エラーの時の説明文もpythonのほうがよっぽどわかりやすく感じます。おーばーふろー？とかも気にしなくていいし、型も定義しなくていいし、セミコロンいちいち打たすとかいう意味不明なことさせられないですし。。。こんな難しい言語を初心者にお勧めしている人たちはなかなか鬼畜ですねぇ（煽り）*4

pythonはC++に若干*5速度は劣りますが、最近のAtCoderは想定解がpypyで通る*6ような設計を目指しているらしい*7ので、まあまあ*8安心*9できます*10*11

というわけで皆さんもぜひぜひpythonを使いましょう！

５．メンタルについて

以下書くことは、あくまで自分はこう考えてる、というものです。

競プロを長期的なレートや実力を競うゲームだととらえると、個人的にはかなりメンタルへ影響を減らすことができると思っています。人生の残り時間は無限にあるので*12、例えば6か月停滞しても、残り時間

無限-6か月＝無限で全然セーフです（は？）

就職などに競プロを使おうとする場合はこの作戦じゃちょっとダメかも。。。

６．これからについて

当然、次は橙色*13を目指します！！！と言いたいところですが、いや、橙以上ACが一個もない人が言えるわけないです。現在アットコーダーアクティブユーザー内1178位なので、1000位を目指したいかな、とか思ってます。まあもちろん達成する前に青に何回かなることは覚悟しています。あくまで長期的にゆっくりでいいから上っていきたいです。

最後まで読んでくださりありがとうございました！いつかまた色変記事が書けるといいな、と思ってます。*14

*1:バーチャルコンテストと言って、Twitterなどで参加者を集めて過去の問題集を一緒にやったりするもの。主催者の方々に感謝です！

*2:競技数学ガチ勢とかデータ構造、アルゴリズムのセンスがある人ならこれ未満でも黄色になれると思いますが、その場合ABCはほとんど出ないでARCやAGCで激むず数学問などを解いてなる、という方が多いような気がします。

*3:とか、って言ってるけどほかに例が思い浮かばないのですが

*4:ごめんなさいごめんなさいごめんなさい

*5:若干とは　検索

*6:かもしれない

*7:訳：という噂を大昔に聞いたかもしれない

*8:まあまあって言葉便利ですよねーこれで僕の責任はゼロ！

*9:嘘です。こどふぉのシステスをC++erの百倍恐れています

*10:想定解以外のもっと簡単な解法がC++だけ通る、とかはあります。

*11:あとこどふぉは普通にpython虐殺してきます

*12:人生残り時間無限は多分偽ですが、50年とかまあほぼ無限でしょ(数学科としてあるまじき発言)。この点、社会人の方や、また40代や50代の方でもやっている方がいらっしゃるのはすごく安心できます

*13:はてなブログの文字色で一番近かったのがこれなんですが。。。

*14:再来週のARCでレートを8失えば。。。？