An Engineering Student's Frank Report.

どこかの工学系学生の覚え書き的な何か。

AtCoder青になった感想

※注意※

この記事で,「問題」などの表記があるところにリンクが貼られている場合,そのリンク先の問題のネタバレを含んでいる場合がございます。ご注意ください。

はじめに

来る先日7月25日のAtCoder Regular Contest 124で,AtCoder青色になることができました!

f:id:Angry_Sad_Eight:20210730225758p:plain

f:id:Angry_Sad_Eight:20210730225817p:plain

ということで,せっかくの機会にと,AtCoder青になった感想をまとめていきたいと思います。

AtCoder青になるまでにやったこと

ここは他の方がたくさんまとめられていたりするとは思うので,簡潔に流したいと思います。どちらかと言えば,この後の「競プロをやるうえでの心構え」という項目のほうがこの記事のメインみたいなところがあるので,出来ればそちらの方を見た方がいいのかなと思います。

問題精進

AtCoder以外のコンテストサイト等でも問題を解いていたりはしますが,ここではAtCoderのもののみ掲載します。

なお,以下の表は,AtCoder Problemsのものです。

f:id:Angry_Sad_Eight:20210730230128p:plain

f:id:Angry_Sad_Eight:20210730230619p:plain

f:id:Angry_Sad_Eight:20210730230631p:plain

f:id:Angry_Sad_Eight:20210730230642p:plain

f:id:Angry_Sad_Eight:20210730230653p:plain

アルゴリズムとデータ構造など

水色になって青になるまでに新たに身に着けたアルゴリズムとデータ構造,競プロでのテクニックなど。

・半分全列挙

概念じたいはそんな難しいものではないけど,すごく頭の良い発想だなぁって思った。

・座標圧縮

たぶん緑までのときにも何かしらの形で似たようなことはやっていたのでしょうが,流石に「座標圧縮」という言葉を知らないのはマズい!と思って,水色になって改めて意識するようになりました。

・三分探索

ふわっとしたところは知ってましたが,この前の某ABCの問題でその理解の甘さを思い知らされました。

・二次元累積和

頭混乱するからってことで今まで忌避してきたけど,意外とたいしたことはなかった。

・最長増加部分列(LIS)

これが簡単なDPと二分探索の合わせ技で求められるって蟻本で見たときは「ほえー」となりました。そんなの思いつかんて。

・ビットDP

これ,身につけると本当に解ける問題の幅が広がると思いました。個人的に,水色で是非身につけるべき一押し。

・「部分集合の部分集合」を列挙するO(3N) の全探索

ビットDPと関連して。ABCで出てきたということなので履修しました。考え方も実装の実現方法も天才か?

クラスカル

最小全域木を使う問題が出てきたからってことで履修しました。直接この方法を使うわけでなくとも,この考えが重要,というような場面も多そう。

・01-BFS

ABCにこれが出て見事に破滅したので履修しました。個人的にはキューを2個交互に使う実装がお気に入り。

ダイクストラ

水色になって以降すらも長いこと放置してきましたが,流石にこれ知らないのはヤバい!と昨年末に履修しました。今では自前のライブラリを持ってすぐに使えるようになっています。*1

・ベルマンフォード法

やり方はわかるのですが,あまり書いたことがなく,ライブラリ化もしていないので不安です。

・マージテク

これも某問題に出てきたので履修。これ天才か?(n回目

・強連結成分分解(SCC)

いざというときに使いそうかなぁと思い,ACLで使えるようにしておきます。

・トポロジカルソート

SCCに関連して,重要になる場面も多そうかと思って。入次数を管理する方法で実装していますが,DFSの方も理解したい。

・ローリングハッシュ

難しそうというだけで忌避してきましたがそこまで難しくもなかったです。本番で文字列を扱う問題が出たらちゃんと使いたいなぁ。

・セグメント木

色々なところで便利になりそうなので。一応自前での実装もありますが,基本的に便利なのでACLを貼っています。

・遅延評価セグメント木

こちらは完全にACL頼りです......

・高速素因数分解(osa_k法)

この方法本当に凄いなぁって思って個人的に好きです。昔に一回出てきたけど,あんまり最近出てきてない?

・行列累乗

いざ実装しようとすると面倒になることがわかり,完全にライブラリ化しました。

・ダブリング

繰り返して同じものが出てくるものを高速化したいなぁと思ったときに発想として出てくるとうれしい気持ちになりそう。

・二部マッチング

これを知らなかった,というか少し前までフロー自体何にも知らない状態でいたので,これを機に履修。実装は相変わらずACLに任せてます。

・燃やす埋める問題

最近履修しました。解ける問題のバリエーションが広がりそう。「燃やす埋める」ってネーミングが好き。

Grundy

全然知らないのもアレかと思っていったんは履修しました。まだあまりうまく使えそうな自信はない。

・一次不定方程式/中国剰余定理

これがACLの普及により簡単に解けるようになったの本当に大きいと思う。

・畳み込み計算(convolution)

実装はAC(ry ともかく,使える場面がわかってきたのは成長だと思います。

・主客転倒テクニック

競プロ典型90問で出てから,改めて意識するようになりました。これが見えるようになってからは視野がすごく広がったなぁと思います。

OEIS

整数列を検索できるツール。うまく使えるとABCやARC,AGCなどのコンテストで合法的にズルをして勝つことが狙えます。私はコンテスト本番に,数え上げの問題で小さいケースの通り数を調べてその数字をOEISに投げたら答えの手がかりを見つけることができ,結局よくわからないままACを得ることが出来た,ということさえありました。

このほかにも色々ありそうですが,まぁこの辺にしておきます。

競プロをやるうえでの心構え

精進について

コンテストと関係ない昔の問題に関しては,基本的には気まぐれでやってきました。やりたいときにやりたい問題をやる,という感じ。「何色を埋めるぞ!」という計画性を持って問題を解こうと思ったことは無いです(そういうのやってもあまりうまくいかない体質だということは自分がよくわかっているので)。

アルゴリズムの勉強に関しても本当に気まぐれです。するときはしていましたが,基本的には「解いた問題でよくわからないアルゴリズムが使われていたら覚える」くらいのスタンスでやってました。*2

なるべく自力で考えて自力でACする,ということを心掛けてはいましたが,数時間単位で考えてもわからないようなら解説を見ることもあります。自分の知らない知識を使って解くような問題があったりすることがあるからです。

ABC,ARC,AGCのどれを集中してなどというのもあまりないです。また,大昔の問題は「方針は単純だが実装が変に面倒」という問題も多いのですが,競プロにおいては実装力も大事なので,そういう問題も訓練だと思って通すようにしています(特に私は実装力が弱いと思っているので,そういう力を磨くのがなおさら大事になってくる)。

ただ,E869120さんの競プロ典型90問」は絶対にやったほうがいいと私は思います。競プロ(主にABC)に必要なエッセンスが本当に見事にあの90問の中に凝縮されている,と感じました。私が青になれたのは,典型90問に取り組んでいた影響が非常に大きいと感じています。*3

たまにバーチャルコンテストに出たりすることがあります(最近はあまりやれてはない......)。

コンテストについて

コンテストについてですが,AtCoderのABC,ARC,AGCといったコンテストは特別な事情がない限り必ず出るようにしています。だいぶ前(1年半くらい前?)にはコンテストに出ないこともたびたびあったのですが,何度でも出られる上に慣れが非常に大切である競プロというコンテンツの特性上,コンテストはたくさん出たほうが得をするものだと思うようになったので,よほどのことがない限り,(たとえテスト期間であろうが)AtCoderのコンテストには出るようにする,と思うようになりました。これの大きな理由としては,コンテストでの「戦略」というものがコンテストでは非常に重要であり,それは,コンテスト本番でしか効率的に身につかない,と思うようになったこと,そして,最終的にレートを上げるためには毎回コンテストに出て,レートを上げられるチャンスを逃さないことが大事だからだと思うようになったこと,が挙げられます(どちらも後述します)。

yukicoderのコンテストも面白い問題が多いのでたまに出たりしています。Codeforcesに関しては,平日や夜遅い時間に開催されることが多いため,あまり最近は出られていないことが多いです。

 

さて,コンテスト中の立ち回りに関してですが

・順位表は必ず見る

・そのうえで,自分の状況がどうなのかを判断し続ける

ということを常に意識しています。順位表に関して,どれくらいの人がどの問題に正解している,という情報が得られるのですが,この情報が,コンテスト中においては非常に大事だと感じています。

例えば,あなた(ここではAC人数の説明の都合上,水色コーダーを想定します。そうでない方は,後述する「通した人数とDiffの色の関係」の表も参考にしながら,自分の色の場合のAC人数に適当に置き換えてください)がまだ通していない問題で,「コンテスト中に10人通している問題」と,「コンテスト中に200人通している問題」があったとします。このとき,「コンテスト中に200人通している問題」のほうが,「コンテストに10人通している問題」のほうが,通せる可能性が高いことのほうが多いです。このように,どの問題を次に解くべきか,ということがわかります。

また,あなたがまだ通していない問題で,「コンテスト中に2000人通している問題」があったとします。このような問題は,多くの人に通されており,通せなければパフォーマンスが大きく落ちます。なので,今すぐにでも解く必要に迫られています。このように,自分が今どのような状況に置かされているか,というのが,順位表を見ればわかります。

ときに,難易度が問題の順番通りに並んでおらず,いわゆる「逆転」が起きている,ということがあるかもしれません。そうしたときに,順位表を見れば,通している人数が逆転していることがあり,「逆転が起きているんだなー」というヒントがわかったりします。

このように,コンテスト中に常に自分の順位を意識し,そこから自分がどのような立ち回りをするべきかの判断をする,ということが,大変重要になってくると,私は感じました。このような「戦略」は,普段の精進ではなかなか身につきづらいものであるため,コンテストに出て場数を多く踏むことで養っていくことが大事だと,私は強く感じました。

(もちろん,コンテスト中に順位表を見ると変な気を持ってしまって集中できなくなる,だから順位表は見たくない,という方もいらっしゃるかもしれません。自分なりの「戦略」を,コンテストの経験を通じて身につけていってもらえたらと思います。)

なお,直近のABCにおいて,最終的にどれくらいの人数が通していればどのくらいのDiffになるか,という傾向の目安を,参考程度に書いておきます。あくまで参考程度なので一色ぶんは容易に変動しうる可能性があります。また,7月31日からABCが8問形式になるので,この数字はおそらく今後大きく変化していくんじゃないかなと個人的には予想しています。

Diffの色 最終的な正解者数
赤(2800~) ~29人
橙(2400~2799) 30人~119人
黄(2000~2399) 120人~349人
青(1600~1999) 350人~799人
水(1200~1599) 800人~1599人
緑(800~1199) 1600人~2999人
茶(400~799) 3000人~4499人
灰(~399) 4500人~

レートがなかなか上がらないときの気持ちの持ちよう

個人的にここがこの記事のメインかなと思っています。故に長文になっていますがお許しください。

競プロをやっていて,レートがなかなか上がらないときがあります。実際,私も水色になってから青になるまで,何度も何度もレートがなかなか上がらないときを経験しています。結局水色になってから青になるまでに1年かかりました。*4

こういうときにどうすればよいのか,私自身の経験談を話していきます。

まず,経験上,コンテストにおいてレートが上がらないorレートを下げる場合,代表的なものとしては次の3つのパターンがあると考えています。(本当はもっと色々なパターンに分かれると思うのですが,この3つを代表的なものとして挙げておきます)

①そもそも精進をしていなかったためにレートが落ちた。(早く解く能力や,難しい問題を解く力が衰えていた,など)

②精進はしていたはずだが,本番で思いがけないところでのミスをしてしまい,それによってレートが落ちた。

③精進はしていたはずだが,セットとの相性が悪すぎた(崖*5が出来てしまって自分のレート帯にとって不利だった,など)。

 

(④コンテスト中にPCが突然ブルースクリーンになって更新が始まり,使えなくなった。)

 

①に関しては,精進をしていなかったことが直接の原因であるため,問題の復習をする,知識を蓄える,早解きの練習をバチャなどでする,で少しずつ取り戻していけることが多いです。

問題は②,③であり,このようなことは,(上位コーダーがどうかはわからないですが,)平気で起こりうるものです。もちろん,自分が原因であることが少なからずあるので,そこを反省して次に生かそう,となっていくわけですが,精進しているのに本番これをやらかしてレートを溶かす,が続いてしまうと,精神的にもよくないです。実際,私はこのようなことを水色の期間中に本当に幾度となく経験しています。

 

このような場合ですが,私は「今回は仕方がない。また来て頑張ろう」と思って割り切るようにしました。競プロのコンテストがあくまで「周囲との競争による相対評価」である以上,不確定要素はどうしても発生します。そのため,レートが落ちることが往々にしてあるというのは,ある意味,仕方のないことなのです。なので,レートが下がるたびにずっと現実と向き合い続けているようではとてもとても精神がもたない,と思うようになりました。よほどレートを上げることが緊急に迫っている場合*6でもなければ,AtCoderのコンテストは何回でも挑戦でき,挑戦回数が多くなったからペナルティがある,というわけでもないので,何回でも挑戦すればよい,と思うようになったのです。*7

レートが下がってもあまり気にせずに自分が今できることをし(問題を解き),コンテストに参加し,うまくハマってレートが上げられたら嬉しい,このような気持ちで臨むようになりました。

 

問題は,「いつ『うまくハマってレートが上げられ』るチャンスが回ってくるかは実際にやってみないとわからない」ということです。出られたはずのコンテストに参加せず,それが実際にはレートを上げられるチャンスだった場合,損をしている,ということになります。個人的に,それはとても勿体無いことをしている,と感じるようになったのです。コンテスト中に何が起こるか,それは本当にコンテストが始まってみないとわかりません。なので,レートを上げるチャンスを逃さないためには,「可能な限りコンテストには出る」,これが一番良いのだと思うようになりました。

AtCoder社長のchokudai(高橋直大)さんもあーだこーだー*8この動画の24:02あたり)で,「AtCoderのレーティングは,2回適正を取るより,1回上振れ引いて1回下振れ引くのほうが高くなるような仕組みになっている」とおっしゃっています。上振れというのは,それと同じ下振れを引いてもなおレートが高くなるほどの強さを持っている,ということになるのです。ちなみに私は,パフォーマンスに全然安定感が無く,レートの浮き沈みが激しいのですが,それでもレートを上げさせてくれるAtCoderのレーティングの仕組みは私にとって優しいものだったのかもしれないですね。

 

実際,うまくハマってレートが上がるタイミングは思いもよらないときに訪れました。私は2週間前の7/18のARCで茶パフォ412という物凄い破滅をやらかしてしまい,レートを大きく下げてしまいました。ただ,下がったものは仕方がない,その次でなるべく取り返そう,と思い,気を取り直して7/24のABCと7/25のARCに臨むことになります。しかし,ARCの翌朝には大学の期末試験が1科目。あまり競プロに現を抜かしてはいられません。取り敢えずレートはあまり気にしないでコンテストに出よう,と思って出ることにします。

すると,7/24のABCでパフォ2120という過去最高パフォを出し,謎に上振れを引いてしまいます。流石にその翌日7/25のARCは試験の前日で,クラスメイトもあまりARCに出る人はおらず,一応出るには出るけどあまりはっちゃけずに期待もせずにやろう,と思いました。試験前で精進の甘さが出てしまったのか,早速出だしが遅く,怪しいスタートとなりましたが,時間ギリギリで高難易度の問題を通せたのが決め手となり最終的に2000近いパフォを出し,ついにレート1600に到達。試験の前日にまさかの入青達成となってしまったのです。これにはまず自分がびっくりしたとともに,試験前日でもARCに出るという選択を取って良かったなと思えました。*9

f:id:Angry_Sad_Eight:20210731003239p:plain
レートはあるとき突然急に上がったりするものです。

このように,「失敗してもまた次がある」,という作戦で臨むぶん,コンテスト参加回数はかなり多くかかります。実際,水色になってから青になるまでに,私はRatedコンテストに58回出場しています。

私は,競プロの成長は周りに比べるとかなり遅いほうだと思っており,実際,私より早くにレートが伸びていく人はいます。(そういう人からは刺激をもらえることが多いです。)しかし,そういう人の真似をしようとしても自分は恐らくうまくはいかず,嫌になってしまうだけで終わってしまうだろうと思い,どんなに遅くても良いから確実にレートを伸ばしていこうと思ったのです。その結果,水色になってから1年かかってしまってはいるものの,青になることができました。青になれたことは節目の一つに過ぎないものではありますが,自分の今までやってきたことが間違っていたわけではないんだ,と自分の中で納得できたのは,青になれて良かったことの一つなのかなと思っています。

(「レートが下がってもあまり気にせず次があると思う」と口ではわかっていても,実際にはどうしてもレートを目の前に一喜一憂してしまうところが無いではなかったですし,そのような気持ちにはすごく同情します。くれぐれも無理はしないようにしましょう。)

おわりに

長々と話しましたが,結局何が言いたかったかというと

①精進はモチベ次第!ただし典型90問はやろう!

②コンテストに出て戦略を自分のものにしよう!順位表見るとかも有効!

③レートが下がっても仕方ない!いつかは上振れ引けるから頑張ろう!

といった感じでしょうか?

水色でいる期間が長く,青タッチまで行っても何度もレートを落とし続け,「本当に青になれるのか」と不安に思うことが無いわけではなかったですが,このように青になることができたのは,一つ競プロで自分に自信が持てたところだなと思っています。これがきっかけで競プロのモチベーションは間違いなく上がったと確信しています。これを機に,さらなる成長を目指して,頑張っていきたいと思っています。せっかく夏休みが始まるということがあって,競プロをやる時間も割と取れそうなので。

それでは。

*1:ちなみに,去年までずーーっとAtCoderのコンテストに登場しなかったですが,今年になってからやたらと頻出するようになりました。何があったのかな。

*2:その結果,解いた問題に全然出てこなかったダイクストラ法を水色中位くらいまで使ったことなかったのは内緒。

*3:私自身,不思議と典型90問に出てくるアルゴリズムは覚えようという気になりました。Grundy数,主客転倒テクニック,二部マッチング,燃やす埋める問題,強連結成分分解...... これらは競プロ典型90問がきっかけで覚える気になったアルゴリズムです。

*4:余談ですが,水色になったのが2020/7/25で,青になったのが2021/7/25なので,水色だった期間はちょうど1年らしいです。

*5:あるコンテストの問題セットをDiffでソートして並べたときに,ある2つの問題の間のDiffが大きいとき,その部分を「崖」と呼びます。例えば,6問の問題のDiffの色が「灰灰灰茶橙赤」だった場合,4問目と5問目の間に崖が出来ている,と言います。

*6:これもそうそう思いつきません。AtCoder Jobsを満足に利用したいから色変したい,というくらいでしょうか?

*7:ICPCなどの一発勝負系の大会はもちろん何回でも挑戦すればよい,という気持ちにはなりません。私自身,まだこういうのに出たことが無いので,どのような気持ちになるかは正直わからないもので......。

*8:不定期で開催されるYouTubeAtCoder公式生放送のことです。

*9:無理してまでコンテストに出ろと言ってるのではありません,後悔しないためにもテスト勉強もしましょう。