プロコン

概要 †

• プロコンで必要となる知識のまとめ。
• 難問を解いて自分のものにする、短時間で学習するサイクルが回せ。
• 役に立つとは別の軸でプログラミングの面白さを主張することで裾野を広げる活動
• 競技プログラミングのメリット
  • 脳内シミュレーション能力の向上
  • コードで語り合う、技術力を認め合い、語り合う。
  • ある問題を一緒に解く時の一体感が楽しい。

下位ページ †

• アルゴリズム
  • プロコン/AtCoder
  • プロコン/スライド
  • プロコン/チャレンジ
  • プロコン/作問
  • プロコン/初心者向け
  • プロコン/勉強したこと
  • プロコン/特有の注意

目次 †

記録 †

• Topcoderのはむこと分布
• Codeforcesのはむこと分布
• はむこ主催の勉強会
• はむこ問題
• プロコン記録
• チャレンジ記録

失う信用 †

• 人が作った問題を解くという枠組みから出られていない
  • いつも自分が作った問題を解いているわけではないでしょう？サーベイの高速化になる。
  • じゃあどういう枠組みかというと、「世界中から10秒以内で解ける全ての問題を集める」世界なので
  • 別に人が作った問題を解くのも面白いじゃん…
• 意味のないことをしている
  • 競技プログラマのコード速度を見たことがありますか？めちゃ早いよ。
  • 無意味だからやらない、と人事の人が言っていると、優秀層エンジニアが逃げる。
  • 強いエンジニアは往々にして「技術が面白いから技術をする」ので、そういう優秀層エンジニアが逃げる。
• お金が儲からない
  • コード速度が上がることはお金が儲からないと思っているの？
  • お金が儲からないからやらない、となると優秀層エンジニアが逃げる。
• 社会貢献できていない
  • プログラミングの能力を高めるのが社会貢献に繋がらないなら、仕事ばっかりやって成長しないゴミエンジニアを応援してそう
• 承認欲求に取り憑かれている
  • それは真逆で、やると自信がどんどんなくなってくるので、承認欲求は満たされない。
  • 実績を求めるという話もある。競技や資格以外に求められる人はやらなくてもいい
  • レートを見ればどれくらいのコーディング能力があるか一目瞭然なので、就活にも役に立つみたいになっていく。

†

• REPマクロは妥当な作法
  • 生for文は言語の欠陥
  • boost::irangeやiota_viewなどが使えない状況ならREPマクロで対処するのは必要。
  • 慣れてない人に「汚い」とか言われたりするかもだけど、そういう場合はLinuxのソースコードとかを見せれば解決すると思う
  • Linuxのソースコードには #define for_each_...(...) のような定義が100個以上存在している
  • マクロによる構文の拡張はC言語における妥当な作法だと主張することができます
  • by うさぎさん

アルゴリズムの勉強必要性 †

• 特にこのページはアルゴリズムのまとめ。
• アルゴリズムが判ってない、計算量が判ってないから、「○○は遅いからダメ」みたいなのをあらゆる状況で言っちゃう人は割と多い。必要なところだけ早くすればいい。
• 以下の問題を何とかしたいから勉強しているのだけど、キリがないという気分
  1. 正しいと信じてるプログラムが間違ってるケースを減らしたい
  2. 脳内でこうやればできる、というところと実装の溝を減らしたい。実装を単純作業にしたい
  3. トップレベルの人でも普通知らない、非自明かつ一般的なアルゴリズムを使えるようになりない
  4. 典型なのに知らずに解けないケースを減らしたい
• 上位者の提出の早いコードを読んで学ぶ必要性
• コンテスト中だけでもいいから、「ちゃんと最後まで問題に向き合う」というのは大切
• 「サンプルが通った時の提出前の回答の信頼度」みたいなのもまるで計れないと、テストの数をどれくらいにすべきかの直感がなくなる
• 実装に時間がかかった問題は、ちゃんと上位陣のコード読んでリファクタリングしないと、実装力の伸びは鈍化する。ちゃんとシンプルな実装を学ぶのとても大切。

レートの直感 †

• AtCoder?は赤→銀→金は4倍ずつレアになる。そこから先は倍々。茶色以下は歪められている（本当は負のレートになるはず）
• 将棋との対応
  • [僕は大体13%
  • 将棋ウォーズを見ると13%は二段相当
  • 将棋ウォーズ二段はアマチュア二段～三段相当と公式が認定している （将棋ウォーズは少し段位認定が厳しいらしい）

マネタイズ †

• Atcoder 定期コンテスト1回で100万-200万（AGCだと1コンテストで15万円くらいを業務委託で払っている？）, マラソンも1問30万くらい？オンライン一発だと150~200万、予選＋決勝方式だと300~400万くらい
  • Codefestivalは異常なので一回問題だけで1000万以上
• Topcoder
  • Topcoderでお金を得る
  • topcoderのビジネスはデザインとかがメイン。マラソンは割と外注あるが客寄せが大きな目的。

• 1000万の案件も

言語 †

• AtCoder?の言語アップデートでPythonにsortedcontainersってのが入ってたんですか！？（YouTube?のコメントで知りました）競プロでのPythonのデメリットの3割くらいが消えました。

練習方法 †

• 解いた問題数を増やすのは良い事なんだけど、解いた問題数を増やすためだけに、簡単な問題を解きまくるのってすげえ時間の無駄
• Codeforces
  • 黄色の人とかがCFのBCD埋めるのは典型力と非典型力と実装力が程よくついていいと思うけどE埋めは本当に虚無なのでやめた方がいいと思う
  • Eには典型重実装がたくさんあって不毛
• AOJ-ICPC
  • 多くの人にはオススメできない気がしてきました。
  • 自分はすごい実力ついたと思っていたけれど、赤になってから実装力不足が目立ち始めたから始めただけ
  • 赤になるまでは質の高い問題をひたすら解くべき

• アプローチの
  • アプローチの手法とは例えば「N=1のときはどうか」と簡単版の問題を考えてみるとか「この条件がないとNP-hardになるからここが本質か」とかそういう風に問題のどこが難しいのかを探る手法
  • 考察力とは、僕は問題に対するアプローチの手法の引き出しをどれだけ持ってて使えるかって感じだと思っています。
  • 問題解決能力と呼ばれてるのと近いと思います。
  • エレガントな問題解決って本とか[[アルゴリズムパズルっぽい本>https://www.amazon.co.jp/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%83%91%E3%82%BA%E3%83%AB-%E2%80%95%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9E%E3%81%AE%E3%81%9F%E3%82%81%E3%81%AE%E6%95%B0%E5%AD%A6%E3%83%91%E3%82%BA%E3%83%AB%E5%85%A5%E9%96%80-Anany-Levitin/dp/4873116694 ]]とかはそういう部分扱ってるように見えます

コンテストの目的 †

• コンテストの役目は、優秀な人材を育てることではなくて、優秀な人材と、そうでない人材とを容易に見分けることが可能な場を提供すること
  • A+Bが解けないみたいなやつを足切りするなど
• 実は緑くらいあれば、ウェブ開発とかは普通にできる。

外部の人への説明 †

• 「単体テストは用意されているけど、単体テスト専用対策による不正がされないように、不正解ケースを教えてくれないシステム」

参考 †

• Div2 Hard 講評
• 診断人さんのDP
• 非公式難易度表
• Spaghetti
• tubo28
  • 現代的な書き方
• Antaさんのライブラリ
  • https://www.dropbox.com/sh/9lknvq4xay709cn/Ly2afJ-87e/%E3%83%A9%E3%82%A4%E3%83%96%E3%83%A9%E3%83%AA%E3%81%BE%E3%81%A8%E3%82%81.txt
  • http://d.hatena.ne.jp/anta1/
  • https://www.dropbox.com/sh/9lknvq4xay709cn/J96DtYOP8V

ライブラリ †

• はむこのライブラリ