読者です 読者をやめる 読者になる 読者になる

ctyl's problem solving

競技プログラミングが主な話題です。

競技プログラミングを始めて2ヶ月が経ちました

唐突ですが,直前のエントリーで話題にしたCODE FESTIVAL予選B,通過していました.久しぶりにこの種類の嬉しさを噛み締めています.というのも,大学に入ってからは評価というものは公正でないものも多く(これは考え方の問題ですが),評価の仕方も教官によってまちまちだったのですが,今回はオートジャッジによる絶対評価と順位が1人単位でわかり,1つ順位を上げる価値が場所によってはとても大きくなるというもので,大会ならではという感じがします.自分がかつて参加した中で一番近いのだと数学オリンピックがそれにあたりますね.さすがにオートジャッジではなかったですが・・

決勝はベテラン勢が上位を制するのは見えているのですが,それでもあと半月あがいて納得できる成績を残したいです.具体的な数値目標としては上位半分(つまり100位以内)に入ることでしょうか.

かつて数学の大会の虜になったのも,中学入りたての当時とりあえずと参加した数学の大会で学内唯一予選を突破し決勝では運良く準優勝したのが,その後高校卒業までモチベーションを上げ続ける最大のトリガーだった記憶があるので,この年ながら競プロでもいい流れを作っていきたいなどと思っています.

さて,競技プログラミングを始めて2ヶ月が経ちましたが,今のところの到達度を書いておきます.もし競プロ始めたての方が万が一この記事を読まれていたら参考にしていただけると嬉しいです.

  • TopCoder Rate: 1131(緑, Highest)
  • Codeforces Rate: 1619(青, Highest: 1661)
  • ABCは全完できるようになった(始めてから皆勤で全回全完)
  • yukicoderを★3を中心に70問弱解いた(知らないアルゴリズムに関しては解説や他人のソースコードを見ながら学んだ)
  • CODE FESTIVAL 2015予選突破

当然ですがまだまだコーディングスピードや思考速度は遅く,あらゆるコンテストに出て上位を狙う,というアクロバティックなことはできないので,TopCoder, Codeforces, AtCoderを軸としてちょっとづつ手を広げられれば良いと思っています.

アルゴリズム的な知識や実装技量に関しての自己評価も載せておきます.

  • 実装系の問題は思考終了から実装に落とすまでの時間がまだ長い
  • STLのコンテナのメンバ関数の扱いは未だ不慣れ(mapにlower_boundがあることを知らなかったり)
  • DPはメモ化再帰方式だったり更新則が少し変わると対応できないことが多い
  • DFS,BFSに関しては理解したつもりだが,まだコンテストでの使用経験が少ない
  • Binary Search, Binary Index Treeなど計算時間が対数時間だったり1クエリに対して対数時間の処理で済むアルゴリズムやデータ構造は未習部分が多い.Segment Tree早く理解実装できるようにならないと・・
  • TLEが起きなさそうか起きなさそうかの見極めが甘い
  • 貪欲に関してはあまり深く考えずに使うことが多い
  • 整数・行列の累乗やmodに関する処理に関してはある程度は慣れた(気がする)

今はyukicoderを中心に各種アルゴリズム習得に利用しているのですが,AtCoderの問題は問題文も理解しやすく問題もいくらか洗練されている気がするので,ある程度までやったら今度はARCの過去問を中心に進めていく予定です.

 

 関連サイト:

http://codeforces.com/

https://www.topcoder.com/

AtCoder (アットコーダー)

http://yukicoder.me/

 P.S. チーム戦が可能なコンテストで誰かと一緒に組んで参加してみたい.