shibak333333n

移転しました→　https://shibaken28.github.io/my-blog-4/

水色になりました【色変記事】

AtCoder 競技プログラミング 色変記事

はじめに

初参加から13ヶ月，48回目に参加したARC109で水色コーダーになりました．

めちゃくちゃ嬉しいです．

この記事は自分語りと自己満足で成り立っています．お役立ち情報は......高確率で，ないです．

自己紹介

とある高専の情報科二年生です．

数学が好きで得意な方かと思っていましたが，AtCoderをやっていると，どうもそんなことは井の中の蛙でしかないことがよくわかります．

学校でアルゴリズムはまだ学んでいないので，情報科であることは実力にあまり関係がないです．

このくらい解いたよ

水色になるまで48回もコンテストに出たわけですが，他の方の色変記事をみるとだいぶ回数が多く感じます．

少し複雑な気持ちです．

いや，いくら時間がかかっても水色は水色だ，喜べ！！

思い出話

思い出とともにどんなことを学んだかを紹介します．

初めた

部活の先輩にAtCoderってのがあるよーって教えてもらったのがきっかけです．

自分のプログラミング能力がどのくらいあるのか純粋に知りたかったので参加してみたいなと思いました．

ある日突然AtCoderの存在を思い出し，ABC144に滑り込みをして1完しました．パフォーマンスは16でした．

終了直後にBは解けたので，C問題を解くのを目標に過去問を漁りはじめました．

この頃はよく愚直な実装をしてTLEを出して唸ってました．

atcoder.jp

この問題のように灰dif(52)でも計算量の見積もりを要求してくることがあります．

全探索するにも，累積和するにも，計算量はついてくるので早めに知っておくべきです．

計算量はC++入門 AtCoder Programming Guide for beginners (APG4b) - AtCoderや，けんちょんさんの記事で学ぶのがおすすめです．

茶色になるまで

その後，3完が安定する頃に茶色になりました．

始めてから3ヶ月半です．

このころやっていたのは過去問埋めとアルゴリズムを学ぶことです．

この頃，じっくり考えないとわからない，というのが普通だということを知りました．

というのも初めた頃は少し考えて「あーこんなん無理だろ」と思ったらすぐに撤退していたし，解ける人はちょっと考えればわかるんだろうなと思っていました．

初心者の頃はすぐ撤退しがちな気がします．

なんにもわからないけどとりあえず手元で実験する，という問題への取り組み方を知りました．

ここで，ABC-Cの傾向について説明します．

ABC-C問題は，

  • 複雑な全探索の問題
  • アルゴリズムそのまま使うタイプの典型問題
  • 数学的，論理的思考力を要求する問題

の三種類が主です．

全探索

まず重要なのは全探索です．

「全探索」と一括りにされていますが，bit全探索や順列列挙などと様々なことが要求されています．

「全探索？for文いくつか使ってぐるぐる回せばいいんでしょ？」と言って全探索の勉強をスキップするのは危険です．僕がそれでした．

また，多くのアルゴリズムは，全探索では時間がかかるので無駄な計算を省くことができないか，という考えで使われているので

「全探索めっちゃ大事！」

です．

よくある全探索の例を挙げます．

  • bit全探索
  • 順列列挙，組み合わせ列挙
  • A+B+C=Nを満たすA,B,Cを求める問題でAとBだけfor文で回してC=N-A-Bとする

全探索の問題の例です．

atcoder.jp

atcoder.jp

atcoder.jp

典型アルゴリズム

最近は典型問題なら有名なアルゴリズムを使うものであっても茶difになる傾向があります．

最近はさらに顕著になったことで茶色のレベルが上がってると思っています．

D - FriendsやD - Water Heaterは有名アルゴリズムほぼそのままなので茶色difとなっています．

よくみるアルゴリズムとしては，

  • 貪欲法
  • UnionFind
  • 累積和
  • いもす法

が挙げれらます．

ネットにはいい記事がありますので，そこでアルゴリズムを理解したり類題を解いてみれば身につくと思います．

学んだアルゴリズムがちょうどコンテストで出題されると嬉しいです．

数学的論理的思考力を要求する問題

一番厄介なのがこれです．僕もこれは今でも苦手です．

下に問題の例を挙げます．

atcoder.jp

この問題はただの数学です．これが茶色difとか恐ろしいです．持ち前の数学力で殴れる人が羨ましいです．

atcoder.jp

場合分けなどの$O(1)$問題もよく出ますね．

このような問題に対して，僕は過去問で訓練しまくることでどうしかしました．投げ遣りな説明でごめんなさい．

緑になるまで

緑になるまでも普通に長かったです．このときもガッツポーズをして叫んでました．

この頃にはだいたいの基本的なアルゴリズムが身についていました．

ここら辺のレートからを伸ばすのに必要なのは，いわゆる考察ガチャのガチャの中身を増やすことが大事だと感じます．

例えば，「余事象を考える」や「後ろから考える」といった発想です．僕は頭が硬くてもこの発想をいつでも引き出せるように，メモをしました．そして，詰まったらそのメモを見るようにしました．

レート1000停滞期

ABC175からABC180の間にレートは浮き沈みし，結局22しか上がりませんでした．レートがあがらねぇ．

何かを理解する

レートが上がらずに無になってきた頃，ARC106,107で突然二連続水パフォがでました．水パフォはたまに出るのでたまたま得意なセットが来たからかと思いましたが，その後も1367,1148,1452という良いパフォーマンスでレートが1198まで上がりました．

別に激精進したわけではなく，正直よくわからないです(は?)．コンテストに出まくったから説が有力です．

入水

ARC108に，入水間近のレート1198のときに参加しました．

しかしAtCoderと人々は無情で，B問題が解けず，1完400パフォを突き出され僕は撃沈しました．

レートが本質ではないのはわかっていますが，レートは50下がり入水圏内からも離れ絶望です．

このような寸止めを多く経験することでメンタルが鍛えられた気がします．

まあでもやっぱり，レートが下がると辛いです．

その後，3回コンテストにでてようやく水色になりました．

大切なこと

とにかくコンテストに出る

「精進をしていない」とか「レートを下げたくない」といった口実でコンテストに出ないのはもったいないです．

僕がよくいうのは「欲しいのはレートではなく経験」です．コンテストに出るとじっくり考える時間が与えられるので良いです．

じっくり考えれば考えるほど，解答がよく染みます．

AGCは色が灰〜緑の人は早解き勝負になり，とくに茶，緑の人の人には出るのにはリスクが高く，出るのに躊躇しがちでしたが最近はrated1200~になったので安心です．

レートを気にせず参加することができます．

Twitter

一緒に取り組む人がいるのはとても大事です．

他の人から刺激を受けることやモチベーションに繋がります．

AtCoderをやっていれば，AtCoderをやっている人は大抵フォロバしてくれるのでどんどんフォローします．

コンテスト後の余韻はTwitterがあるからこそ浸ることができます．

あと，色が変わっていいねがたくさんくると嬉しいですね(承認欲求の塊)．

周りを気にしすぎない

僕は色変記事にどんなこと書くかを調べるためにいくつかの記事を見ましたが，点が少なくてかくかくしているスカスカなレートのグラフをたくさん見て劣等感を感じました．気にしすぎないようにします．

人は競プロだけじゃないです．

競プロやって良かったこと(2021/2/23追記)

ある種の発想力が得られる，鍛えられる

一見実装が大変そうに見える問題(C - Digital Graffiti)でも，実はループを回すだけで簡単に解けます．自分で思いつかなくても，その発想を覚えていくことはできますので，どんどん発想をためていくことができます．

実装力が身につく

例えば，C - Kaprekar Numberこの問題は数字自体をソート(8128なら，各位の数を小さい順に並べ1288)しますが，この処理は決して簡単ではないです．「数字を文字列にして一文字ずつに分ける」ことや，「数字を小さい順にくっつける」ことは僕が競技プログラミングを始めたときもそうでしたが，それらは長い考察の末に思いつく方法だと思います．しかし，競プロに慣れてくるとこのような発想は自然で，実装もすぐにスラスラできるようになりました．難しいアルゴリズムを実装できることが注目されがちですが，ABCのAB問題あたりの実装が難なくできる点は大きいと思います．

感想

なんだかまとまりのない記事になってしまいました．文章力がないです．

趣味でやっていることですが，こうした努力が客観的に水色という形で評価されて嬉しいです．

AtCoderは楽しいので，続けます．次の目標は青です．今のところ青になれる見込みは全くないですが気長に頑張ります．