なんとな~くしあわせ?の日記

「そしてそれゆえ、知識そのものが力である」 (Nam et ipsa scientia potestas est.) 〜 フランシス・ベーコン

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

競プロ始めた

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

adventar.org

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

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

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

  • 転職に役立ちそうなので実は前からやろうとは思ってた
  • 働き始めてからこのかた何か作りたいものがいろいろあったけど最近は特になくなってきたため
  • グラフ (データ構造) - Wikipedia の話を見て、現状にも適用できそうだと思ったため *1

AtCoderの感触

最初3ヶ月ぐらいの体感

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

後半3ヶ月ぐらいの体感

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

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

以上からの来年の目標

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

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

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