ひらめの日常

プログラミングと読書と

AtCoderで水色になるまでやったこと

2019/03/24のABC122で水色になりました.

自分が割と苦労して水色になったのと,同じようなブログがかなり参考になったので自分も書いてみようと思い,残しておきます .

茶に5ヶ月滞在,緑に4ヶ月滞在なので,その都度レートがそのままだと上がらないという状態だったように感じます.

f:id:thescript1210:20190325162007p:plain
レート遷移図

競プロ始めた時の自分

  • 工学部のB3(情報系とは明言できない学科)
  • Java/KotlinでAndroidアプリ開発を一年間やっていた.
  • Pythonあたりも機械学習周りで使っていた.
  • C言語系の知識はほぼなし.
  • 数学はとっても苦手.

基礎固め,灰→茶

ここはAtCoder解くだけならいらないかも知れません

Java競技プログラミングをやろうと思っていたので,AtCoderに参加すると同時にJavaアルゴリズムとデータ構造的な初歩的な内容を勉強しました.

定本Javaプログラマのためのアルゴリズムとデータ構造

定本Javaプログラマのためのアルゴリズムとデータ構造

それと同時に自分は図で何が起こっているのかを理解するタイプだったので,アルゴリズム図鑑を買って各種アルゴリズムがどのように動くのかイメージを理解しました.(すごくわかりやすい本です)

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

ここまでで以下のことを身につけました.しかし具体的に使えるかというとそうではありませんでした.

  • 計算量の概念
  • 各種ソートアルゴリズムとその計算量
  • スタック・キュー・ハッシュ・ヒープなどのデータ構造
  • 二分木の概念
  • 二分探索の概念
  • 深さ優先・幅優先・ダイクストラ法のイメージ

コンテストに参加するにあたって,入出力についてもちょっと勉強しました.

茶→緑の精進

最初は緑下位パフォが出たものの,回数を重ねるにつれてパフォが茶色になっていました.200点問題までは解けるのですが,300点の壁が非常に高かったです.

そこで本格的にアルゴリズムの勉強と,AtCoderの問題を解くことを始めました.具体的には以下のことを並行して行いました.

ここまででだいたい300点問題を30分ほどで解けるようになり,緑パフォが安定してきました.

一つ大きな疑問として,なぜC++に変えようと思ったのか?ということがありますが,これは完全に自分の気持ちです.

  • C言語系を勉強したかった.
  • アルゴリズムの教材にC++で書かれていたものが多かった.(別言語に変換するところで時間を取られるのは本質的ではないので,より多くの人間が使っているものを使うのがいいと考えました)
  • 実行速度が速い.(...正直水色までだったら大して問題にはなりません.)

緑→水の精進

ここでは300問題を早く解く + 失敗をなくす + たまに400点問題を解く.あたりが必要になってくるかと思います.

  • 400点問題埋めを始める.
  • ABCのセットのバチャを AtCoder Virtual Contest で立てて,きちんと緊張感持ってやる.
  • 苦手分野を集中的にやる.(自分はグラフ問題とか二分探索とかやってました.)

あとは本質的ではありませんが,早解きのためのtipsをためていきました. hiramekun.hatenablog.com

問題量をこなすと引き出しが増える + その引き出しを開くのが早くなるので,300点問題なら15分前後で解けるようになり,水色パフォが増えてきます.

水色になった時にはこれくらいの問題を解いていました

f:id:thescript1210:20190325173726p:plain
AtCoder Scores

ここまでで最終的にできるようになったことはだいたい以下のようなものです.

大事なこと

自分は何ができないのかを把握する

使っているアルゴリズム自体がわからないのか,それとも問題の解法自体が思いつかないのかによって違ってくると自分は思います. 前半がわからないなら蟻本やQiitaの記事で身につける.後半がわからないなら,ひたすら問題を解き,解説などもみて発想の過程を訓練するという感じでした.

復習大事

まず解説放送は聞いたほうがいいと思います.日本トップレベルの競プロerがどのような思考過程を経て解答にたどり着いているのかを,なんと無料で聞けるのですから聞かない手はありません.

そして,自力で解けるようになるまで間違えた問題は解き直しました.これは,一回解説放送などで聞いたはずの,自分より強い人たちの思考方法を追うことができますAtCoder Scores などを使って解けなかったの問題はお気に入り登録して解き直します.

ここはかなり大事だと思っていて,問題からアルゴリズムへの帰着に対する良い練習になりました.

焦らない

周りの人がすごいペースで問題解いていたりすぐに色が変わったりすると焦ります(自分が周りと比べて成長が遅かったので).自分のペースで,何より自分に合ったやり方で続けることが大事だと思います.

Twitter

同じくらいのレートの人や,自分より上のレートの人が,どのような精進をしているのか・何を考えているのかを知れて良いです.頑張っている人たちの様子が見れるので良い刺激とプレッシャーにもなります.