1 of 18

プログラミングコンテスト

について（仮）

@lizan

​

2010/12/18

0と1しか興味ない人のためのマルウェア分析会にて

2 of 18

目次

  • 自己紹介

​

  • プログラミングテストとは？

​

  • 参加レポート

​

  • 参加するには

​

  • 問題紹介

​

  • 質疑応答

3 of 18

自己紹介

​

  • 東京大学理科一類→経済学部

​

  • セキュリティキャンプ2007卒
    • 2008プログラミングコースチューター

​

  • プログラミングコンテスト歴
    • 情報オリンピック（優秀賞）
    • パソコン甲子園（準グランプリ）
    • EPOCH＠まつやま（優勝）
    • ACM/ICPC 2010（Tokyo-site 5th）

​

4 of 18

プログラミングコンテストとは？

  • 与えられた問題を
    • 制限時間内に
    • 効率的なアルゴリズムで
    • なるべくすばやく
      • 解く

​

  • 多項式時間で解けない問題（NP問題）
    • なるべく最適解に近い解を出す
      • ex. 巡回セールスマン問題

5 of 18

プログラミングコンテスト（学生向）

  • 情報オリンピック（中高生）

​

  • パソコン甲子園（高校生）

​

  • 高専プロコン（高専生）

​

  • EPOCH＠まつやま（大学生以下）

​

  • ACM/ICPC（大学生）

6 of 18

プログラミングコンテスト（一般向）

�� 

    • Alogrithm部門
    • Marathon部門

​

​

  • Google Code Jam

7 of 18

参加レポート（ACM/ICPC）

  • 正解すると風船

​

  • 色は問題に対応

8 of 18

参加レポート（EPOCH＠まつやま）

  • システムが独特

​

  • 運要素を取り入れて

　「楽しく」

​

  • 本戦第2ステージ

　　4色オセロ

9 of 18

参加記（パソコン甲子園

ICPCを意識したルール・運営

10 of 18

まずはここから！TopCoderのススメ

  • 予め用意されたインタフェースを実装するタイプ
    • 入出力の処理が不要

​

  • 始めるにあたって必要な知識
    • C++/C#/Javaのいずれか
    • if文, for文が書ける
    • 配列と文字列の基本的な扱い方を知っている
    • 関数が分かっている

​

    • 英語が分かる

11 of 18

TopCoderのSRMの流れ

  • Coding Phase（75分）
    • 問題を読み、コードを書く
    • 提出した時間に応じて仮の点数がつく

                ↓

  • Challenge Phase（15分）
    • みなさん大好きなハッキング
    • 他人のコードを読んで、失敗しそうなテストケースを提出する

                ↓

  • System Test Phase
    • 出題側が用意したテストケース＋Challenge Phaseで成功したケースでテストされる

12 of 18

Google Code Jam

  • 標準入力から読み込んで標準出力に提出

​

  • 言語は自由
    • 自分のマシンで実行して結果を提出

​

  • 部分点がある
    • 最も効率的なアルゴリズムが思いつかなくても点数がもらえる

13 of 18

オンラインジャッジシステム

  • AOJ（会津大学）
    • http://rose.u-aizu.ac.jp/onlinejudge/
    • 日本語の問題が多い

​

  • POJ（北京大学）
    • http://poj.org/
    • 問題数が多い

14 of 18

問題紹介（1）

http://poj.org/problem?id=1852

  • 　長さL cmの竿の上をn匹のアリが毎秒1cmのスピードで歩いています。アリが竿の端に到達すると竿の下に落ちていきます。また、竿の上は狭くてすれ違えないので、二匹のアリが出会うと、それぞれ反対を向いて戻っていきます。各アリについて、現在の竿の左端からの距離x[i]はわかりますが、どちらの方向を向いているのかはわかりません。すべてのアリが竿から落ちるまでにかかる最小の時間と最大の時間をそれぞれ求めなさい。

15 of 18

問題紹介（1）解答

  • 最短時間
    • 近いほうの端に向かうと仮定
    • 出会うことはない

​

  • 最長時間
    • 出会うとそれぞれ逆向きに進む

​

    • アリを区別しなければ、そのまま進んだのと同じ

16 of 18

問題紹介（2）

  • http://bit.ly/fla8qa
  • 人間が1人、モンスターがM匹、ウサギがB匹います。ここから、モンスターか人間がいなくなるまで無作為に2匹（もしくは1人と1匹）を選び出し、以下の行動を繰り返します。
    • モンスターとモンスターが選ばれると、両方のモンスターが死にます
    • モンスターとモンスター以外が選ばれると、モンスター以外が殺されてしまいます
    • ウサギとウサギが選ばれると、何も起こりません
    • ウサギと人間が選ばれると、人間の生存確率が最も高くなるように、ウサギを殺す、またはそのままにする、のどちらかの選択をします
  • モンスターの数Mとウサギの数Bが与えられたときに、最後に人間が生き残る確率を答えなさい。ただし、M、Bともに1000以下の整数とする。

17 of 18

問題紹介（3）

  • Binary codes

    http://poj.org/problem?id=1147

​

  • ブロックソートと言って、bzip2のアルゴリズムの一部

​

​

18 of 18

ありがとうございました