AtCoder 1級になりました

　先日行われた第二回日本最強学生選手権で224位perf 2127 を取り、

AtCoder 1級になりました！！！

　せっかく昇級したので、喜びの声ついでにブログを書こうと思います！！！！！！！！！！！！！！！！！
　とりあえず各種記録から↓↓

レーティング遷移

f:id:yamakeeee:20210423000135p:plain

各コンテストサイトAC状況

Solved By yamake
Topcoder: 0
Codeforces: 506
AtCoder: 1181
AOJ: 12
yukicoder: 21
library-checker: 1
Sum: 1721

AtCoder

f:id:yamakeeee:20210420215715p:plain
f:id:yamakeeee:20210420215808p:plain
f:id:yamakeeee:20210420215830p:plain
f:id:yamakeeee:20210420215847p:plain
f:id:yamakeeee:20210420215949p:plain
f:id:yamakeeee:20210420220042p:plain

Codeforces

f:id:yamakeeee:20210420220223p:plain

スニペットに登録されてるデータ構造/アルゴリズム

　本当は「履修したデータ構造/アルゴリズム」を乗せたいのですが、思い出すのが~~面倒くさい~~大変なのでライブラリに入れてるデータ構造/アルゴリズムを紹介します。
　実際に使っているもののみ抜粋です。以下のデータ構造/アルゴリズムは "貼るだけ" です。

素数mod, nCr
繰り返し二乗法
mod をとる掛け算の逆元
セグ木（非再帰）
行列演算クラス（研究で使っていたものの仕様をパクった、繰り返し2乗法もできる。）
String で整数を文字列として受け取ってmで割ったあまりをint で返す関数（一度だけ使った気がする）
グラフ構造体
- 入力を受け取りグラフを構築する
- トポロジカルソート
- ダイクストラ
- 二部グラフ判定
- ワーシャルフロイド
LCS
時間計算量 $\Theta(\sqrt N)$ の素因数分解
座標圧縮
順序付き整数集合で、要素の追加、削除、小さい方からk番目を取得が $O(\log N)$ でできるやつをセグ木で実装したもの
UnionFind
木の構造体
- 入力を受け取り木を構築する
- BFS
- DFS+オイラーツアー
累積和
最大独立集合
エラトステネスの篩（無いと思ったので今書きました）

　"よく使うものはちゃっちゃとライブラリ化すべき" みたいな思想があって、単純ですぐ書けるものでも、ライブラリとして貼るだけの状態にしておくのは速度も上がりバグも生みづらくなって良いかなと思います。

読んだ本

蟻本

　この問題で爆死して、蟻本読むか〜〜と思ったら大学図書館で電子書籍が読めたので読みました。京都大学のｷｮｳは競プロのｷｮｳ！！読んでみると普通に面白くて、難しいところは流しながらとりあえず一通り読みました。Lucas の定理とか全然記憶に無かったので、次はもう少しきちんと読みます...。演習問題は答えを見ずに、できるだけわかるまで考えました。どうしてもわからない問題は答えを読みました（牛ゲーなど）。サンプルコードは写経まではしていませんが、読み飛ばしもしませんでした。きれいな実装を学べる機会でもあるので、C++er には二度おいしい本だと思います。

組合せ論, ラスロウ・ロバース

　数え上げを期待して読んでみたらグラフとか出てきてびっくり、どちらかというと「◯◯を満たす組合せがあるか？」に関する議論が多い印象。とはいえ数え上げもあって、競プロer には結構刺さる内容が多くて面白いと思います。1対1対応、鳩の巣原理、2項係数関係の天才式変形、グラフの話、漸化式の解き方などが載っています。競プロにもすこし役立つと思います。

数学ガール　 乱択アルゴリズム, 結城浩

　タイトルが面白そうだったから買いました。内容も面白かったです。経路の数え上げ、『 $O,\ \Theta,\ \Omega$ の使い分け』、対角化を使った行列累乗、3-SATの乱択、乱択クイックソートなどの内容があります。競プロにもつながる内容が多くて面白いです。
　ストーリーへの言及をしている人を見たことがないので下の行に白文字で感想を書きます。読みたい方はドラッグして読んでください。あくまでも個人の感想です。
　リサとミルカさん、お互い自分にはないもの（数学に明るい親/数学の能力）を持っている相手を意識して少しバチバチになっている、でもそれは理不尽な感情だから露骨には出さないようにしている。それはそうと、お互い相手の得意な部分を認めて尊敬しあっている。そんな関係性が尊い...。

ゲームづくりで学ぶPython, 日向俊二

　目指せ脱純粋培養！と思って買いましたが、pygame というライブラリに詳しくなるだけでした。ゲームを作るのはそれはそれで楽しいからok。たぶん競プロの役には立ちません。

アルゴリズム理論入門, 岩間一雄（まだ読み切ってない）

　本屋さんで見つけて、知らないこと、興味有る内容が多いので買いました。面白いので少しずつ読み進めていますが、練習問題に答えがなくて厳しいです...。一緒に読んでくれる誰か氏〜〜〜。この内容が競プロの役に立つ未来はあまり見えません。

りゅうおうのおしごと！, 白鳥士郎

　人生で大事なことは大体りゅうおうのおしごと！から学びました。基本的に将棋か小学生の話です。競技プログラミングからプログラミングを抜いた部分と将棋は似ているので（「きょうぎ」と「しょうぎ」の編集距離は1）、競プロer なら将棋が好きでなくても楽しめると思います。好きなものに熱くなれることの素晴らしさ、小学生の素晴らしさなどの内容があります。読むと何故か競プロモチベが上がる（マジ）ので、競プロの役に立つと思います。小学生部分が気に入った人は、ロウきゅーぶ! も読んでみると良さそうです。

マシュマロ回答

　何書こうかな〜〜って思った時に色変ブログとかでマシュマロ回答してるのあんまり見なかったし、面白そうと思って聞いてみたけど、想像よりずっと質問来なくて焦りました。
　最終的にはたくさん質問が来ました。送ってくれた方ありがとうございます！！

Q. 競プロでの得意、苦手分野はなんですか？この得意、苦手分野は時間と経験を経て変わりましたか？

A. 得意・苦手分野は時間と経験を経て変わっていて、得意分野苦手分野の変遷についてまとめると↓のようになります。
　時期:　得意 / 苦手
　最初: 数学, ad-hoc　　　 / プログラミング
　〜緑: 数学, ad-hoc　　　/ DP, グラフ関連
緑初期: ↑, 基礎的なDP　　/ グラフ関連
緑〜水: なんでもそこそこ　 / 典型速解き
水〜青: 木関連　　　　　　 / ad-hoc, DP
　〜今: 数え上げ, 典型速解き / ad-hoc, 数学, 構築

　あくまでイメージですが、↑の感じです。
　青になるまでは "苦手分野の難しい問題を1問めちゃくちゃ考える -> 苦手意識が消える（得意になる）" と、"苦手な問題ばかりに取り組む -> 苦手な問題が得意になる -> 最初得意だった問題が相対的に苦手になる" を繰り返していたイメージです。
　余談ですが、ad-hoc は相対的に苦手になって以降、得意になる未来が見えません（泣）。

Q. 最近あった良かったことを教えてください！

A. マシュマロ1件しかこね〜〜って泣いていたら、このマシュマロが飛んできたことです！！！あとはAtCoder のレーティングが1800を越えたことですね。

Q. □□□□（マシュマロにより伏せ字）ですか？

A. なんとなく何聞かれてるかわかるんですよね。回答は伏せます。

Q. どんな精進をしていましたか？

A. 〜1500 は基本的に AtCoder Problems の Recommendation の moderate か Hard をやっていました。次に所属している部内で AtCoder でのバチャが流行り、廃れました。その次に AtCoder Problems でのバチャが流行り、廃れました。諸行無常。この間も Streak は意識していました。
　以降は栄枯盛衰が速いので、箇条書きでまとめます。

青になってから

1. Streak が切れる。
2. JOI の難易度6を埋めた。
3. Streak 時代に「AtCoder のStreak が繋がらないから」という理由でやっていなかった Codeforces のバチャをするようになった。
4. JOI 難易度7を埋めた。

青安定期

1. えすえふさんのバチャ*1に出る。
2. 修論が迫ってきてあまり時間を取れなくなる。もにふぉ*2へ参加、えすえふさんのバチャはあまりしなくなる（競プロの時間変わって無くないですか？）。
3. 修論終わりの目処が立つ。毎日もにふぉ、div. 3バチャ時代に突入。この時期が一番バチャをしていた。
4. 修論提出後研究活動にハマり、何もしなくなる（修論書いてるとき無限にアイデアが湧いたので）。
5. 社会へ出荷、バチャをしなくなり黄 diff を頭に入れて暇なとき考えている　←今
です。

解説 AC, 解き直しなどについて

　解説 AC についての考え方ですが、基本的にはしない。どうしてもわからないけど答えが見たい、最近のコンテストでネタバレ不可避、ABC, div. 3, えでゅふぉの問題の場合は解説を見る。としています。今している黄 diff 埋めでは、解けなかったらひとまず放置しています。
　こどふぉバチャを毎日走っていた時期は、詰まった問題はバチャ後〜一時間くらいで解説を見ていました。そうしないと upsolve が追いつかないので。
　解き直しですが、ほとんどしません。一度解いた問題より、初見の問題に取り組みたいという気持ちが強いので。

Q. 1800になるのに一番効いた精進はなんですか

A. 二段階あって、青->青安定では JOI の難易度7埋めが一番効いたと思っています。青安定->1800では、いろいろな要因があるのですが、一番を挙げるならdiv. 3バチャだと思います。今後労働が安定したら時間を見つけてdiv. 3埋めは再開したいと思ってます。

Q. どうやって競プロの時間を捻出してますか？研究や仕事との両立は難しいですか？

A. 研究との両立ですが、正直研究室がホワイトだったからできたと思います。~~研究せずに~~競プロばかりしていましたが、修論は運良くテーマとその解決法を思いついたおかげでなんとかなりました。良い院生は真似しないでね！！
　仕事との両立はこれからですが、『常に数問頭の中に入れて、暇なときに考える』を今していて、良さげだなと思っています。また、自分だけの Slack を作って進捗管理をしていて、これもかなり好感触です。

f:id:yamakeeee:20210421221939p:plain — こんな感じ

Q. 推し教プロerさんを教えてください

A. こたつがめさんとapiad さん、atomicenergy 氏です！！！！！！

Q.どうして色変でなくて昇級でブログ書いてるの？

A. 青になったときブログやってなかったんですよね。でもブログは書きたいな〜〜と思っていて、機会を窺っていました。えびまさんが色でなくて級で実力を分けていたので、昇級を節目にブログを書いても良くね？？ということで書いてみました。
　ちなみにこの質問は自演なので、実際はこのようなチクチク質問は送られてきていません。

Q. おすすめの百合マンガ教えてください（完結済みだと嬉しいでふ）

あまりにも長いので折りたたみ

A. 良い質問ですねえ（ﾆﾁｬｧ
　完結作から紹介していきますね。

やがて君になる　仲谷鳩

f:id:yamakeeee:20210421232958p:plain
www.amazon.co.jp
　百合マンガ、おすすめ、完結済み　といえばこれ！！！みたいな作品。『百合漫画総選挙』4連覇中、百合マンガ界のtourist。百合マンガを読みたいなら、とりあえずこれを読むと良いでしょう。全8巻。
　実は競技プログラミングにも馴染みが深くて、参加者二万人以上のプログラミングコンテストのメインテーマになったこともあります。こちら

高嶺の花はウソツキです　飴野

f:id:yamakeeee:20210421232459p:plain
高嶺の花はウソツキです。 (百合姫コミックス) | 飴野 | 女性マンガ | Kindleストア | Amazon

　なんばでやってた百合展で見かけて、表紙が良すぎてジャケ買いをしました。ギャルだけど初心なJKと、腹黒OLお姉さんの百合です。1巻で完結する作品なので、初心者にも入りやすくてかなりオススメです。

とどのつまりの有頂天　あらた伊里

f:id:yamakeeee:20210421234022p:plain
www.amazon.co.jp
　新進気鋭の百合漫画を応援したいという有志によって行われる『百合漫画大賞』において、2019年に大賞を受賞した作品です！！！構成は2巻完結で、ギャグ要素強めかと思えばしっかり百合もしてくるハイテンション百合コメディです。全2巻。
　現在、同じ設定の『雨でも晴れでも』が電撃大王で連載中です。とどつまとは雰囲気が違っていて、こちらはかなり百合に寄った作品になっています。

徒然日和　土室圭

f:id:yamakeeee:20210421235039p:plain
www.amazon.co.jp
　田舎の女子高生たちが日常を過ごす作品です。田舎の女子高生の何気ないやり取りにほっこりできる作品です。意外とちゃんと百合もしてます。また、背景も含めて描写がとても丁寧です。僕自身今週読んだばかりですが、これも非常におすすめな作品です。全3巻。

短編集

　そう何冊も買ってられるか！！！という方にぴったりなのが短編集です。一冊で5~6個くらいのお話を読めます。まずはいろいろな短編集を読んで、自分の好きな百合漫画家を探すのも良いと思います。僕のオススメを何冊かあげていきますね。

ゆりゆり　なもり

　 f:id:yamakeeee:20210422222229p:plain
ゆりゆり (百合姫コミックス) | なもり | 女性マンガ | Kindleストア | Amazon
　『ゆるゆり』、なもりグラフで有名な作者の出している百合短編集です。二巻も出てます。ゆるゆりの緩さを期待して読んだ見たらかなりしっかりした百合で尊死した記憶があります。

はるゆきろう作品集

　同人サークル『Happy Yellow Rabbit』の『雪子』さん、『河合朗』さん、『はるかわ陽』さんが同時に出した百合短編集群です。全人類買ってください。下のブログに詳細があります。ぜひ見てください。
happyyellowrabbit.localinfo.jp

まだまだ連載中の作品

　完結済みが求められているので、どうしても布教したい2作品だけ布教させてくださいm(_ _)m

ふたりべや　雪子

f:id:yamakeeee:20210422224659p:plain
www.amazon.co.jp
　はるゆきろうの一人、雪子さんの代表作です。高校を機に下宿することになり、そこでたまたまルームメイトになった川和桜子と山吹かすみの日常を描いた作品です。非常に細かい話なんですが、5巻の帯が天才でとても好きです。現在8巻まで発売中。

ふたりエスケープ　田口囁一

f:id:yamakeeee:20210422230303p:plain
www.amazon.co.jp
　〆切に追われる漫画家の「後輩」と、現実逃避のプロである無職金無しヒモ女の「先輩」が織りなす現実逃避コメディー。基本的に笑えるギャグ漫画だけど、時々「後輩」や「先輩」の相手に対する愛情が読み取れる素晴らしい作品。全人類読むべき。現在2巻まで発売中。僕の一番好きな話は16話です。

番外編　百合ラノベ

　最後に、ラノベも紹介します。百合においてストーリーや関係性を重視する人はラノベもかなり楽しめると思います。

女同士とかありえないでしょと言い張る女の子を、百日間で徹底的に落とす百合のお話　著: みかみてれん, 絵: 雪子

f:id:yamakeeee:20210422231322p:plain
www.amazon.co.jp
　「女同士とかありえないでしょ」と言い張る女の子を、百日間で徹底的に落とす百合のお話です。結構えっちです。みかみてれん文庫で4巻まで、GA文庫で3巻まで発売中です。僕はGAで追っているので完結しているかを知りません。マンガUP! にてかやこさんによるコミカライズも連載中です。