2回目の競プロ記事です
2021/08/21(土)までの競プロ状況を報告いたします。相変わらずAtCoderで素晴らしい成績が出ていません。しかし、Ratingは上がっています。自分なりに考えて実行した競プロ活動の振り返りを行い、共有いたします。
現状報告
AtCoderのrateが3桁になりました。やっとですね
やっと茶色のラインが見えてきました。しかし、今後Ratingが下がることもありえるので油断はできません
最近は何をやってるのか
前回のブログで紹介したAtCoder Problemsを解いています。2021/08/18(水)に easy 100 を全問見てみました。自力で全部解けませんでしたが、一通り取り組みました。
今は easy 100 の先に進み、 Medium 100 と新しく Recommendation に取り組んでいます。
easy100を経て変化はあったのか？
変化がありました。具体的には3つの変化がありました。
- データ構造と型の意識
- 問題慣れ
- 計算量の意識
個別に説明していきます。
1. データ構造と型の意識
非常に恥ずかしいのですが、配列と変数ぐらいしか頭に浮かんでいなかった自分ですが、easy100を解くうちにmap(連想配列)やset(順序付集合)を考えられるようになりました。特にmap(連想配列)は非常に強力です。これを知っているか知らないかで解ける問題の数が変わるのではないかと思います。
またデータの型も大事です。私はC++で競プロをやっているのですが、計算するうちにデータが扱えない大きさになりオーバーフローすることが多々ありました。「オーバーフロー」と検索すれば色々記事が出てくると思うのでそれを参考にしてください。
私は桁と型の感覚を覚えるためにMicrosoftの資料を参考にしました
2. 問題慣れ
これはその通りなのですが、問題を解き続けることで得られました。問題慣れを実感した例としてはこの問題に取り組んでいた時の話があります。
この問題(AtCoder Beginner Contest 214)
C - Distribution 問題文 N人のすぬけ君が円周上に並んでおり、反時計回りに 1,2,..,Nの番号がついています。 i(1≤i≤N)番目のすぬけ君は時刻 tに宝石をもらうとSi単位時間後、すなわち時刻 t+Siにその宝石を (i+1)番目のすぬけ君に渡します。ただし、(N+1)番目のすぬけ君とは 1番目のすぬけ君のことを指すとします。 また、高橋君は時刻 Ti に i 番目のすぬけ君に宝石を渡します。 全ての i(1≤i≤N) について、i 番目のすぬけ君が初めて宝石をもらう時刻を求めてください。なお、宝石の受け渡しにかかる時間は無視できるものとします。
円状というキーワードだけで自分は『mod計算が使えるかも』と考えられました。この問題は最近の問題なのでeasy100には入っていませんが、似た問題はありました。AtCoderの問題に慣れてきたので新しい問題を見た時でも『あの時解いたあの問題の解法が利用できるかも』と思えるようになりました。
競プロは習うより慣れろかもしれません。 毎日1問でも良いので継続し、しっかりと解法を理解すれば知識は溜まっていくと思います
3. 計算量の意識
AtCoder Beginner Contest(ABC)のC問題からは計算量というものを意識する必要があると考えています。
easy100を解いていてなんとなくわかってきた計算量を減らす方法
1.エラトステネスの篩(素数の列挙) 2.累積和 3.動的計画法
まだまだ片手で数えられる数しかパッと出てきません。簡単なアルゴリズムをより素早く頭の中から取り出せる訓練とより複雑なアルゴリズムを組み立てる力が欲しいです。
また、計算量を意識できるようになったので『この回答だとTLE(制限時間切れ)になるな。もっと工夫した回答を作成しないと』と実装していく中でわかってきます。データ構造を意識するきっかけにもなりました
今後の予定
ついに3桁に突入ということで茶色目指してより一層精進をしていきます。
また、問題のパターンに触れていくためにCodeforcesも参加しています。英語の問題文ですし、開催時間も深夜なので大変ですが、やはり自分はプログラミングで問題を解くのが好きです。もちろん自分は社会人(社畜)で「業務優先」なので無理のない範囲でやります。
AtCoderに限らず、Codeforcesの精進記事も書いて行けたら幸いです。
