モグリンの競プロ備忘録

主に競プロの記事を書きます

入水しました

はじめまして、mogurinです。ブログを始めるにあたって最初に何の記事を書こうかなーと思ったので色んな人が書いてて書きやすそうな色変記事から書くことにしました。ですので、基本的にここに書いてあることは入水した約一か月前のことになりますがご了承ください。ついでに初めての記事だから色々荒いのも許して

f:id:mogurin1000000007:20201121040945p:plain

これわざわざ入水時点のグラフ引っ張り出してくるのに時間かけたのウケる

1.自己紹介

所属:東京大学理科一類

競プロ歴:およそ9か月、(入水時点で7か月強)

Twitter:mogurin (@mogurin_kyopro)

Atcoder ID: mogurin

2月にAPG4bをやる前はプログラミングどころか人差し指タイピングだったAtcoderの完全純粋培養(?)競プロerです。趣味は当然競プロ、後最近はノベルゲーにハマってます。ICPCに一緒に出てくれるUT生募集中です!!

 

2.水になるまでにやったこと

 

はじめは水になるまでにやったことを、各色になるまでごとに分けて書こうかなぁ、と思ったんですけど、元々の原稿が6000字を超えたあたりで心が折れたのでこの記事はゆるっと書いてもし何か特筆して書きたくなったら別の記事に書きます。

あーこれも結構あるな面倒くさいなー........ん?

そうだ、他の入水記事書いてる人で僕の知ってるアルゴリズム全部書いてくれてる人の記事引用すればいいんだ!!(最低)

というわけでこちら

 

AtCoder 水色わーい!soohprogramming.wordpress.com

 

W_Acmanさんの入水記事です、いろんな記事見たけどこの記事に載ってて僕が履修してないアルゴリズムはあっても入水時点での僕が履修しててこの記事に載ってないアルゴリズム多分ない、気がする。(こんな引用の仕方でごめんなさいW_Acmanさん...、ちなみにかなり良いこと書いてるんでみんな読んでみてね、特に後半)

 

流石にこれでアルゴリズム部分終わりだと神様から赤べことか頭の上に落とされそうなんで個人的に印象深いとこだけでも色々書くか

 

  • 累積和、BFS/DFS、bit全探索、コンビネーション(組み合わせ)

驚くべきことにこれらの単語を (単語) けんちょん の順にならべて検索するだけであなたに最適な記事が出てきます、けんちょんさん、いつも良質な記事をありがとう。

なぜかコンビネーションだけ出てこなかったからリンク貼っときます。しっかりしてGoogle

qiita.com

 

通称DP、これ一つの呼び名でまとめるのどうかと思うよね、いや私も便利だから使うが。簡単なのは本当に簡単ですが、時に赤diffになってABC参加者を苦しめたりします恐ろしい子。対策としては Educational DP Contest

atcoder.jp

がおすすめです、解けば解くほど典型DPがわかる(気がする)。例のごとくけんちょんさんの解説記事があるのでこちらもおすすめです。

qiita.com

 

後はフレンズさんの記事もユーザー解説についてるので好きな方(あるいは両方)を読むといいと思います、どちらも非常にためになります。一度学べば想定解がDPじゃない問題も少し遠回りすれば楽な発想でDPで解けたりすることもあるので学んで損はないはず。

 

  • ModInteger、セグ木、BIT、UnionFind(、遅延セグ木)

データ構造ってめんどいよね、わかる、僕も実装できない。

けどAtcoder優しいから公式データ構造を作ってくれました、公式マイバチみたいなもんだね(伝われ)。使い方もドキュメントに書いてある至れり尽くせり仕様なので、もしセグ木とかの実装に困っている人がいたらガンガン使いましょう!!

ところで遅延セグ木だけは結構ドキュメントが難しい気がします(主観)、なんかわかりやすく書いてるところないかなー

 

 

opt-cp.com

 

 

ありましたね、というわけでoptさんの記事です、非常に細かくわかりやすく遅延セグ木の使い方が書かれています。これで遅延セグ木を使う問題も怖くない!!optさんありがとう!!

 

  • 二分探索

二分探索ってあれだよね、単調増加(減少)数列から少ない計算量で必要な値引っ張ってこれる奴。

 

atcoder.jp

?????????ナニコレ????????

 

 

というわけで人によっては典型、人によっては大苦戦を強いられた問題ですが(私は後者、コンテスト中には解けなかった)、この問題を解いたことがない人はこれを解説ACでも良いので解いてから続きを読んでほしいです。

 

 

 

 

 

 

 

はい、おかえりなさい(?)、値を決め打ちすることで二分探索の問題に持ち込む、 自力でこれ思いつくのはさすがに無理だろ。このように二分探索にはある値以上/以下で性質の変わる値の求値問題を、Yes/No判定問題に持ち込めるという強力な側面があります。使いどころを見極めればこれは非常に強力なツールです、時に黄diff以上の問題でもこの方法で簡略化して解けることがあります。流石にこのレベルの問題だと二分探索が本質であることはまずなさそうですが、問題を簡略化できることで視野が開けることはよくあります。(経験談)

 

アルゴリズムで書きたいこと他にあったかなー、特に思いつかないんで思いついたら追記しますね。(適当)

 

  • やったこと

  • 茶diff埋め、緑diff埋め

茶diffと緑diffを埋めました、ちなみに今はdiff変更により埋まってないグラフに逆戻りしました、悲しい...。特に効果があるかといわれると...、ほら、埋まるとなんか達成感あるじゃないですか、そんな感じです、多分。実際一色下の色埋めればその色のレートになれるって黄コーダー(当時青コーダー)が言ってた。また埋めなおさなきゃ...

f:id:mogurin1000000007:20201121102356p:plain

悲しい...
  • バチャ

くじかつに出てみました。楽しいけど長続きはしなかった...やっぱり時間縛られるのきついよね。

 

 

あれ俺やってること意外となくね?大丈夫か?

緑diff全部埋めるのは言葉以上に大変なはず、多分、そういうことにしておきます。

 

3.意識していたこと

  • 諦めない

負けないで、もーおー少しー(古い)

コンテスト中、明らかに自分の知らない典型を含んでいる、あるいは自分の解いてきた問題より高難易度、または添え字ガチャで外れしか出ない(それはただのバグでは?)、など様々なこちらの心を折りに来る事態に遭遇します、した。こんな時、ほんっっっとーーーに心が折れそうになるのですが、最後時間いっぱいまで折れないことを私は意識していました。もちろん何もできずに終わることのほうが多いのですが、ごく稀にミラクルは起こります。自分が散々悩まされた問題の解法がひらめいたとき、そしてその解法が通った時の達成感はひとしおです。ダメでもともと、最後まで粘り続けるのは、きっと大切なことだと思います。

 

  • 自分を天才だと信じる

理由なんてなんでもいいです、とにかく私は天才なんです。僕は天才僕は天才僕は天才僕は...

 

 

 

 

 

と、コンテスト前(あるいは最中)に自分に暗示をかけると「この問題も天才の私に解けないはずがない」と考えられるようになります。これほんと。実際舐めてかかったほうが超速で典型に落とし込む道筋が見つかって解けたりする。やっぱ俺天才だわ。よし、この調子でABC183全か...

f:id:mogurin1000000007:20201121135822p:plain

え?

f:id:mogurin1000000007:20201121135844p:plain

は?

f:id:mogurin1000000007:20201121140009p:plain

引退です...

こんな感じで解くべき(解かないと冷える)問題が解けないと著しくメンタルを傷つける諸刃の刃です、用法用量を適切に守って服用しましょう。

4.最後に

なっがながと毒にも薬にもならない駄文書いた感ありますけどまぁ当初の目標である入水できたことは素直に嬉しいのでこっからも頑張ってくつもりです。結構入青近づいてきた気がするし!(単に最近あたりくじ引いてただけ説は、ある)

結局考えること精進の仕方は人それぞれなんですが、私の記事が少しでも役に立つ人がいてくれるならこんなにうれしいことはありません。

最後に、twitterその他での私の質問に嫌がる素振りも見せず丁寧に答えてくださった皆さんや、いつもわかりやすい解説記事を書いてくれる皆さん、ここまで様々なアドバイスを下さった TeamSPJ のお三方、そして何よりもここまでこの記事を読んでくださったあなたへの感謝をもって、この記事の締めとさせていただきたいと思います、本当にありがとうございました!!

 

余談

 この記事書いてる最中に昔のやったこと見返してたんですけどAPG4b普通に難しくありません?詰まりやすいポイントと対処法とかまとめた記事を次は書いてみようかな