shuのブログ

好きな時に好きなこと書くブログです。

【2021年】新年の目標

あけましておめでとうございます!

2021年が始まって数日が経ってしまいましたが,今年の目標を記しておこうと思います.一年後に振り返りやすい場所に書いておこうと思いました.

 

目標

競プロ

  • 年度内に緑コーダー【達成:4/18】
  • 年内に水色コーダー

その他

  • ポートフォリオサイト作り
  • 曲作り
  • 動画作り
  • TOEIC600 over
  • 基本情報【達成:4/27】

今年はいろいろ国内旅行したいですね〜

今年も気楽にゆるゆるといきましょう

 

自分へ

ちょいちょい確認しに来てると思うけど,達成できているかはあんま重要じゃないので途中までやったのか,どこまで進んだか目標の修正に使ってください.これで辛くなるならやめてもいいのでw

 

最近の精進と反省会とおすすめ

色変記事を書いてひと月ぐらい経ったので、最近の勉強についてまとめたいと思います。プラスで、最近停滞気味なので今の気持ちと反省を残しておきます。最後には、近況として好きなことを書いてます。

 

 

最近の精進

ここ最近は、相変わらず茶色、緑の問題を地道に解いています。加えて、レッドコーダーが教えるシリーズ中級編のQiita記事の精選100問も解き進めています。難しい問題は、後回しにしてできるだけ解説読まずに時間かけてでもACしようと頑張ってます。

qiita.com

新たに勉強しているアルゴリズムとしては、DFS・BFS・ダイクストラ法です。ここら辺を中心に木の持ち方だったり、実装の仕方を学んでいます。応用が効くようになるまでにはまだまだ時間がかかりそうです。

DPの勉強も進めたいと思っていて、実際に問題を眺めて解説も見ながら取り組んではいるのですが、いまいち自分の中でしっくり来ていない部分が多く、コンテストには頻出で重要項目なのは承知の上でじっくり時間を掛けながら進めています。

最近のABCでは、自分にとって非常に教育的でいい問題が多くコンテスト中に調べて勉強して通すことやコンテスト後に復習することも多いです。特にABC183, 184はいもす法やマージテク、マンハッタン距離・チェビシェフ距離、確率DP、半分全列挙など勉強するいい題材をもらってる感じで非常に楽しいです。

 いもす法

これはABC中にサイト検索したら、例題と問題がほぼ一緒だったのですぐACできました。応用や使える問題の例も下のサイトで紹介されているのでみんなで練習しましょう。

imoz.jp

マンハッタン距離・チェビシェフ距離

先日出題されたSuper Ryumaは、茶diffでもなかなか難しい問題でしたが、自分としては解けないとダメだったなと感じています。その理由がこの問題。

atcoder.jp

解いたときに分からなくて、解説読んでACしたんですが、結果的に身についてませんでした。問題を見てマンハッタン距離しか出てきてなくね?と思ったあなたチェビシェフ距離との関係も調べましょう。必ずしも使わなきゃ解けない問題ではないですが、その発想を覚えておくことも大事だと思ってます。

確率DP

これを参考にしてます。ネットで拾った北大の競プロerの方のプレゼン資料?です。

https://compro.tsutaj.com//archive/180220_probability_dp.pdf

 

こんな感じで勉強に活用しているものをまとめてみました。

後もう一つ進めていることがライブラリの整理です。ある程度分量のある実装が必要なアルゴリズムや頻繁に使うようなものを参照しやすいようにGithubを使ってまとめています。けんちょんさんのライブラリを参考にしながら、徐々に充実させようと思っています。現状では、約数列挙やDFS・BFS、二分探索、UnionFindなどを整理しました。素数判定や素因数分解なども近いうちに整理したいですね。

反省

ここは個人的な反省です。

最近停滞気味なんで反省を書き記しておきます。ここ2週間は、いらない勘違いをして解法があっているのにACまで結び付けられないという事態が発生しています。一つ目は、long long型で 10^{18}を受け取れないと勘違いしたせいで合っていた解法を変えてしまう、もう一つは、問題文をよく読んでいなくて、余計な制約を付け加えて考えていたせいで場合分けを一つし損なってしまう、というものでした。型の受け取れる最大値はlong long以外のものも一度しっかり確認しました。そして自分がしたミスをHackMDのメモにまとめてコンテスト中詰まったり悩んだら見ることにしました。そしてそして、詰まったときには1文字1文字問題文を読み返すのもコンテスト中冷静さを取り戻すために必要なことだと感じています。

最近のミスは、しょうもなすぎて心にきていますが、精進ができていないわけではなく確実に難易度の高い問題も徐々にですが解けるようになってきている感覚はあるので次のコンテストにつながるようにしていきたいですね。

後、使っているメモツールも悩んでいるところです。github, HackMD, Scrapboxを復習や知識整理に利用しているのですが、だんだん煩雑になってきたのでそこの整理もしなきゃなと思っています。皆さんはどんなツールを使っているんでしょうか?数式(Tex)とソースコードがまとめられてどの端末からもアクセスできるツールって限られている感じもするんですが。。。

近況

ここからは、競プロ関係ないです。

最近ハマってるYouTubeが「週末養蜂ちゃんねる」です。

www.youtube.com

ニホンミツバチの養蜂をしている方の動画で、蜂の巣の構造きれいだな〜とか思って見てます。蜂たちがせっせと蜜を集めている様子やはちみつを取っている様子がなんでか見てしまいます。将来ニホンミツバチの養蜂するのもいいな〜なんて。(勘違いされても困るので、私は基本的に虫は嫌いですw)

 

もう一つ、最近ハマってるバンド。昔から知っていたバンドではあるんですが、最近また聴くようになって「F1RST TAKE」で公開されているバンド演奏は結構な頻度で見てます。聴いたことない人におすすめな曲は、「Mela!」、「Shout Baby」、「sabotage」。ポップで聴きやすいと思います!ボーカルの歌うますぎぃ!!

ライブとCD音源で演奏を変えているようなので、比較すると楽しんで聴けます。

www.youtube.com

AtCoderで茶色になった

AtCoderで競プロを始めて約2ヶ月、2020/11/01 のABC181で茶色になったのでブログ書きます。自己紹介をしつつ、これまでどう勉強したのかまとめてみました。

 

f:id:shu8Cream:20201102200230p:plain

現在のレート

 

 自己紹介

職業:大学4年(情報系)

競プロ歴:約2ヶ月(20/09/13開始)

使用言語:C++

生息地:shu (@shu8Cream) | Twitter

twitter.com

大学で勉強したことも触れつつまとめてるので参考になったら嬉しいです。

僕の簡単なスペックとしては、プログラミング力は、自分ではよくわからないので大学の成績をあげると真ん中ぐらい、なのでそんな程度だと思ってます。数学力としては、大学受験でいうとセンター数学IA・IIBともに9割以上で2次試験も数学で戦ってた感じはあります。競プロ界隈では数強の方も多いので自分が数強だとは言えないですが、数学は好きで趣味程度に楽しんでます。

レートについて

競プロ界隈にいると上にいる方々が凄すぎて、自分なんてという気持ちが強くなるんですが、茶色も凄いぞって感じで褒めてくれたり、評価していただけると僕が嬉しいです。

正直、茶色の難易度の問題でも本番で解けないことも多々あります。スピードも実装力が求められる問題だとかなり時間がかかったり、数学でゴリ押せる問題だと似たようなレートの中でもかなり早く解けたりするのでまだまだ不安定な部分もあります。

 AtCoderでのレート

レート 補足
1600~1999 なれたらいいな
1200~1599 ここになりたい
800~1199 次の目標
400~799 現在地(427)
0~399 戻ることはないようにしたい
未参加  

 目標としてはこんな感じで最終的には水色を目指しています。青にもなれたらいいですが、今のところ現実味がないです。

茶色コーダーになるためにやったこと

競プロの取り組み方

まずは、AtCoder Problemsの記録をみてもらうのがわかりやすいと思うので載せときます。

 

f:id:shu8Cream:20201102200600p:plain

Streak

f:id:shu8Cream:20201102200459p:plain

解いた問題

こんな感じですね・・・って言ってしまったらこの記事終わるのでちゃんと説明します。解いた問題数は画像の通りなんですが、はじめ頑張っていたのは以下の3つです。

  • 本番の形式に慣れる(バチャコン参加)
  • 灰問題をひたすら解く
  • うーんと悩んで解けるぐらいの問題を毎日一問

僕は実装力が無いと思っているのでひたすらコードを書く事を意識しました。あとは、APG4bで解説されるようなSTL関数やSTLのコンテナは本当によく使うので、実際の問題で試しまくりました。慣れると「この問題set使えるな」とかすぐ頭に浮かぶようになりました。

覚えたこと

  • 線形探索
  • bit全探索
  • 二分探索
  • 累積和
  • Union Find
  • (modint)

意識して覚えたのはこんなところです。どれにしても応用の難しい問題は解ける気はしてないです。とりあえず理解して基礎問題は取れるぐらいにしました。最後のmodintはACLにありますが、使い方覚えていた方が圧倒的に便利です。

 

大学でやったこと

初めにも触れましたが、情報系の大学にいるため嫌でもアルゴリズムやデータ構造は勉強しました。ここにまとめるために残ってた授業資料見直したんですが、強くなるために必要そうなものは網羅されてそうでした(もう覚えてないけど)。

出す順番が無茶苦茶ですが、一通り知っているので改めて勉強するにも取り組みやすかったです。まだ復習できていないものに関してもそうだと思います。ただ問題は実装がちゃんとできるのか、これが大きい問題で僕自身の課題です。地道にやっていこうと思います。

目標とこれからやりたいこと

入茶したので今後の当分の目標はです。期間は年内までに、と言いたいところですがそんな甘く無いと思うので年度内までに入緑できるよう精進したいと思います。

具体的にこれから取り組みたいことと言えば、

  • 高校数学の場合の数、確率+数列の復習
  • DPの勉強(EDPC)
  • けんちょんさんの本を読み進める(現在DP頑張ってます)
  • 茶diff埋め

こんな感じです。競プロ勢のみなさん数学が得意な方もいっぱいいると思いますが、僕は色々抜け落ちている部分があるので高校数学の復習をしたいと思っています。そして、DPは慣れというのも見聞きするんですが、ひたすら精進あるのみですね。最後に茶問題を解ききろう!って感じです。

茶色コーダーのみなさん一緒に頑張りましょう!

おすすめの本

以前から持っていた本や読んだ本をいくつかまとめておきます。

 プログラマの数学

https://amzn.to/34vQe0B

数学ガール』シリーズを書いている結城浩さんの本でプログラミングに役立つ数学の知識がわかりやすくまとめられています。ソースコードが多く載っているわけではないので、これだけですぐ競プロに使えるほどではないですが、論理・剰余・順列・再帰など高校数学の復習知識やプログラミングする上で大事な基礎の考え方がまとまっています。けんちょんさんの本(一つ下で説明)もいきなりだと難しそうと感じる人は読んでみるといいと思います。数学に苦手意識のある競プロerは『数学ガール』シリーズもおすすめです。(ただ僕が好きなだけ)

問題解決力を鍛える!アルゴリズムとデータ構造

https://amzn.to/3rfPGFS

僕が説明するまでもないと思いますが、けんちょんさんの本です。実際の競プロで役立つ知識満載の競プロerなら買いの一冊だと思います。本格的に競プロで戦っていくために学ぶべきものが詰まっています。競プロ本として有名な蟻本だとちょっとむずくて厳しいと感じる人はこの本から始めるといいかもしれません。(こんなふうに紹介してる方が結構います)僕は「蟻本むずそうだな〜」と手を出そうか迷ってる時にこの本が出版されたのですぐ買いました。

まとめ

以上が入茶するまでにやっていたことです。初めてブログを書いたので拙い文章ではあったと思いますが、ここまで読んで下さりありがとうございます。今後も気が向いた時に書いていこうと思うので僕のTwitterで動向を見ていただけると嬉しいです。