社会人がAtCoderに参加する時に読むと良い本

プログラマとして働いている社会人が、 「競プロといふものをやってみんとす」と言って AtCoderに出て、緑パフォも出ずに終わってしまうことがあります。

彼らは実戦的にはちゃんと動くソフトウェアを作れるのですが、 競技プログラミングとなると全く力を発揮出来ません。

なぜこんなことが起こるかというと、 そもそも実戦的なソフトウェアの実装と競技プログラミングで要求される実装には、 かなりの乖離があるからです。

これが、「競技プログラミング 意味ない」という大量の検索を生んでいる理由でもあります。 いつもおれのサイトに来てくれてありがとうございます。

学生の方が強いのはある意味当たり前です。 授業でアルゴリズムとデータ構造の授業を受けたばかりですし、 場合によっては大学院でアルゴリズムの研究をしてる場合もあります。 競技プログラミングではどちらかというと、大学で学ぶ理論を要求されます。

制約のうちで問題が解けるようなアルゴリズムをデザインする理論部分がもっとも重要で、 それが出来ているならば大抵の問題は、実装自体は大したことがないです。 競技「プログラミング」とはいいますが、仕事でソフトウェアを作ってきた人間から見ると、 そのプログラミングの部分ははっきり言って大したことがないというのが実際のところです。

例えば、みなさんは仕事のソフトウェアの開発において、 木構造やグラフを実装したことがどれほどありますか? 再帰関数を書いたことがどれだけあるんですか? 関数型言語を使っていれば別ですが、ふつうはそれほど多くないと思います。 おれ自身も、Haskellなどの関数型言語を勉強しなかったら、 大学の授業以降は再帰なんか書いたことなかったはずです。 少なくとも、パズルのような問題を解いたことはあまりないはずです。

動的プログラミング?メモ化? 名前くらいは聞いたことはあるかも知れません(メモ化を実装したライブラリはあります。例えばGuava) が実際に再帰関数をメモ化したことがある人は少ないと思います。

むしろ、実戦的なソフトウェア開発では、 「データがすべて」「型がすべて」などと言われます。 パズル的に関数やデータ構造を操作するという機会はあまりありません。

例えば、木構造の走査一つとっても、 深さ優先ではスタックを使い、幅優先ではキューを使うというのは知識としてあったとしても、 普段そんなコード書いていないから、いきなり書けと言われても無理に決まってます。

なので、実戦と理論のギャップを埋めれば、 自然とある程度の問題は解けるようになるのです。 少なくともAtCoderのCやDまではすぐに解けるようになるはずです。

この観点でおれが読んで良かったなと思う本がこれです。

この本は大学で習うようなデータ構造とアルゴリズムとかグラフ理論の学び直しのような本で、 内容がとても軽いので、まず競プロのとっかかりとして読む本として優れていると思います。 いわゆる「蟻本」はいつかは読む必要がありますが、扱ってる内容が少し難しいので、 まずはこの本で学び直しをすることをオススメします。

あるいは、別に競技プログラミングにどっぷり浸かる気はないという人にとっても、 学ぶ価値のある本です。

章立てはこうなってます。

  • Part 2 プロコンのためのアルゴリズム
    • アルゴリズムと計算量
    • 初等的整列
    • データ構造
    • 探索
    • 再帰・分割統治法
    • 高等的整列
    • 二分探索木
    • ヒープ
    • 動的計画法
    • グラフ
    • 重みつきグラフ
  • Part 3 プロコン必携ライブラリ
    • 高度なデータ構造
    • 高度なグラフアルゴリズム
    • 計算幾何学
    • 動的計画法
    • 整数論
    • ヒュースティックプログラム

読み方ですが、 Part 2は基本なので全部やるとして、 Part 3は部分的にかじればよいでしょう。 Part 3はおれも全部読んだわけではないです。 競プロerの好きなデータ構造で上位にランキングされる Union Findと初等的なグラフアルゴリズム (ダイクストラ法・ワーシャルフロイド法・クラスカル法くらい) だけ学んでおけば十分と思います。

この本が蟻本より優れているのは、どのトピックにも例題がついていて その例題がAOJ(Aizu Online Judge)で提供されているという点です。 トピックについて学び、手を動かしてみたいと思ったらAOJにいって例題を解くという スタイルで学習を進めていくことが出来ます。

https://d33wubrfki0l68.cloudfront.net/1d70d50569f83fcdd961265333abdb17ff699241/fd2c4/images/1578956239.webp

このエントリーをはてなブックマークに追加

See also