凡人でも入緑できました!(初投稿)

プロフィール

• 理系大学生
• pythonを初めて約1年
• 凡人です(緑になるのに50回以上参加しているので…)

使用言語

• 機械学習や深層学習にも興味があり、いずれkaggle等にも挑戦したいと考えていたためpythonを選択しました。
• 処理速度は灰~緑diff程度では気にすることはほとんどないと思います。
• python or pypy　みたいな知識を知っておく必要があるのが少し厄介でした

緑色の個人的なレベル感

• 最近のインフレにより、昔の問題と比べると同じdiffの場合の難易度は上がっているとは思います。
• chokudaiさんの記事に書いてあることは今でも的を得ていると思っています。

入茶した時の知識

• データ構造(連想配列,Heap,deque)
• 全探索(計算量を工夫する全探索,bit全探索,順列全探索)
• 累積和
• いもす法
• 尺取法
• DPの基本的な問題
• 2分探索(基本的なもの)
• 貪欲法
• ソート
• グラフの基本問題
• 数学の基本的知識

入緑した時の知識(+α)

• グラフアルゴリズム(bfs,dfs,dijkstra)
• データ構造(unionfind,順序付き集合)
• 多次元の動的計画法
• 2分探索(応用)
• ダブリング

正直、他にも最大流問題やセグメントツリー,最小共通祖先などのアルゴリズムにも手を出してはいますが、本番で使えるレベル(考察を踏まえて)ではないです。

また、知っている≠使えるなので、自分は習得するまでには4,5問は解かないと身につきませんでした。
実際、知識力+考察力+実装力の3つが揃って初めて問題が解けると考えているので、どれか一つでも欠けているとなかなか本番でACできなかったりします。

個人的アルゴリズム重要度ランキング

1. 2分探索(応用範囲がとても広く、頻出であるため)
2. 累積和(茶色diffでよく見る)
3. DP(基本的なdpは最近は茶diffなので...)

なぜ,入緑するのに半年も停滞してしまったのか

• 正直4月にレートが759になったとき、緑はすぐいけるだろうと油断していました。
  (今覚えば、過去の問題と類似してたラッキー問題やたまたま早解きが成功した上振れでした)
• 学業で忙しい(というの言い訳にしていた)ため、精進を全く行っておらず、週1回コンテスト参加のみを行なっていた
• 実装力不足(体系的にアルゴリズムの勉強をしたときに本番で使いこなせる気持ちになっていた)
• ミスがとても多い(色んな種類のミスをしてしまいます)

問題を解く上で心がけていること

• アルゴリズムベースで考えない
  新しいアルゴリズムを勉強すると、使える手札が増える一方で、問題の考察を疎かにしてしまうことがあったため。
• 20分考えてわからなかったら次の問題に飛ぶ(悩みすぎるとダメな思考回路になってしまうことがあるため)

レートを上げるためにやったこと

• 過去問精進

  • 正直これが1番大事だけど個人的には辛い作業
  • 本番の緊張感が好きなので、なかなかモチベが保てない

• 鉄則本

  • 6割ぐらいのページと問題を解いた
  • 体系的に競技プログラミングに関する知識を習得することができるので、レート400ぐらいの人に1番おすすめ(灰coderだと少しコードを理解するのに時間がかかると思うので、鹿本を勧めます)

• PAST試験

  • 2回受けましたが、両方ともあと一問というところが解けずギリギリ初級
  • 本番と同じような緊張感が味わえる(お金払っているので)ため、お金に余裕のある人にはおすすめ

• 知識を体系的にまとめる

  • 長期休みにipynb形式でチートシート的なものを作っていた
  • 昔解いた問題の振り返りが出来たり、理解していたつもりのアルゴリズムを再履修する機会になりました

• 問題分類

  • 解いた問題をグラフ問題やDP,データ構造などのフォルダに振り分けてます
  • コンテスト中も今まで解いた問題から、コードを引っ張ってくることが多いです

• 精錬100問、典型90問

  • 精錬の方は3割程度、典型90は~星4,5のうち理解出来たものを解説AC含めて7割程度埋めました
  • 鉄則本→典型90のステップで勉強していくと、かなり力がつきそうです。

モチベ維持のTIPS

• 競プロ友達を作る(twitterはスゴい人が多いのでただ眺めるだけになっています(悲しい))
• レートで一喜一憂(賛否ありますが、レートが上がるとモチベは確実に上がりますね)
• AC数を積み重ねる(精進グラフがレートより低い場合は、全体的に演習量がたりないと考えていいと思います)
• ライバルとレートを競う
• 一旦競プロから離れる(楽しむことが1番です)
• 競技プログラミングに参加している時点でスゴい!!!

精進の仕方について

• 自分よりも低いdiffの問題だけを解くのはあまりおすすめしません。(解くスピードは多少上がるかもしれませんが、長期的にみると、自分より一色高い難易度の問題を解けないといつまで経ってもレートが上がらないから)
• 個人的なおすすめは、自分のレート+半色の問題を解きつづけること
• 考察をガンガンプログラムの中に書き込む(これは精進のときは必ずやっています。)
• 20分考えて全くアイデアが浮かばなかったら解説を少し見ます。方針は合っているけど実装がうまくいかない場合は、出来る限り自分で解くようにしてます。

これから

• しばらくはunratedでコンテストに参加しようと思います(入水できるレベルの考察力が全然足りないから。あとレート下がるの怖い...:(
• 他にも,kaggleやヒューリスティックコンペ,ゲームAIなど興味があることがたくさんあり、そっちの方にも時間を割いていきたい
• 毎日1問は緑・水diffをACして鈍らないようにしたいです
• 過去問精進800AC超えたあたりで再びrated

をしていきたいです。

(記事というよりメモ書きみたいになってしまいました…。いいねしてくれると嬉しいです)