水色になりました

f:id:dzon1682392:20220122144954p:plain

先週のABC235でRatingが1200台に到達し、ランクが緑色から水色になりました。 色が変わると記事を書く風習がどうやらあるらしいので、駄文ながら色変記事を書きます。

精進内容

書いたのが色変してから１週間後なので直後とは多少差がありますが、このような感じです。

だいたい400問近く解いています。そこそこ問題を解いてきているつもりですが、そんなにたくさん埋めているわけではないです。

 

コンテスト初参加が7月中旬なので、その前に少しだけ問題を解いています。当初はFまで解けるようになってから参加しようと思っていたのですが、今になると本当に無謀な願望を抱いていたなあと。ただそのおかげで図らずも２回目で水diffを出してしまい、結果として自信がついてモチベーションの維持に繋がっています。

勉強したもの

友人の入水記事↓で重要度順に書いてあってわかりやすかったので自分もやってみようと思いましたが、どう書いてもその劣化版になりそうなので、ここでは自分の到達度レベルとちょっと感想を書く程度にします。

というより、友人の入水記事がかなり丁寧で学んできたサイトなども書いてあるのでおすすめです。

lorent-kyopro.hatenablog.com

入緑時点でのメモも残っていたので、入緑時点と入水時点で自分がどれくらい使えたかについて書きます。

☆：スムーズに使える

◎：完璧ではないが使える

○：調べたら多分使える

△：勉強したことある程度

－：なんも分からない

基本的なデータ構造や型の理解：緑☆~水☆~

・vector、string、pair...☆☆

・map、set、queue...◎☆

・priority_queue、multiset...○◎

・stack構造過去問含めて使ったことない...

for loop、if文、while文：緑☆水☆

文字列処理：緑☆水☆

・文字コードについても勉強すると幸せになります

modint：緑◎~水☆~

・基本的な計算：緑◎水☆

・逆元：緑△水○

・逆元未実装です...

・群論の復習がてらフェルマーの小定理を勉強しなおしたいです

場合の数・組み合わせ・確率・期待値：緑☆水☆

深さ優先探索(DFS)：緑☆水☆

・いろいろなところで使えますが、最近本当によく見かけますね

幅優先探索(BFS)：緑☆水☆

・DFSとBFSでどちらでも解ける場合、個人的にはこっちをよく使っています

動的計画法(DP)：緑☆~水☆~

・まだまだ苦手です

・漸化式を作るので、その値に関係するのが定数個分になってそれより前の結果は関係なくなるような遷移の仕方を考えなくてはならず、どうしたらそれをすぐに見抜けるのかな〜と思っています

・ナップサックDP：緑◎水☆

・配るDP：緑○水◎

・メモ化再帰：緑○水○

・ゲームDP：緑△水△

・最長増加部分列：緑－水○

・桁DP：緑－水△

・文字列DP：緑－水△

・bitDP：緑－水△

分割統治法：緑☆~水☆~

・std::sort関数：緑☆水☆

・分割統治法：緑○水◎

二分探索：緑☆~○水☆~

・lower_bound、upper_bound関数：緑☆水☆

・具体的な実装：緑○水○

累積和：緑☆水☆

素数試し割り、素因数分解：緑☆水☆

Union-Find-Tree：緑◎水☆

・最近めちゃくちゃ出てきていますね、これそのものではなくこれの仕組みが背景にある問題とかも出てきていてかなり重要です

互除法、GCD：緑◎水☆

繰り返し２乗法：緑△水☆

・最近になってmod付きのをライブラリに加えましたが、0^0が0か1かどっちになっているかを把握しておらずに使って詰んだことがあります

イテレータ：緑◎水◎

bit演算子の理解：緑◎水◎

・上記の友人の入水記事には

　　・a^a==0

　　・a^b <= a+b(等号成立は、右辺の繰り上がりのないとき)

とありますが、他にも

　　・a^b^b==a

も使えるかと

尺取法：緑○水◎

ラムダ式：緑○水◎

区間スケジュール問題：緑○水◎

Kruskal法：緑○水◎

imos法：緑－水◎

bit全探索：緑－水◎

順列全探索：緑－水◎

Warshall-Floyd法：緑○水○

Dijkstra法：緑△水○

01-BFS：緑△水○

Fenwick-Tree：緑△水△

Segment-Tree：緑－水△

Lazy-Segment-Tree：緑－水△

全方位木：緑－水△

エラトステネスの篩：緑－水－

・これ入水まで名前と計算量くらいしか知らなくて、入水後に解いた問題で初めて使いました

強連結成分分解：緑－水－

・概念自体は知っていましたが実装の仕方を知ったのはつい先日です、実装方法見た時頭いいなあと感動しました

コメント

ここの部分は思考の整理のために私の個人的な感想や自分の場合のことを勝手にただただ書き連ねているだけなので、ここを読む際は、ただただ無意味なことが書いてあると思っていただき、決して書いてあることを鵜呑みにしないでください。

最近の傾向について

上に勉強した内容を書き連ねましたが、水色に到達したにしては理解している、特にその中でも覚えているアルゴリズムやデータ構造がかなり少ないです。

それでもこうして水色に到達したのですが、少し前の過去問と比較して最近の水色レベルまでの問題は必要な知識がけっこう絞られており、あまりアルゴリズムを知らなくとも水色パフォーマンスを出せる問題セットが多いなあと思っています。

ただその代わり、一見解き方がわかりにくい問題が多く、特に計算量をヒントにしていかに見抜いて基本的な問題に落とし込めるかといった問題(ARCのAやB問題じみたもの)が多くなっている印象があります。(多分)

上記の友人の記事でまず全探索する癖をつけることがついたのが有効だったと書いてあり、最近の問題だと特にそういうアプローチで取り組むことが大事になってきており、計算量の制約から全探索できることを判断させる問題がとても多い印象です。

私は幸いにも友人の記事を読んで全探索を意識して取り組むことができましたし、もともとABCよりARCの方が得意でしたのであんまりそのあたりの問題でズタボロになることはありませんでしたが、入緑、入水するには知っているアルゴリズムの数というよりいかに限られたアルゴリズムの性質を理解しているかということが重要になっているなあと思っています。

問題への取り組み方について

私が主に解いているレベルの問題に関しては、その問題に対する解き方、および発想のポイントをきちんと身につけることが一番大事だと思っています。

私の場合は、解けない問題を１から考え出せるまで放置して悩み続けるより、解説を読んで背景やそれを使う気持ちを学ぶ方が結果的に早くいろいろなことが身に付くのではと思っているので、解説を見て復習することを大事にしています。

むしろ、私の場合だと勉強したその場の理解度よりも１ヶ月くらい放置した後に軽く見直した時の理解度の方がよっぽど高いということが多く、勉強した当時はまっさらな状態から学ぶのでなかなか考え方の基礎から受け入れづらく思っていたことも、放置することで考え方の基礎が記憶に残り、再度学ぶ際ある意味前提として捉えられ、順序立てて考えることができるようになるという状況になっているので、(個人的には復習大の苦手なのですが)復習メインの方向が私に合っていると思っています。

私の場合以下の通りに対応するようにすることを目標としています。(目標なのでちゃんとやっていないこともあります())

  •  ある程度時間が経って分からないorかなり時間をかけて解いた
    •  解説を見る
      • 解説を見てわかるなら
        • 一回正しいコードを書いてみる
      • 解説を見てわからないなら
        • 他の人のコードを参照して一回写経してみる
    • 復習リストにいれる
    • 解き方がすぐに思い出せなくなった頃にもう一回解く
      • 難なく解けたら
        • 他の人のコードと比較し、改善点を見つける
      • 時間がかなりかかるorわからない
        • 再度復習リストに入れる

本当にわからない場合は、何か明確な目的、および期待できる成果があるならば、一回写経してみるのは全然ありという持論です。私の場合はその問題をある種典型とみなして考えた方が良いと判断した場合はいったん写経するのも手段の１つに入れます。

ただ、もちろんそれだけでは意味がないので、写経しながら今書いている部分がどういう意味を持っていてどういう発想で書かれているかを常に意識する必要はあります。それがなければ意味はありません。

このように考えながら写経した後に自分のコードで書く、というのも私は１つの手だと思っています。

ただ、例えばこのdiffの問題の複雑さを体験する、とか難易度的に理解可能な典型的な考え方があるはずだからそれを見つけ出す、といった明確で、かつある程度成果が保証されるなら手段として取ってものではと思っているので、無闇矢鱈にやるのは当然問題の無駄だと思っています。

また、最終的には難なく解けることが目標ですので、レート帯の割に時間がかかってしまった問題についても不正解の問題とほぼ同等に扱うようにしています。

今後の目標

競プロを始めた当初はとりあえず水色には到達したいと思っていたので今回で１つの大きな目標は達成できました。ただ、達したら達したでまだまだいろいろなことを書けるようになりたいと思っていますし、研究のことを考えると青色ないし黄色レベルのアルゴリズム力があった方が良い気がしているので、時間は非常にかかりそうですがまずは青色を目指して頑張りたいと思っています。

短期的な目標としては

  • 典型90問をマスターする
  • 復習リストを早く消化する
  • 基本的なアルゴリズムを仕組みから覚える

といったところです。

１つ目については、私は典型力が弱い方だと思っているので、これからはこれをやることが力になってくるのではないかなと思っています。最近はアルゴリズムの理解・応用が大事になってきているとは申し上げましたが、ここまででその考え方はだいぶできるようになってきたと思っていてそろそろインプットに力を入れたいですし、知識重視に変わったときに対応できるようにもしたいですので。

２つ目については上述したとおりで早く忘れた頃のを消化してものにしたいです。

３つ目については深く理解したいというのと単純になんだかよくわからずに道具として使っているのが嫌だからちゃんと理解したいと思っていることからです。時間があるならAOJでデータ構造の問題があるので、C++ではなくCで実装してできるようになりたいです。

おわりに

取り留めのない無責任なことを書き連ねていて見苦しい文章でしたが、ここまでお付き合いしてくださりまことにありがとうございました。