競プロ始めた - アドカレ用

競プロ始めた

この記事は Competitive Programming Advent Calendar 2017 - Adventar のために書かれました。

adventar.org

あまり新規性のある内容は書けないので、半年ぐらい素人が競プロやってみてどうだったかをつらつら書いてみようと思います。他の人の参考になれば幸いです。

競技プログラミング(AtCoder限定)を始めたのは2017/06/18からです。勝手がわからなかったのか、無謀にもAtCoder Grand Contestに参加しています。当然なにも解けていません。

競プロやろうと思った動機

• 転職に役立ちそうなので実は前からやろうとは思ってた
• 働き始めてからこのかた何か作りたいものがいろいろあったけど最近は特になくなってきたため
• グラフ (データ構造) - Wikipedia の話を見て、現状にも適用できそうだと思ったため *1
  • 発端となったのは、RDBでは ナイーブツリーSQLアンチパターン - ナイーブツリー は表現しにくいが、グラフDBではそれが容易に表現できそうだということ

AtCoderの感触

最初３ヶ月ぐらいの体感

• 問題文を読んでも頭に入らない（NとかKってなんぞ？高橋くんって誰）
• アルゴリズムを学んでないのでとても効率の悪いプログラムを書いてしまう
  • 最初は遅い言語で書いてるのが原因かと思ったのですが、遅い原因の90%は正しいアルゴリズムが選択できていないことのようです
• AC*2されたコードを読んでも理解できない、解説読んでも理解できない

最初３ヶ月ぐらいの気づき

• AtCoderにはBeginnersコンテストがあるので、初心者はまずそれに出たほうがいい
• AtCoderは毎週土曜日or日曜日の21:00〜開催
• レーティングの更新について を読んで、AtCoderで順位がつくと灰、茶、緑、水色、青、黄色、オレンジ、赤といった称号がつき赤色はRedCoderと呼ばれるヤバイ奴らということを知る
• コンテストにはratedとratedじゃないコンテストがあるので、順位を上げるにはratedなコンテストだけでれば良い
• プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 を見て、アルゴリズムの種別はけっこう体系化されていることに気づく

後半３ヶ月ぐらいの体感

• 問題文の内容がすぐに頭に入るようになってきた（要は慣れ）
• 効率の良いアルゴリズムが何か、計算量のオーダー表記について意味がわかってきたのでどうすると計算が遅くなってしまうかわかってきた
  • 計算量オーダーについて - Qiita が参考になりそう
• 他人の書いたコードの意味が徐々にわかってきた
  • 競プロerが書くコードは確かに汚いが、それを理解できない理由は使われているアルゴリズムの仕様を知らないからである
  • あとC++で書かれるコードにマクロを使いまくるために、後から読む人はそれが何かわからない

後半３ヶ月ぐらいの気づき

• 勉強するときに、コードを書くよりも解説読んだりアルゴリズム要素を探すほうがよさそうだとわかってくる
  • アルゴリズムをわかって初めてコードを書く意味が出てくる
• 出題されるアルゴリズム要素は、それなりに限られているようだということ
  • なんとなく、学ぶべき数学としては組合せ、グラフ、確率、整数ぐらいが範囲かと、大雑把に言うと離散数学
• プロジェクトオイラーはいいぞ

以上からの来年の目標

• AOJ本、蟻本を読んで問題解く
• AtCoder Beginners Contest ４完
• 緑コーダーからの水色コーダー

*1:実際グラフアルゴリズムと数え上げ、組み合わせ、確率らへんはギョームプログラミングに役立つと思う

*2:Acceptedの略、問題文に対して正しいコードを提出するとこういう表示が出る

アルゴリズムまとまってるサイト

メモ用、他にあれば追記する

ポータルサイト

英語読めれば大抵の典型問題に関する示唆が得られる

www.geeksforgeeks.org

www.csegeek.com

数学問題に対抗するために

mathtrain.jp

大学の授業シラバス系

• ヨークカレッジ・ペンシルベニア校
  • Lecture Notes

• イリノイ大学アーバナ・シャンペーン校
  • Jeff Erickson's Algorithms, Etc.

個人サイト

• • tubo28.me

このサイトにあったサイトも転記している

• [O] 無料で読める2つのアルゴリズムの講義資料

ダイクストラの出身校とかでググってもいいレクチャーノート出てこないのはちょっと不思議

AtCoder - AtCoder Beginner Contest 040 (道路の老朽化対策について) を解いてみた

ABC 040 D問題に使われるアルゴリズム要素はUnion-Findです。

Union-Find自体は前回ブログ記事にしていたのですが…これだけでは足りませんでした。ACするためには経路圧縮とrankによる木のマージ処理が必要です。

nantonaku-shiawase.hatenablog.com

今回の内容はAOJ本にバッチリ書かれています。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

アルゴリズム

経路圧縮

前の記事の中で、ある要素の最上位の親を求める処理を以下のように求めたはずです。

def root(i, id)
  while i != id[i] do
    i = id[i]
  end
  i
end

しかし、これではある要素を求める際に毎回whileループが回ります。計算量が増えてしまいます。以下のようにすることで、途中までの要素を全て書き換えます。関数名はfind_setに変えます。

def find_set(i, id)
  if i != id[i]
    id[i] = find_set(id[i], id)
  end
  id[i]
end

rankによる木のマージ処理

木のマージ処理に関しては、擬似コードのほうがわかりやすいでしょう。前回作ったuniteという関数に以下のような処理を加えます。

またアメリカの大学の資料から

• http://jeffe.cs.illinois.edu/teaching/algorithms/notes/17-unionfind.pdf
• https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/UnionFind.pdf

UNION-BY-SIZE (x, y) 
    r ← FIND (x).
    s ← FIND (y).
    IF (r = s) RETURN.
    ELSE IF (size(r) > size(s))
        parent(s) ← r.
        size(r) ← size(r) + size(s).
    ELSE
        parent(r) ← s.
        size(s) ← size(r) + size(s).

これらを行うことで計算量が削減され、満点となるようです。AtCoderの問題としては、これらの計算量の削減がなくてもロジックとUnion-FIndの実装ができていれば50点もらえます。

解答

• 今回、解答の作成にあたってはだいぶ他の人の解答を真似している面があります…コピペはしてないけど

Submission #1754689 - AtCoder Beginner Contest 040 | AtCoder