Pythonではじめる競技プログラミング #pyconjp
PyConJP2014で競技プログラミングについてLTしてきました。
発表で出した問題と、主要な競技プログラミングのコンテストについて紹介したいと思います。
発表資料
発表で紹介した問題の回答について
発表でみなさんに考えてくださいと言った問題です。
単純に全探索をすると時間制限にひっかかってしまうこの問題。
a + b + c + d = 0 は、
a + b = - (c + d)
というのを利用して解いた例がこんなかんじになります。
- create_pairsの関数でAとB，CとDをそれぞれ足し合わせた数を計算し、それがいくつあるかをカウントしておきます。
- あとはAとBの合計値をfor文でまわして、CとDの合計値のなかに-(A+B)がいくつあるかを探しています。
この解法だと計算量はO(N **2)なので、Nが200でも間に合いますね。
(ここで利用しているcollections.Counterは、めちゃくちゃ使える子です！)
他にもいろいろな解法があると思います。
みなさんはどんな風に解いたかぜひ教えて下さい(^^)
主要なコンテストの紹介
地味にこのスライドはがんばって作りました。
TopCoder(SRM)
毎回参加者は2000人以上で、競技者以外にも広く知られているコンテスト。
このコンテストのランク（色）を使って、すごい人はレッドコーダーとか、イエローコーダーとか言われる。
なんとなく１番真剣にがんばらなきゃいけない気がしてしまうコンテスト。
あと参加するまでにプラグインを入れたりしなきゃいけなくてちょっぴりめんどくさいです。
(Pythonに対応しているオススメプラグインはgreedです。)
現在私はがけっぷち青コーダー( >ω<)
半年前はバリバリのグレーコーダーの私でしたが、
「競技プログラミングで青春」してれば気合で青くらいにはなれます。
それ以上は・・・・さらに努力が必要になって来ると思います＞＜
以下(めっちゃ恥ずかしいけど)私のレーティングのグラフです。
CodeForces
最近流行ってる気がしてるコンテスト。
私は初心者にこのCodeForcesをおすすめしています。
毎回参加者は4000人以上！
参加登録さえすれば、めんどうな準備は一切いりません。
いろいろな言語に対応しています。(Python2でも3でも！)
一度レーティングが落ちても次がんばればすぐ上がれる（気がする）ので、気軽に参加できます。
問題が5問あるので、1問解けなくても次の問題ってチャレンジできるのもいいところ。
TopCoderは問題ごとの難易度の差が大きすぎてそうはいかないです。
私のグラフはこんな感じ。
元気よく上がったり下がったりしてますね。
AtCoder (アットコーダー)
毎週土曜の21:00~と、時間が決まってるのが良いところ。
英語で問題文よむのつらい(´；ω；｀)って方はぜひAtCoderに参加しましょう。
ABC(AtCoder Beginner Contest)は、初心者でも解ける問題が多いです。
コンテスト後に丁寧な解説が日本語でみれるのが良い所ですね。
CodeForcesと同じくらい様々な言語で参加することができます。
PyConJP2014について
PyConはPythonistaにとっては神イベントです！
今年は、衝撃的な基調講演から始まり、たくさんの興味深い話が聞けました！
特に私が面白いと思ったのは以下２つです。
その他以下のサイトで色々な講演を紹介しています。
さいごに
私は今回は5分という短い時間の中で、いかに競技プログラミングに興味を持ってもらえる内容にできるか頑張って考えてみました。
初めての発表で未熟な点も多かったと思いますが、皆さんに楽しんで聞いていただけたようで嬉しかったです( o･ω･)！
一緒に競技プログラミングで青春しましょう！
