Study

AtCorderをやりはじめて1ヶ月過ぎてからわかったこと

競技プログラミングをはじめて1ヶ月半ぐらい経ちました。

万年、灰色の最下層にいる私ですが、それでもAtCorderについてわかったことがいくつかあります。今回は、競プロをはじめたころには、わからなかったことをまとめてみたいと思います。

もしかしたら、競プロをはじめて1,2ぐらいの人には参考になるかもしれません。

過去問サイトはヒートマップで進捗管理にも使える

有志で(?)作成されている、過去問一覧のページがあります。

https://kenkoooo.com/atcoder/

私はずっと、このページはただの過去問のリンク集だと思っていました。

でも、左上の”User ID”の入力欄に、自分のIDを入れれば自分の回答状況がヒートマップで表示されます。

この機能、全然知りませんでした。これで自分の勉強の進捗管理やモチベーション維持にも使えそうですね。色の詳細はわかりませんが、緑はPASSした、黄色は提出したけどPASSできていない、白は提出していないということでしょうか。濃い緑や黄色は、本番で提出したもののようです。

実は自分でスプレッドシートでヒートマップを作成して勉強の進捗管理をし始めてから、このサイトのこの機能に気がつきました。

このサイトよりもう少し詳細に色分けしたいのと、アルゴリズムや自分の状況のメモなどを残したいので、スプレッドシートでの管理も続けるつもりです。

計算量という概念

競プロをはじめたころ、計算量の概念がわかりませんでした。

O(n)が出てきても何じゃこりゃ? って感じでした。しかし、C問題で全探索やってもTimeOverになることがわかってきて、計算量についても意識するようになりました。

O(n)は、計算量の書き方で、nはループ回数です。厳密には違うかもしれませんが、この認識で解説ページとかは理解できると思います。つまりO(1)はループなし、O(5)はループ5回ということになります。Pythonだと以下の様なコードになります。

for i in range(5):
    print(i)

で、たまに解説ページにO(logN)とかO(NlogN)とか出てくるのですが、これはまだよくわかっていません。(数学でlogってやった気がするけど、全然覚えていない・・・💧) 特定のアルゴリズムを使ったときは、この計算量になるようです。 こちらのページによるとlogNは無視して良い小ささ、NlogNはNより少し大きいぐらいの認識で良さそうです。

で、肝要なのは、AtCorderでTimeOverしない計算量は

  • O(2 * 10^6)
  • O(10^5 log 10^5)

ぐらいのようです。

当然ですが、自分で書くforループのほか、配列やタプルの組み込み関数にも計算量はかかっています。競プロで使用する主要な組み込み関数の計算量はこちらにまとまっています。
https://qiita.com/Hironsan/items/68161ee16b1c9d7b25fb

C++がわからなくても何とかなる

競プロのメイン言語はC++です。本家解説や蟻本などの有名本は、すべてC++で書かれています。

なので、競プロのトップレイヤーまで上り詰めたいと考えている人には、C++は必須と言えるかと思います。ただ趣味として、水色を目指すぐらいなら、Pythonでも十分そうです。

ググれば、Pythonで書かれたAtCorderの回答はありますし、蟻本のコードもPythonで書かれたものがでてきます。

競プロで必要なのは言語特性というよりは、競プロ独特の考え方なので他の言語はともかく、メジャーで使用者も多いPythonなら何の問題もなさそうです。

私もC++はほとんどわかりませんし、今の所は勉強する気もありません。

水色になるには

AtCorderの勉強法をいろいろ調べた結果、水色になる方法は、過去問のA〜Dを解きまくるということでした。

参考

  • https://qiita.com/e869120/items/eb50fdaece12be418faa#2-1-%E6%B0%B4%E8%89%B2%E3%82%B3%E3%83%BC%E3%83%80%E3%83%BC%E3%81%A7%E8%A6%81%E6%B1%82%E3%81%95%E3%82%8C%E3%82%8B-4-%E3%81%A4%E3%81%AE%E3%81%93%E3%81%A8
  • https://i.ytimg.com/an_webp/8YW5g2f8GKA/mqdefault_6s.webp?du=3000&sqp=CIDylJUG&rs=AOn4CLAd38MwRkPMKlC7fq7nLmpw0MzKVQ

水色に求められるのは、A-Dの4完を安定させることです。

そのためには過去問を解きまくって、自分が知らないアルゴリズムや考え方が出てきたら都度勉強して、その問題と類問を自力で解けるようにするしかありません。

まとめ

以上、AtCorderをはじめたころには知らなかったことをまとめて見ました。

AtCorder、競技プログラミングは独特の世界です。知っているのか、知らないのかの差が大きいです。私もまだはじめたばかりなので、まだまだ知らないことが多そうです。今後もアンテナを貼り続けて、知識をアップデートし続けていきたいと思います。